5外部排序.ppt

外部排序 内容 外存信息的存取 外部排序的基本方法—归并排序法 多路平衡归并 置换-选择排序 外部排序的特点 外部排序的应用对象 保存在外存储器上的信息量很大的数据记录文件。 外排序与内排序的差别 内部排序充分利用内存可以随机存取的特点，如 希尔排序中，相隔di的记录关键字可作比较； 堆排序中，完全二叉树中父R[i]与子R[2i]，R[2i+1]可比 快速排序中，需正向和逆向访问记录序列 外存信息的定位和存取受其物理特性的限制 外部排序的实现手段 在排序过程中，进行多次内外存之间的数据交换 所谓内排序就是可以在内存中完成的排序。RAM的访问速度大约是磁盘的25万倍，我们当然希望如果可以的话都是内排来完成。但对于大数据集来说，内存是远远不够的，这时候就涉及到外排序的知识了。 外排序分为两个步骤：预处理和合并排序。即首先根据内存的大小，将有n个记录的磁盘文件分批读入内存，采用有效的内存排序方法进行排序，将其预处理为若干个有序的子文件，这些有序子文件就是初始顺串，然后采用合并的方法将这些初始顺串逐趟合并成一个有序文件。 外排序的时间消耗又由最初归并段的内排序时间，文件I/O时间和归并排序时间几部分组成，但影响排序时间的主要是文件I/O时间，因此应尽量采取一些手段，如减少文件扫描次数，有效利用缓冲区，使I/O和CPU处理尽可能重叠来提高外排序速度 在外存上进行排序的最通常的方法是合并排序。这种方法由两个相对独立的阶段组成：预处理和合并排序，即首先根据内存的大小，将有n个记录的磁盘文件分批读入内存，采用有效的排序方法进行排序，将其预处理为若干个有序的子文件，这些有序子文件被称为初始游程或顺串(run)，然后采用合并的方法将这些初始游程逐趟合并成一个有序文件。 对文件扫描一遍，意味着文件中的每个记录被读/写一次，即从磁盘上读入内存一次，在内存中完成合并后，再写到磁盘一次。由此看来，扫描的遍数对于合并排序的时间起着决定性作用。 预处理时先产生初始游程能提高外排序的效率，很重要的原因是减少了对磁盘数据的扫描遍数。 外排序基本方法：归并排序 [步骤] 生成若干初始归并串/顺串(文件预处理) 把含有n个记录的文件，按内存缓冲区大小分成若干长度为L的子文件（段）； 分别调入内存用有效的内排序方法排序后送回外存； 多路合并 对初始归并串逐趟合并，直至最后在外存上得到整个有序文件为止 [例]某文件共10000个记录，设每个物理块可以容纳200个记录，内存缓冲区可以容纳5个物理块 1)经过10次内排序后得到10个初始归并段R1~R10 2)采用两路归并，需四趟可以得到排好序的文件 R1 R2 R3 R4 R5 R6 R7 R8 R9 R10 2000 2000 2000 2000 2000 4000 4000 8000 10000 提高外排序效率的途径 扩大初始归并段长度，从而减少初始归并段个数m 进行多路(k路)归并 减少合并趟数s，以减少I/O次数 s = ?logkm? 多 路 归 并 多路平衡归并 [通过简单比较进行K路归并存在的问题] 设记录总数为n，初始归并段的个数为m， 从k个记录中选择一个关键字最小的记录时的比较次数为c 则s趟内部归并总的比较次数为： C=s?c(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无关 胜者树(树形选择排序) 6 8 6 8 9 8 9 6 8 90 9 15 8