第十章外部排序.ppt

《第十章外部排序.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第十章外部排序外存信息的存取外部排序的基本方法—归并排序法多路平衡归并置换-选择排序外部排序的应用对象保存在外存储器上的信息量很大的数据记录文件。外排序与内排序的差别内部排序充分利用内存可以随机存取的特点，如希尔排序中，相隔di的记录关键字可作比较；堆排序中，完全二叉树中父R[i]与子R[2i]，R[2i+1]可比快速排序中，需正向和逆向访问记录序列外存信息的定位和存取受其物理特性的限制外部排序的实现手段在排序过程中，进行多次内外存之间的数据交换外部排序的特点外排序基本方法：归并排序[步骤]1、生成顺串生成若干初始归并串/顺串(文件预处理)把含有n个记录的文件，按内存缓

2、冲区大小分成若干长度为L的子文件（段）；分别调入内存用有效的内排序方法排序后送回外存；2、合并顺串多路合并对初始归并串逐趟合并，直至最后在外存上得到整个有序文件为止[例]某文件共10000个记录，设每个物理块可以容纳200个记录，内存缓冲区可以容纳5个物理块，每段含1000个记录。1)经过10次内排序后得到10个初始归并段R1~R102)采用两路归并，需四趟可以得到排好序的文件R1R2R3R4R5R6R7R8R9R102000200020002000200040004000200080002000内排序：10tIS10000I/O操作：100tIO(排序)+(100+8

3、0+80+100)tIO(归并)=460tIO归并：(10000+8000+8000+10000)tmg=46000tmg外部排序分析外部排序所需总时间T=m*tIs+d*tI/O+s*ntmg其中tIs是构造一个初始归并段所需内部排序的平均时间；m为初始归并段的个数；tI/O是进行一次外存读/写的平均时间；d为总的读/写次数;tmg是对一个记录进行内部归并所需时间；n为记录个数；s为归并的趟数；提高外排序效率的途径扩大初始归并段长度，从而减少初始归并段个数m进行多路(k路)归并,减少合并趟数s，以减少I/O次数s=logkm11.3多路归并排序k-路归并，n个记录

4、分布在k个归并段上，从k个记录中选出一个最小记录需进行k－1次比较，一趟归并要得到全部n个记录共需进行(n－1)(k－1)次比较。此k-路归并排序的内部归并过程中进行的总的比较次数为s(n－1)(k－1)。故有：k，s，可减少I/O次数；k，c=(k-1)，归并效率——利用“败者树”选关键字最小的记录,此时从k个记录中选出一个最小记录需进行log2k次比较,则C=log2m(n-1)，与k无关败者树败者树是一颗完全二叉树叶结点存放参加比较的记录非叶结点记忆其子女结点中的败者根结点之上的结点存放最后的胜者胜者树(树形选择排序)6868989689091589

5、01092068121092015812109206812901092015812901422241516179214222425161792263830255018972638305018977路合并胜者树重构后的胜者树重构胜者树时，从根结点至新补入记录的叶结点的路径上的所有结点都必须更新。实现5-路归并的败者树029201031461525∞123748∞101516∞91820∞202240∞126Ls[4]Ls[2]Ls[1]Ls[3]Ls[0]b3b4b0b1b242920101031525∞123748∞101516∞91820∞

6、202240∞1215Ls[4]Ls[2]Ls[1]Ls[3]Ls[0]b3b4b0b1b2败者树52204013690136901092068121092015812109206812901092015812901422241516119214222425161192263830255018972638305018977路合并败者树重构后的败者树败者树的特点：记录败者，胜者参加下一轮比赛败者树的优点：重构时修改结点较少01234564ls[0]5ls[0]12345607777777900109206812123456[k-路归并对内存的要

7、求]至少要有k个输入缓冲区和一个输出缓冲区建败者树的过程7-1初始化败者树调整b[6]6调整b[5]5调整b[4]4调整b[3]34调整b[2]2调整b[1]124调整b[0]054建败者树的过程4520136900109206812123456调整败者树的方法:将新补充的结点与其双亲结点比较,败者留在该双亲结点,胜者继续向上直至树根的双亲以在b[4]补充15为例154与3比较4与2比较42与5比较25调整败者树的方法[数据结构](败者树为完全二叉树)主：b[0..k]b[0..k-1]——k个叶结点，存放k个输入归并段中当前参加归并的记