外部排序数据结构.ppt
外存信息的存取外部排序的方法多路平衡归并p外存储器类型：n1、顺序存取的设备（磁带）、顺序存取的设备（磁带）n2、随机存取的设备（磁盘）、随机存取的设备（磁盘）磁带工作原理：p将磁带盘放在磁带机上，驱动器控制磁带盘转动，带动磁带向前移动，通过读/写头就可以向读出或写入信息。磁带信息存贮p可记下各种文字信息和二进制信息，按字符组存放，而不是按字符存放。读写的启动停止：p磁带不是连续运转的设备，由于读/写需要稳定时进行，因此当启动/停止时，需要一个加速/减速的过程，这个过程磁带不写入任何内容，因而相邻的两个字符组之间要留一个空白，叫做间隙p所需时间由两部分组成：nTi/o = ta+ntwnta为延迟时间，即读写头到传输信息所在的物理块的为延迟时间，即读写头到传输信息所在的物理块的起始位置所需的时间起始位置所需的时间ntw为传输一个一个字符所需的时间为传输一个一个字符所需的时间n特点：特点：p查找速度慢，检索和修改信息不方便，主要用于处理变化小，只进行顺序存取的大量数据p磁盘信息的存取磁盘是一种直接存取的存储设备p磁盘读写块所需的时间组成：nTi/o = tseek + ta + n * twm tseek：读写头定位的时间 ta：等待信息快的初始位置转到读写头下的时间 twm：传输时间外部排序的应用对象保存在外存储器上的信息量很大的数据记录文件。外排序与内排序的差别p内部排序充分利用内存可以随机存取的特点，如n希尔排序中，相隔di的记录关键字可作比较；n堆排序中，完全二叉树中父Ri与子R2i，R2i+1可比n快速排序中，需正向和逆向访问记录序列p外存信息的定位和存取受其物理特性的限制外部排序的实现手段在排序过程中，进行多次内外存之间的数据交换p由两个独立的阶段组成n将外存含n个记录的文件分成若干长度为l的子文件或段，依次读入内存并用内部排序方法排序，将排序后的有序子文件重新写入外存，称为归并段或顺串n对这些归并段进行逐趟归并，（有序子文件）由小变大，直到获得整个有序文件步骤步骤p生成若干初始归并串/顺串(文件预处理)n把含有把含有n个记录的文件，按内存缓冲区大小分成若干长度为个记录的文件，按内存缓冲区大小分成若干长度为L的子文件（段）；的子文件（段）；n分别调入内存用有效的内排序方法排序后送回外存；分别调入内存用有效的内排序方法排序后送回外存；p 多路合并n对初始归并串逐趟合并，直至最后在外存上得到整个有序文件为止对初始归并串逐趟合并，直至最后在外存上得到整个有序文件为止例例某文件共10000个记录，设每个物理块可以容纳200个记录，内存缓冲区可以容纳5个物理块 1)经过10次内排序后得到10个初始归并段R1R10 2)采用两路归并，需四趟可以得到排好序的文件 R1 R2 R3 R4 R5 R6 R7 R8 R9 R10 2000 2000 2000 2000 2000 4000 4000 8000 10000p外存上的信息的读/写以“物理块”为单位，假设每个物理块可容纳200个记录，则每一趟归并所需进行50次“读”和50次“写”，4趟归并并加上内部排序所需进行的读写使得外排序总共需进行500读/写p外部排序所需的总的时间= 内部排序所需的时间（内部排序所需的时间（m*tis） + 外存信息读写的时间（外存信息读写的时间（d*tio） + 内部归并所需的时间（内部归并所需的时间（s*utmg）tis:：得到一个厨师归并段进行内部排序所需时间：得到一个厨师归并段进行内部排序所需时间tio：进行一次外存读：进行一次外存读/写所需时间写所需时间utmg：对：对u个记录进行内部归并所需的时间个记录进行内部归并所需的时间m：经过内部排序后得到初始归并段的个数：经过内部排序后得到初始归并段的个数s：为归并的趟数：为归并的趟数d：为总的读：为总的读/写次数写次数因此：上例进行外派的总的时间为：因此：上例进行外派的总的时间为：10tis + 500*tio + 4 * 10000tmg，由于，由于tio比比tmg大的多，因此提高大的多，因此提高外排序的效率要降低读外排序的效率要降低读/写次数写次数d p因为d和归并的趟数s成正比，而s又与m成正比，因此有： 1、扩大初始归并段长度，从而减少初始归并段个数m 2、进行多路(k路)归并减少合并趟数减少合并趟数s，以减少，以减少I/O次数次数s = logkm通过简单比较进行通过简单比较进行K路归并存在的问题路归并存在的问题 设记录总数为n，初始归并段的个数为m， 从k个记录中选择一个关键字最小的记录时的比较次数为c则s趟内部归并总的比较次数为： C=sc(n-1)= logkm c (n-1)= log2m/ log2k c (n-1) k，s，可减少I/O次数； k， c=(k-1) ，归并效率解决矛盾的方法解决矛盾的方法 利用“败者树”选关键字最小的记录 此时c= log2k则 C= log2m(n-1) ，与k无关矛盾1 2 k胜者树胜者树(树形选择排序树形选择排序) 6 8 6 8 9 8 9 6 8 90 9 15 8 90 10 9 20 6 8 12 10 9 20 15 8 12 10 9 20 6 8 12 90 10 9 20 15 8 12 90 14 22 24 15 16 17 92 14 22 24 25 16 17 92 26 38 30 25 50 18 97 26 38 30 50 18 97 7路合并胜者树路合并胜者树 重构后的胜者树重构后的胜者树 重构胜者树时，从根结点至新补入记录的叶结点的重构胜者树时，从根结点至新补入记录的叶结点的路径上的所有结点都必须更新。路径上的所有结点都必须更新。 5 2 2 0 4 0 1 3 6 90 1 3 6 90 10 9 20 6 8 12 10 9 20 15 8 12 10 9 20 6 8 12 90 10 9 20 15 8 12 90 14 22 24 15 16 11 92 14 22 24 25 16 11 92 26 38 30 25 50 18 97 26 38 30 50 18 97 7路合并败者树 重构后的败者树败者树的特点：记录败者，胜者参加下一轮比赛 败者树的优点：重构时修改结点较少01 2 3 4 5 64ls05ls01 2 3 4 5 60 4 5 2 0 1 3 6 90 0 10 9 20 6 8 12 1 2 3 4 5 6调整败者树的方法: 将新补充的结点与其双亲结点比较, 败者留在该双亲结点,胜者继续向上直至树根的双亲以在b4补充15为例154与3比较4与2比较42与5比较25 7 7 7 7 7 7 7 90 0 10 9 20 6 8 12 1 2 3 4 5 6k-路归并对内存的要求路归并对内存的要求 至少要有k个输入缓冲区和一个输出缓冲区建败者树的过程7 -1初始化败者树调整b66调整b55调整b44调整b334调整b22调整b1124调整b0054数据结构数据结构 (依据：败者树为完全二叉树)p主：b0. k b0. k-1k个叶结点 ，存放k个输入归并段中当前 参加归并的记录（缓冲区） bk虚拟记录，该关键字取可能的最小值minkeyp辅：ls0. k-1 不含叶结点的败者树 存放最后胜出的编号（ls0）以及所记录的败者编号处理步骤处理步骤p建败者树ls0. k-1p重复下列操作直至k路归并完毕n将将bls0写至输出归并段写至输出归并段n补充记录补充记录(某归并段变空时某归并段变空时,补补 )，调整败者树，调整败者树void CreateLoserTree() bk = MINKEY; for (i = 0; i = 0; i+) Adjust(i);void Adjust(int s) for (t = (s + k) / 2; t 0; t /= 2) if (bs blst) s lst; ls0 = s;void K_Merge() for (i = 0; i k; i+) input(i); /* 第i路输入一个元素到bi */ CreateLoserTree(ls); while (bls0 != MAXKEY) q = ls0; output(bq); input(q); Adjust(q);
