殷人昆数据结构

,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第十章 文件、外部排序与搜索,1,主存储器和外存储器,文件组织,外排序,多级索引结构,可扩充散列,Trie树,第十章 文件、外部排序与外部搜索,2,主存储器与外部存储器,外存储器与内存储器相比，优点是：,价格较低,永久的存储能力,缺点：,访问外存储器上的数据比访问内存要慢56个数量级,要求我们在开发系统时必须考虑如何使外存访问次数达到最少。,3,磁带（tape）,磁带是一种顺序存取设备。,磁带主要用于备份、存储不经常使用的数据，以及作为将数据从一个系统转移到另一个系统的脱机介质。,读出头,写入头,磁带,送带盘,卷带盘,4,磁带卷在一个卷盘上，运行时磁带经过读写磁头，把磁带上的信息读入计算机，或者把计算机中的信息写到磁带上去。,数据记录在磁带带面上。在带面上并列存放有 9 个磁道的信息，即,每一横排有 9 位二进制信息,：8 位数据加 1 位奇偶校验位。,磁带的存储密度用,BPI（Bit Per Inch）,为单位，典型的存储密度有 3 种：,6250BPI,（=246排/mm）、,1600BPI,（=64排/mm）、,800BPI,（32排/mm）。正常走带速度为35m/Sec，因设备而异。,5,数据的传送速度 =,存储密度,走带速度读写时间,。,在应用中使用文件进行数据处理的基本单位叫做,逻辑记录,，简称为记录；在磁带上物理地存储的记录叫做,物理记录,。,在使用磁带或磁盘存放逻辑记录时，常常把若干个逻辑记录打包进行存放，把这个过程叫做“块化”（blocking）。经过块化处理的物理记录叫做,块化记录,。,磁带设备是一种启停设备。磁带每次启停都有一个加速与减速的过程，在这段时间内走带不,6,稳定，只能走空带，这段空带叫做记录间间隙,IRG,（Inter Record Gap）或者块间间隙,IBG,（Inter Block Gap），其长度因设备而异。,磁带速度,75-200英寸/秒,传输速度,字/秒,1.5-16,ms,1.5-16,ms,定速,加速,IBG,0.30.75英寸,减速,物理记录,启动位置,IBG,0.30.75英寸,停止位置,传输开始,传输完成,经过时间,7,如果每个逻辑记录是,80个字符,，IRG为,0.75英寸,，则对存储密度为,1600BPI,的磁带，一个逻辑记录仅占,80/1600 = 1/20英寸,。每传输一个逻辑记录磁带走过,0.05英寸,，接着磁带要走过一个IRG占,0.75英寸,。结果大部分时间都花费在走空带上，,存储利用率只有1/16,。,如果将若干逻辑记录存放于一个块，将IRG变成IBG，可以提高存储利用率。例如，将50个有80个字符的逻辑记录放在一个块内，此块的长度将达到50,80/1600 = 2.5英寸，存储利用率达到,0.77,。因此在磁带上采用,按块读写,。,8,在磁带设备上读写一块信息所用时间,t,IO,= t,a,+ t,b,其中，,t,a,是,延迟时间,，即读写磁头到达待读写块开始位置所需花费的时间，它与当前读写磁头所在位置有关。,t,b,是对一个块进行,读写所用时间,，它等于数据传输时间加上IBG时间。,磁带设备只能用于处理变化少，只进行,顺序存取,的大量数据。,9,磁盘（disc）,磁盘存储器通常称为,直接存取设备,，或,随机存取设备,，它访问外存上文件的任一记录的时间几乎相同。,磁盘存储器可以,顺序存取,，也可以,随机存取,。,目前使用较多的是活动臂硬盘组：若干盘片构成磁盘组，它们安装在主轴上，在驱动装置的控制下高速旋转。除了最上面一个盘片和最下面一个盘片的外侧盘面不用以外，其他每个盘片上下两面都可存放数据。将这些可存放数据的盘面称为记录盘面。,10,主轴,盘片,活动臂,（回转臂）,读写磁头,磁道,柱面,11,每个记录盘面上有很多磁道，数据就存放在这些磁道上。它们在记录盘面上形成一个个同心圆。,每个记录盘面都有一个读写磁头。所有记录盘面的读写磁头都安装在同一个动臂上，随动臂向内或向外做径向移动，从一个磁道移到另一个磁道。,任一时刻，所有记录盘面的读写磁头停留在各个记录盘面的半径相同的磁道上。运行时，由于盘面做高速旋转，磁头所在的磁道上的数据相继在磁头下，从而可以读写数据,12,各个记录盘面上半径相同的磁道合在一起称为,柱面,。动臂的移动实际上是将磁头从一个柱面移动到另一个柱面上。,一个,磁道,可以划分为若干段，称为,扇区,，一个扇区就是一次读写的最小数据量。这样，对磁盘存储器来说，从大到小的存储单位是：盘片组、柱面、磁道和扇区。,对磁盘存储器进行一次存取所需时间：,当有多个盘片组时，要选定某个盘片组。这是由电子线路实现的，速度很快。,13,选定盘片组后再选定某个柱面，并移动动臂把磁头移到此柱面上。这是机械动作，速度较慢。这称为“寻查（,seek,）”。,选定柱面后，要进一步确定磁道，即确定由哪个读写磁头读写，由电子线路实现。,确定磁道后，还要确定所要读写数据在磁盘上的位置（如在哪一个扇区）。这实际上就是在等待要读写的扇区转到读写磁头下面。这是机械动作。这段时间一般称为旋转延迟（,rotational delay,）时。,真正进行读写时间。,14,在磁盘组上一次读写的时间主要为：,t,io,t,seek,t,latency,t,rw,其中，,t,seek,是,平均寻查时间,，是把磁头定位到要求柱面所需时间，这个时间的长短取决于磁头移过的柱面数。,t,latency,是,平均等待时间,，是将磁头定位到指定块所需时间。,t,rw,是传送一个扇区数据所需的时间。,在MS-DOS系统中，多个扇区集结成组，称为簇。簇是文件分配的最小单位，其大小由操作系统决定。在UNIX系统中不使用簇，文件分配的最小单位和读写的最小单位是一个扇区，,15,称为一个块（block）。,磁盘一次读写操作访问一个扇区，称为访问“一页”（page）或“一块”（block），又称为“一次访外”。,为了实施磁盘读写操作，在内存中需要开辟一些区域，用以存放需要从磁盘读入的信息，或存放需要写出的信息。这些内存区域称为缓冲区）。,多数操作系统至少设置两个缓冲区，一个为,输入缓冲区,；一个为,输出缓冲区,。,缓冲区（buffer）,16,例如在从磁盘向内存读入一个扇区的数据时，数据被存放到输入缓冲区，如果下次需要读入同一个扇区的数据，就可以直接从缓冲区中读取数据，不需要重新读盘。,缓冲区大小应与操作系统一次读写的块的大小相适应，这样可以通过操作系统一次读写把信息全部存入缓冲区中，或把缓冲区中的信息全部写出到磁盘。,如果缓冲区大小与磁盘上的块大小不适配，就会造成内存空间的浪费。,缓冲区的构造可以看作一个先进先出的队列。,17,缓冲区的定义及其操作,#include,#include,const int,DefaultSize = 2048,;,template ,struct,buffer,T,*,data,;,/,缓冲区数组,int,current,maxSize,;,/,当前指针, 缓冲区容量,buffer,(,int,sz = DefaultSize),:,maxSize(sz),current(0),data,= new,Tsz,;,assert (data,!=,NULL),; ,buffer(), delete,data,; ,18,void,OutputInfo (,ostream&,out,T x),;,/,缓冲区输出,void,InputInfo (,istream&,in,T,&,x),;,/,缓冲区输入,;,template ,void,buffer,:,OutputInfo (,ostream&,out,T x),if,(current,=,maxSize),for,(,int,i,=,0,;,i,maxSize,;,i+) out,datai,;,current = 0,;,datacurrent,=,x,;,current,+;,;,19,template ,void,buffer,:,InputInfo (,istream&,in,T,&,x,) ,if,(current,maxSize),x = datacurrent,;,current+,;,else ,for,(,int,i,=,0,;,i,datai,;,current = 0,;,;,20,文件组织,什么是文件,文件是存储在外存上的数据结构。,文件分操作系统文件和数据库文件,操作系统中的文件是流式文件：是没有结构的字符流,数据库文件是具有结构的数据集合,数据结构中讨论的是数据库文件。,操作系统对文件是按,物理记录,读写的，在数据库中文件按,页块,存储和读写。,文件的基本概念,21,文件的组成,文件,由,记录,组成；,记录,由若干,数据项,组成。,记录是文件存取的基本单位，数据项是文件可使用的最小单位。,从不同的观点，文件记录分为逻辑记录和物理记录。前者是面向用户的基本存取单位，后者是面向外设的基本存取单位。,能够唯一标识一个记录的数据项或数据项集称为主关键码项，其值称为主关键码；,不唯一标识一个记录的数据项或数据项集称为次关键码项，其值称为次关键码。,22,文件结构包括文件的逻辑结构、文件的存储结构和文件的操作。,文件的逻辑结构是线性结构,，各个记录以线性方式排列。,文件的存储结构是指文件在外存上的组织方式，它与文件特性有关。,顺序组织,索引组织,直接存取组织（散列组织）,文件的操作是定义在逻辑结构上的，但操作的具体实现要在存储结构上进行。,23,评价一个文件组织的效率,执行文件操作所花费的时间,文件组织所需要的空间。,文件的操作,检索,维护,简单查询,范围查询,函数查询,布尔查询,插入,删除,修改,重构,恢复,24,顺序文件 (Sequential File ),顺序文件中的记录按它们进入文件的先后顺序存放，其,逻辑顺序与物理顺序一致,。,如果文件的记录按主关键码有序，则称其为,顺序有序文件,，否则称其为,顺序无序文件,。,顺序文件通常存放在顺序存取设备（如磁带）上或直接存取设备（如磁盘）上。,当存放在顺序存取设备上时只能按顺序搜索法存取；当存放在直接存取设备上时，可以使用顺序搜索法、折半搜索法等存取。,25,顺序文件的存储方式,连续文件,：文件的全部记录顺序地存放外存的一个连续的区域中。优点是存取速度快、存储利用率高、处理简单。缺点是区域大小需事先定义，不能扩充。,串联文件,：文件记录成块存放于外存中，在块中记录顺序连续存放，但块与块之间可以不连续，通过块链指针顺序链接。优点是文件可以扩充、存储利用率高。缺点是影响了存取,和修改的效率。,26,直接存取文件 (Direct Access File),文件记录的,逻辑顺序与物理顺序不一定相同,。通过记录的关键码可直接确定该记录的地址。,利用散列技术组织文件。处理类似散列法，但它是存储在外存上的。,使用散列函数把关键码集合映射到地址集合时，往往会产生地址冲突，处理冲突有两种处理方式：,按桶散列,可扩充散列,27,(1) 按桶散列,文件中的记录成组存放，若干个记录组成一个存储单位，称之为,桶,。假若一个桶能存放m个记录，则m个互为同义词的记录可以存放在同一地址的桶中。当第m+1个同义词出现时，才发生“溢出”。,(a) 溢出链,当发生“溢出”时，将第m+1个同义词存放到“溢出桶”。并称存放前m个同义词的桶为“基桶”。溢出桶和基桶大小相同。当在基桶中检索不成功，就循指针到溢出桶中检索。,28,在这种散列文件中删除记录时，因为可能需要重新链接，所以只需,做一个逻辑删除标记,即可，待系统做周期性重构时再做物理删除。,桶大小为3的溢出桶链表示例,070,512 204 246,O,1,597 177,262 157,116 613,285 635 208,O,2,923 076,0,1,2,3,4,5,6,O,1,O,2,O,3,O,4,O,5,O,6,O,7,015 337 988,O,3,817 117 390,O,4,575 540 435,362,基桶编号 基桶区 溢出桶编号 溢出桶区,29,(b) 分布式溢出空间,溢出桶按照一定的间隔分布在基桶之间。如果有一个基桶溢出了，系统就将记录存放在下一个溢出桶中。,如果溢出桶自己溢出了，则使用下一个相继的溢出桶，这需要第二次溢出处理。,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,分布式溢出桶,基桶,基桶,基桶,溢出桶,溢出桶,30,如果系统对基桶按0, 1, 2, 3, 4, 5, 进行编号，在按间隔 G = 5 插入溢出桶后，可按下列公式按字节求出各个桶的实际存储地址：,其中，B,0,是在文件中第0号桶的起始地址，B是每个桶的字节数。在括号中的除数5表示每隔5个基桶安排一个溢出桶。,(c),相继,溢出法,此方法不设置溢出桶。当记录应存放的桶溢出时，溢出记录存放到下一个相继的桶中。,31,如果该桶已满，就把它放到再下一个桶中，如此处理，直至把记录存放好。,相继溢出法的优点是对溢出不需要漫长的寻找。紧邻的桶通常相距不多于一次磁盘旋转。但当邻近的多个桶被挤满时，则为了查找空闲空间就需要检查许多桶。如果桶的容量很小更是如此。,362,177,597 157 817 575,070 246 015 542,389,116 204 512 435,337 117,635 613,262 988,285 923 076 208,相继溢出法,0,1,2,4,3,5,6,7,9,8,10,32,(2) 可扩充散列,这是基于数字搜索树的一种散列方法，细节稍后介绍。,散列文件具有随机存放、记录不需进行排序、插入删除方便、存取速度快、不需要索引区和节省存储空间等优点。,散列文件不能顺序存取，只能按关键码随机存取。在经过多次插入、删除后，可能出现溢出桶满而基桶内多数记录已被删除的情况。此时需要重新组织文件。,33,索引文件 (Indexed File),索引文件由,索引表,和,主文件,组成。,索引表用于指示逻辑记录与物理记录间的对应关系，它是,按关键码有序的表,。,索引顺序文件,：主文件也按关键码有序。此时可对主文件分组，一组记录对应一个索引项。称这种索引表为稀疏索引。,索引非顺序文件,：主文件中记录未按关键码有序。此时，每一个主文件记录必须对应索引项。称这种索引表为稠密索引。,34,静态索引,：采用,多级索引结构,，,每一级索引均为有序表,。优点是结构简单，缺点是修改很不方便，每次修改都要重组索引。,动态索引,：采用,可动态调整的平衡搜索树结构,，如二叉搜索树、B_树与B+,树等。优点是插入、删除和搜索都很方便。,在文件中搜索时，访问外存所花费时间比在内存中搜索所需的时间大得多，因此，外存上搜索一个记录的时间代价主要取决于访问外存的次数，即索引树的高度。,35,0,1k,2k,3k,4k,5k,6k,7k,索引表,数据表,职工号,姓名,性别,职务,婚否,83,张珊,女,教师,已婚,08,李斯,男,教师,已婚,03,王璐,男,教务员,已婚,95,刘琪,女,实验员,未婚,24,岳跋,男,教师,已婚,47,周斌,男,教师,已婚,17,胡江,男,实验员,未婚,51,林青,女,教师,未婚,key,addr,03,2k,08,1k,17,6k,24,4k,47,5k,51,7k,83,0,95,3k,索引非顺序文件示例,36,22 12 13 30 29 33,36 42 44 48 39 40,60 74 56 79 80 66,92 82 88 98 94,子表1,子表2,子表3,子表4,数据区,33,48,80,98,索引表,1,2,3,4,max_ min_,key addr,索引顺序文件示例,当记录在外存中有序存放时，可以把所有,n,个记录分为,b,个子表 (块) 存放，一个索引项对应数据表中一组记录 (子表)。,37,对索引顺序文件进行搜索，一般分为两级:,先在索引表,ID,中搜索给定值,K,确定满足,ID,i,-1.,max_key,1) 个归并段得到,l,/2,个归并段。总归并趟数等于归并树的高度减一：,log,2,m,。,估计 2 路归并排序时间,t,ES,的上界为：,t,ES,=,m,*,t,IS,+,d,*,t,IO,+,S,*,n,*,t,mg,56,对 4500 个记录排序的例子, 各种操作的计算时间如下：,读,18,个输入块,内部排序,6,段,写,18,个输出块,6,t,IS,36,t,IO,成对归并初始归并段,R,1,R,6,36,t,IO,4500,t,mg,归并两个具有,1500,个记录的归并段,R,12,和,R,34,24,t,IO,3000,t,mg,最后将,R,1234,和,R,56,归并成一个归并段,36,t,IO,4500,t,mg,合计,t,ES,6,t,IS,132,t,IO,12000,t,mg,57,由于,t,IO,=,t,seek,+,t,latency,+,t,rw, 其中,t,seek,和,t,latency,是机械动作，而,t,rw,、,t,IS,、,t,mg,是电子线路的动作, 所以,t,IO,远远大于,t,IS,和,t,mg,。想要提高外排序的速度，应着眼于减少,d,。,若对相同数目的记录，在同样页块大小的情况下做 3 路归并或做 6 路归并(当然, 内存缓冲区的数目也要变化)，则可做大致比较：,归并路数,k,总读写磁盘次数,d,归并趟数,S,2 132 3,3 108 2,6 72 1,58,增大归并路数, 可减少归并趟数, 从而减少总读写磁盘次数,d,。,对,m,个初始归并段, 做,k,路平衡归并, 归并树可用正则,k,叉树 (即只有度为,k,与度为0的结点的,k,叉树) 来表示。,第一趟可将,m,个初始归并段,归并为,l,=,m,/,k,个归并段,，以后每一趟归并将,l,个归并段,归并成,l,=,l,/,k,个归并段,，直到最后形成一个大的归并段为止。归并趟数,S,log,k,m,树的高度减一 。,59,k路平衡归并 (k-way Balanced merging),做,k,路平衡归并时, 如果有,m,个初始归并段, 则相应的归并树有,log,k,m,+1,层, 需要归并,log,k,m,趟,。下图给出对有 36 个初始归并段的文件做 6 路平衡归并时的归并树。,60,做内部,k,路归并时, 在,k,个记录中选择最小者，需要顺序比较,k,-,1 次。每趟归并,n,个记录需要做 (,n,-,1)*(,k,-,1) 次比较,S,趟归并总共需要的比较次数为:,S,*(,n,-,1)*(,k,-,1) =,log,k,m,* (,n,-,1) * (,k,-,1),=,log,2,m,* (,n,-,1) * (,k,-,1) /,log,2,k,在初始归并段个数,m,与记录个数,n,一定时,log,2,m,*(,n,-,1) = const, 而,(,k,-,1) /,log,2,k,在,k,增大时趋于无穷大。因此, 增大归并路数,k, 会使得内部归并的时间增大。,61,使用“败者树”从,k,个归并段中选最小者, 当,k,较大时 (,k,6)，选出排序码最小的记录只需比较,log,2,k,次。,S,*(,n,-,1)*,log,2,k,=,log,k,m,* (,n,-,1) *,log,2,k,=,log,2,m,* (,n,-,1) *,log,2,k,/,log,2,k,=,log,2,m,* (,n,-,1),排序码比较次数与,k,无关, 总的内部归并时间不会随,k,的增大而增大。,下面讨论利用败者树在,k,个输入归并段中选择最小者，实现归并排序的方法。,62,败者树是一棵正则的完全二叉树。其中,每个叶结点存放各归并段在归并过程中当前参加比较的记录；,每个非叶结点记忆它两个子女结点中记录排序码大的结点(即败者)；,因此，根结点中记忆树中当前记录排序码最小的结点 (最小记录)。,败者树与胜者树的区别在于一个选择了败者(排序码大者), 一个选择了胜者(排序码小者)。,示例：设有 5 个初始归并段, 它们中各记录的排序码分别是：,63,Run0: 17, 21, ,Run1: 05, 44, ,Run2: 10, 12, ,Run3: 29, 32, ,Run4: 15, 56, ,冠军 (最小记录),输出段1当前记录,29,32,15,56,17,21,05,44,10,12,15,10,05,17,29,3,0,2,4,1,k,3,k,4,k,0,k,1,k,2,Run,3,Run,4,Run,0,Run,1,Run,2,ls,1,ls,0,ls,2,ls,4,ls,3,选中,64,次最小记录,输出段1最小记录，,段1下一记录参选，,调整败者树,29,32,15,56,17,21,05,44,10,12,15,10,44,17,29,3,0,1,4,2,k,3,k,4,k,0,k,1,k,2,Run,3,Run,4,Run,0,Run,1,Run,2,ls,1,ls,0,ls,2,ls,4,ls,3,选中,65,败者树的,高度为,log,2,k,+1,，在每次调整, 找下 一个具有最小排序码记录时, 最多做,log,2,k,次排序码比较。,在内存中应为每一个归并段分配一个输入缓冲区, 其大小应能容纳一个页块的记录, 编号与归并段号一致。每个输入缓冲区应有一个指针, 指示当前参加归并的记录。,在内存中还应设立一个输出缓冲区, 其大小相当于一个页块大小。它也有一个缓冲区指针, 指示当前可存放结果记录的位置。每当一个记录,i,被选出, 就执行OutputRecord(,i,)操作, 将记录存放到输出缓冲区中。,66,在实现利用败者树进行多路平衡归并算法时, 把败者树的叶结点和非叶结点分开定义。,败者树叶结点,key,有,k,+1个,key0,到,keyk,-,1,存放各归并段当前参加归并的记录的排序码，,keyk,是辅助工作单元, 在初始建立败者树时使用: 存放一个最小的在各归并段中不可能出现的排序码:,-,MaxNum,。,败者树非叶结点,loser,有,k,个, 其中,loser1,到,loserk,-,1,存放各次比较的败者的归并段号,loser0,中是最后胜者所在归并段号。另外还有一个存放各归并段参加归并记录的数组,r,k,。,67,k 路平衡归并排序算法,const int,MaxValue,= ;,/,当作无穷大值使用,void,kwaymerge(Element,*,r, int,k),int,i,q,;,r,= new,Elementk,;,/,败者树中的k个记录,int *,key,= new int,k+1,;,/,记录的排序码,int *,loser,= new int,k,;,/,存放败者树,for,(i,=,0,;,i,k,;,i,+,),/,叶结点的值,InputRecord(ri),;,keyi,=,ri.key,; ,for,(i,=,0,;,i,0,;,i,-,) adjust (key,loser,k,i),;,/,从keyk-1到key0调整形成败者树,while,(keyloser0,!=,MaxValue),/,选冠军,q,=,loser0,;,/,取当前最小记录,OutputRecord(rq),;,/,写到输出归并段,InputRecord(rq),;,/,读入下一个记录,keyq,=,rq.key,;,adjust (key,loser,k,q),;,/,从,keyq,起调整,Output end of run marker,;,/,输出段结束标志,delete,r,; delete,key,; delete,loser,;,;,69,自某叶结点keyq到败者树根结点的调整算法,void,adjust (,int,key,; int,loser,; int,k,; int,q),/,从,败者树某叶结点,keyq,起到根进行比较, 将最小,/,key,记录所在归并段的段号记入,loser0,。,for,(,int,t,=,(k+q)/2,;,t,0,;,t,/=,2),/t,是,q,的双亲,if,(keylosert,keyq),/,败者记入,losert,胜者记入,q,int,temp,=,q,;,q,=,losert,;,losert,=,temp,;,/q,与,losert,交换,loser0,=,q,;,;,70,每选出一个当前排序码最小的记录, 就需要在将它送入输出缓冲区之后, 从相应归并段的输入缓冲区中取出下一个参加归并的记录, 替换已经取走的最小记录, 再从叶结点到根结点, 沿某一特定路径进行调整, 将下一个排序码最小记录的归并段号调整到loser0中。,段结束标志MaxNum升入loser0, 排序完成。,归并路数,k,不是越大越好。归并路数,k,增大, 相应需增加输入缓冲区个数。如果可供使用的内存空间不变, 势必要减少每个输入缓冲区的容量, 使内外存交换数据的次数增大。,71,利用败者树进行,5,路平衡归并的过程,(1) 初始状态 (2) 加入15, 调整,29,15,5,17,5,05,5,10,-,5,5,k,3,k,4,k,5,k,0,k,1,k,2,ls,1,ls,0,ls,2,ls,3,ls,4,10,k,2,5,05,ls,3,k,1,17,5,k,0,ls,2,4,ls,4,15,k,4,-,k,5,29,k,3,5,ls,1,5,ls,0,72,(3)加入29, 调整 (4) 加入10, 调整,29,15,3,17,4,05,5,10,-,5,5,k,3,k,4,k,5,k,0,k,1,k,2,ls,1,ls,0,ls,2,ls,3,ls,4,10,k,2,2,05,ls,3,k,1,17,4,k,0,ls,2,3,ls,4,15,k,4,-,k,5,29,k,3,5,ls,1,5,ls,0,73,29,15,3,17,4,05,2,10,-,1,5,k,3,k,4,k,5,k,0,k,1,k,2,ls,1,ls,0,ls,2,ls,3,ls,4,10,k,2,2,05,ls,3,k,1,17,0,k,0,ls,2,3,ls,4,15,k,4,-,k,5,29,k,3,4,ls,1,1,ls,0,(5) 加入05, 调整 (6) 加入17, 调整,输出05,74,(7) 输出05后调整 (8) 输出10后调整,29,15,3,17,0,44,1,10,4,2,k,3,k,4,k,0,k,1,k,2,ls,1,ls,0,ls,2,ls,3,ls,4,12,k,2,1,44,ls,3,k,1,17,0,k,0,ls,2,3,ls,4,15,k,4,29,k,3,4,ls,1,2,ls,0,输入44,输出12,输出10,输入12,75,29,15,3,17,0,44,2,1,4,k,3,k,4,k,0,k,1,k,2,ls,1,ls,0,ls,2,ls,3,ls,4,k,2,2,44,ls,3,k,1,17,3,k,0,ls,2,4,ls,4,56,k,4,29,k,3,1,ls,1,0,ls,0,输入,输出17,输出1,5,输入,56,(9) 输出12后调整 (10) 输出15后调整,76,29,56,4,21,3,44,2,1,0,k,3,k,4,k,0,k,1,k,2,ls,1,ls,0,ls,2,ls,3,ls,4,k,2,2,44,ls,3,k,1,0,k,0,ls,2,4,ls,4,56,k,4,29,k,3,1,ls,1,3,ls,0,输入,21,输出29,输出21,输入,(11) 输出17后调整 (12) 输出21后调整,77,(13) 输出29后调整 (14) 输出32后调整,32,56,4,0,44,2,1,3,k,3,k,4,k,0,k,1,k,2,ls,1,ls,0,ls,2,ls,3,ls,4,k,2,2,44,ls,3,k,1,0,k,0,ls,2,3,ls,4,56,k,4,k,3,4,ls,1,1,ls,0,输入3,2,输出44,输出32,输入,78,(15) 输出44后调整 (16) 输出56后调整,56,3,0,2,1,4,k,3,k,4,k,0,k,1,k,2,ls,1,ls,0,ls,2,ls,3,ls,4,k,2,2,ls,3,k,1,0,k,0,ls,2,3,ls,4,k,4,k,3,1,ls,1,4,ls,0,输出,，,结束,输出56,输入,输入,79,初始归并段的生成 (Run Generation),为减少读写磁盘次数, 除增加归并路数,k,外, 还可减少初始归并段个数,m,。在总记录数,n,一定时, 要减少,m, 必须增大初始归并段长度。,如果规定每个初始归并段等长, 则此长度应根据生成它的内存工作区空间大小而定, 因而,m,的减少也就受到了限制。,为了突破这个限制, 可采用败者树来生成初始归并段。在使用同样大内存工作区的情况下, 可以生成平均比原来等长情况下大一倍的初始归并段, 从而减少初始归并段个数。,80,设输入文件,FI,中各记录的排序码序列为17, 21, 05, 44, 10, 12, 56, 32, 29 。,选择和置换过程的步骤如下：,从输入文件,F,I,中把,k,个记录,读入内存中, 并构造败者树。(内存中存放记录的数组,r,可容纳的记录个数为,k,),利用败者树在,r,中选择一个排序码最小的记录,r,q, 其排序码存入,LastKey,作为门槛。以后再选出的排序码比它大的记录归入本归并段, 比它小的归入下一归并段。,将此,r,q,记录写到输出文件,F,O,中。(,q,是叶结点序号),81,若,F,I,未读完,则从,F,I,读入下一个记录,置换,r,q,及败者树中的,key,q,。,调整败者树,从所有排序码比,LastKey,大的记录中选择一个排序码最小的记录,r,q,作为门槛,其排序码存入,LastKey,。,重复,直到在败者树中选不出排序码比,LastKey,大的记录为止。此时,在输出文件,F,O,中得到一个初始归并段,在它最后加一个归并段结束标志。,重复,重新开始选择和置换,产生新的初始归并段,直到输入文件,F,I,中所有记录选完为止。,82,83,若按在,k,路平衡归并排序中所讲的，每个初始归并段的长度与内存工作区的长度一致, 则上述9个记录可分成3个初始归并段：,Run0 05, 17, 21 ,Run1 10, 12, 44 ,Run2 29, 32, 56 ,但采用上述选择与置换的方法, 可生成2个长度不等的初始归并段:,Run0 05, 17, 21, 44, 56 ,Run1 10, 12, 29, 32 ,84,在利用败者树生成,不等长初始归并段,的算法和调整败者树并选出最小记录的算法中，用两个条件来决定谁为败者，谁为胜者。,首先比较两个记录所在归并段的段号,段号小者为胜者，段号大者为败者,；,在归并段的段号相同时,排序码小者为胜者，排序码大者为败者,。,比较后把败者记录在记录数组,r,中的序号记入它的双亲结点中, 把胜者记录在记录数组,r,中的序号记入工作单元,s,中, 向更上一层进行比较, 最后的胜者记入,loser0,中。,85,17, 21, 05, 44, 10, 12, 56, 32, 29 ,(1),初始化,(2),输入17, 调整,17,0,0,0,0,0,0,0,0,0,ls,1,ls,0,ls,2,k,2,k,0,k,1,0,0,0,2,1,ls,0,ls,1,k,0,ls,2,17,1,k,2,0,0,k,1,0,0,排序码,段号,86,17,21,05, 44, 10, 12, 56, 32, 29 ,(3),输入21,调整 (4) 输入05, 建败者树,21,21,1,1,17,1,0,0,2,0,ls,1,ls,0,ls,2,k,2,k,0,k,1,05,1,2,1,0,ls,0,ls,1,k,0,ls,2,17,1,k,2,21,1,k,1,05,选05,87,17,21,05,44,10, 12, 56, 32, 29 ,(5),lastKey=05, 置换 (6),lastKey=17, 置换,k,0, 选择17,k,2, 段号加1, 选择21,44,21,1,1,17,1,44,1,0,2,ls,1,ls,0,ls,2,k,2,k,0,k,1,44,1,0,2,1,ls,0,ls,1,k,0,ls,2,10,2,k,2,21,1,k,1,10,选21,选17,88,17,21,05,44,10,12,56, 32, 29 ,(7),lastKey=21, 置换 (8),lastKey=44, 置换,k,1, 段号加1, 选择44,k,0, 选择56,12,12,2,1,10,2,44,1,2,0,ls,1,ls,0,ls,2,k,2,k,0,k,1,56,1,2,1,0,ls,0,ls,1,k,0,ls,2,10,2,k,2,12,2,k,1,56,选56,选44,89,17,21,05,44,10,12,56,32, 29 ,(9),lastKey=56, 置换 (10) 输出段结束标志,k,0, 段号加1, 本段结束 选择10,32,12,2,1,10,2,32,2,0,2,ls,1,ls,0,ls,2,k,2,k,0,k,1,32,2,0,1,2,ls,0,ls,1,k,0,ls,2,10,2,k,2,12,2,k,1,选10,90,17,21,05,44,10,12,56,32,29,(11),lastKey=10, 置换 (12),lastKey=12,k,1,置,k,2, 选择12 虚段, 选择29,29,12,2,2,29,2,32,2,0,1,ls,1,ls,0,ls,2,k,2,k,0,k,1,32,2,0,1,2,ls,0,ls,1,k,0,ls,2,29,2,k,2,12,3,k,1,选29,选12,虚段,91,17,21,05,44,10,12,56,32,29,(13),lastKey=29,k,2,置 (14),lastKey=32,k,0,置,虚段, 选择32 虚段, 本段结束,12,3,2,29,3,32,2,1,0,ls,1,ls,0,ls,2,k,2,k,0,k,1,32,3,0,2,1,ls,0,ls,1,k,0,ls,2,29,3,k,2,12,3,k,1,选32,虚段,虚段,虚段,虚段,虚段,92,(15) 输出段结束标志,结束,12,3,2,29,3,32,3,0,1,ls,1,ls,0,ls,2,k,2,k,0,k,1,段号,超出,当输入的记录序列已经按排序码大小排好序时，只生成一个初始归并段。,在一般情况下，若输入文件有,n,个记录，生成初始归并段的时间开销是