文档介绍：该【第10章外部排序 】是由【孔乙己】上传分享，文档一共【28】页，该文档可以免费在线阅读，需要了解更多关于【第10章外部排序 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。第10章外部排序
OFFACFS
Inner推荐
:假设磁盘上存有一文件,共有3600个记录(A1,A2,…,A3600),页块长为200个记录,供排序使用的缓冲区可提供容纳600个记录的空间,现要对该文件进行排序,排序过程可按如下步骤进行:
第一步:每次将三个页块(600个记录)由外存读到内存,进行内排序,整个文件共得到6个初始顺串R1~R6(每一个顺串占三个页块),然后把它们写回到磁盘上去。。
第二步:将供内排序使用的内存缓冲区分为三块相等的部分(即每块可容纳200个记录),其中两块作为输入缓冲区,一块作为输出缓冲区,然后对各顺串进行两路归并。。
一般说来,如果初始顺串有m个,[log2m]+1层,要对数据进行[log2m]遍扫描。采用多路归并可以减少扫描遍数,如图所示。
1234 56789101**********
 
123456789101**********
在k路归并中,为了确定下一个要输出的记录,就需要在k个记录中寻找关键字值最小的那个记录,这要比2路归并复杂些。如果逐个比较每个顺串的待选记录,从而选出一个关键字值最小的记录,则每选取一个记录需要进行k-1次比较。为了减少这个代价,我们可采用下面介绍的选择树的方法来实现k路归并。
选择树是一种完全二叉树,下图显示了8路归并的选择树,其中叶结点为各顺串在归并过程中的当前记录(图中标出了它们各自的关键字值),其它每个结点都代表其两个子结点中(关键字值)较小的一个。因此根结点是树中的最小结点,即为下一个要输出的记录结点。这种选择树的构造可比作一种淘汰制的体育比赛,其中获胜者便是那个具有较小关键字值的记录。
在非叶结点中,可以只存关键字值及指向相应记录的指针,而不必存放整个记录内容。由于非叶结点总是代表优胜者,所以可以把这种树称为胜方树。
(胜方树)
由上述过程可见,要选取关键字值最小的记录,只有第一个需要进行m-1次比较(建立胜方树),此后每个只要进行[log2m]次比较即可,这是由于树中保持了以前的比较结果。
胜方树的缺点:在选取一个记录之后重构选择树的修改工作比较麻烦,既要查找兄弟结点,又要查找父结点。为了减少重构选择树的代价,可以采用败方树的办法来简化重构的过程。
败方树:就是在比赛树(选择树)中,每个非叶结点均存放其两个子结点中的败方。
建立过程是:从叶结点开始分别对每两个兄弟结点进行比较,败者(较大的关键字值)存放在父结点中,而胜者继续参加下一轮的比较,最终结果是每个“选手”都停在自己失败的“比赛场”上。在根结点之上有一个附加的结点,存放全局优胜者。
在败方树中,当输出全局优胜者记录之后,对树的修改比胜方树容易一些。修改过程如下:将新进入树的叶结点与父结点进行比较,大的存放在父结点,小的与上一级父结点再进行比较,此过程不断进行,直至到根,最后把新的全局优胜者存放到附加的结点。
采用多路归并可以减少对数据的扫描遍数从而减少了输入/输出量。但也应该看到,若归并的路数k增大时,缓冲区就要设置得比较大。
其生成过程见下图。
输入文件
10,9,20,6,8,12,90,17,14,22,7,24,15,16,11,100,13,18,26,38,30,25,50,28,110,21,40,19,…
(a)输入文件,每个记录只列出其关键字值
初始顺串1:6,8,9,10,12,14,15,16,
17,20,22,24,26,30,38,
50,90,100,110
初始顺串2:7,11,13,18,21,25,28,40
(b)生成的初始顺串
(c)包含8个记录的败方树,并列出了新进入败方树的各记录的结点位置及进入的次序,用符号表示该记录不属于当前的初始顺川。
磁带排序过程基本上与磁盘排序过程相同。首先对待排序文件的各段进行内排序,产生所有的初始顺串,再把它们写回到磁带上,然后对这些顺串进行反复归并,直至成为一个顺串(即为有序文件)为止。
磁带排序需充分考虑顺串的分布情况,因为磁带是顺序存取的,排序过程中寻找或等待的时间较长,所以各顺串分布在不同磁带和同一磁带的不同位置对排序效率影响极大。