文档介绍：第12章外排序
外排序概述
磁盘排序
磁带排序
本章小结
外排序概述
文件存储在外存上,因此外排序方法与各种外存设备的特征有关,外存设备大体上可分为两类,一类是顺序存取设备,例如磁带,另一类是直接存取设备,例如磁盘,其结构如下图所示。
外排序的基本方法是归并排序法。它分为以下两个步骤:
(1) 生成若干初始归并段(顺串),这一过程也称为文件预处理:
①把含有n个记录的文件,按内存大小分成若干长度为L的子文件(段);
②分别将各子文件(段)调入内存,采用有效的内排序方法排序后送回外存。
(2) 多路归并:对这些初始归并段进行多遍归并,使得有序的归并段逐渐扩大,最后在外存上形成整个文件的单一归并段,也就完成了这个文件的外排序。
磁盘排序
磁盘排序过程
磁盘是直接存取设备,读/写一个数据块的时间与当前读/写头所处的位置关系不大。
我们通过一个例子来说明磁盘排序的过程。设有一个文件,内含4500个记录:A1,A2,…,A4500,现在要对该文件进行排序,但可占用的内存空间至多只能对750个记录进行排序。输入文件(被排序的文件)放在磁盘上,页块长为250个记录。排序过程可如下进行:
6个归并段的归并过程
多路平衡归并
上图所示的归并过程基本上是2路平衡归并的算法。一般说来,如果初始归并段有m个,那么这样的归并树就有log2m+1层,要对数据进行log2m遍扫描。采用k路平衡归并时,则相应的归并树有logkm+1层,要对数据进行logkm遍扫描。
做内部归并时,在k个记录中选择最小者,需要顺序比较k-1次。每趟归并u个记录需要做(u-1)*(k-1)次比较,s趟归并总共需要的比较次数为:
s*(u-1)*(k-1)=logkm*(u-1)*(k-1)
=log2m*(u-1)* (k-1)/log2k
其中,log2m*(u-1)在初始归并段个数m与记录个数u一定时是常量,而(k-1)/log2k在k增大时趋于无穷大。因此,增大归并路数k,会使内部归并的时间增大。若k增大到一定的程度,就会抵消掉由于减少读写磁盘次数而赢得的时间。
下面讨论利用败者树实现多路平衡归并。
败者树是一棵有k个叶结点的完全二叉树,叶子结点存储记录,非叶结点可由关键字和它对应的记录地址构成,为讨论方便起见,设非叶结点的结构为:
关键字,输入有序段的路号
对k个输入有序段进行k路平衡归并的方法如下:
(1) 取每个输入有序段的第一个记录作为败者树的叶子结点,建立初始败者树:两两叶结点进行比较,在双亲结点中记录比赛的败者(关键字较大者),而让胜者去参加更高一层的比赛,如此在根结点之上胜出的“冠军”是关键字最小者。
(2) 胜出的记录写至输出归并段,在对应的叶结点处,补充其输入有序段的下一个记录,若该有序段变空,则补充一个大关键字(比所有记录关键字都大,设为kmax)的虚记录。
(3) 调整败者树,选择新的关键字最小的记录:从补充记录的叶结点向上和双亲结点的关键字比较,败者留在该双亲结点,胜者继续向上,直至树根的双亲。
(4) 若胜出的记录关键字等于kmax,则归并结束;否则转(2)继续。
例如,设有5个初始归并段,它们中各记录的关键字分别是:
R1:{17,21,∞}
R2:{5,44,∞}
R3:{10,12,∞}
R4:{29,32,∞}
R5:{15,56,∞}
其中,∞是段结束标志。利用败者树进行5路平衡归并排序的过程如下图所示。