数据结构第十一部分外部排序.ppt

该【数据结构第十一部分外部排序 】是由【fanluqian】上传分享，文档一共【35】页，该文档可以免费在线阅读，需要了解更多关于【数据结构第十一部分外部排序 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。数据结构第十一章 外部排序
#2022
本章内容
1 外存信息的存取
2 外部排序的方法
3 多路平衡归并的实现
4 置换-选择排序
5 最佳归并树
11-2
外存信息的存取
常用的外存储器分类：
顺序存取的设备（如磁带）；
随机存取的设备（如磁盘）。
常用的外存储器是磁表面存储器, 信息记录在一薄层磁性材料的表面上, 这层材料附着于载体表面, 随着载体作高速旋转或直线运动, 在运动过程中用磁头进行读或写。
外存信息的存取特点, 决定了外部排序的策略选择。
11-3
外存信息的存取
记录 1
记录 3
记录 2
11-4
磁带信息的存取
磁带存储器的工作原理和磁带录音机一样, 不同之处在于它存储的是数字信息而不是模拟信息。
磁带上的信息在横向分布、纵向分布以及首尾标志等都一定的格式。
以1/2英寸九道的磁带为例, 每一横排就可表示一个字符（8位+1个校验位）。
纵向按区进行存储, 区的长度不固定, 但有一个范围, 例如2到4096字节, 相邻区之间有一定长度的间隔（IBG, Inter Block Gap）, 作为磁带起停之用。
外存信息的存取
在磁带上读写一块信息所需的时间由两部分组成：
TI/O = ta + n tw
ta为延迟时间, 即读/写头到达传输信息所在物理快起始位置所需时间；
tw为传输一个字符的时间。
显然, 延迟时间和信息在磁带上的位置、当前读/写头所在的位置有关。
所以磁带便宜、可反复使用、是一种顺序存取设备, 但查找费时、速度慢（尤其是查找末端记录时）。
11-5
外存信息的存取
磁盘信息的存取
磁盘是一种直接存取的存储设备(DASD）。
页块的读写时间：TI/O = tseek + tlatency + n twm
tseek：寻道时间
tlatency：等待时间
twm：传输时间
11-6
外部排序的方法
外部排序基本上由两个相对独立的阶段组成：
首先, 按可用内存大小, 将外存上含n个记录的文件分成若干长度为l的子文件或段(segment), 依次读入内存并利用有效的内部排序方法对它们进行排序, 并将排序后得到的有序子文件重新写入外存, 通常称这些有序子文件为归并段或顺串(run)；
然后, 对这些归并段进行逐躺归并, 使归并段（有序的子文件）逐渐由小至大, 直到得到整个有序文件为止。
11-7
外部排序的方法
11-8
例：一文件含10000记录, 通过10次内部排序得到10个初始归并段R1…R10, 其中每一段都含有1000个记录。
然后作两两归并：
R1 R2 R3 R4 R5 R6 R7 R8 R9 R10
R1’ R2’ R3’ R4’ R5’
R1’’ R2’’ R3’’
R1’’’ R2’’’
有序文件
由10个初始归并段到一个有序文件, 共进行了4趟归并, 每一趟都从m个归并段得到ceil(m/2)个归并段。这种归并方法称为2-路平衡归并。
外部排序的方法
外存上信息的读/写是以“物理块”为单位进行的, 假设每个物理块可以容纳200个记录, 则每一趟归并需进行50次“读”和50次“写”, 4趟归并加上内部排序时所需进行的读/写使得在外排序中总共需进行500次读/写。
11-9
外部排序的方法
11-10
外部排序所需总的时间 = 内部排序（产生初始归并段）所需的时间(m × tIS) + 外存信息读写的时间(d × tIO) +内部归并所需的时间(s × utmg)
其中： tIS 是为得到一个初始归并段进行内部排序所需时间的均值； tIO 是进行一次外存读/写时间的均值； utmg 是对u个记录进行内部归并所需时间； m 为经过内部排序之后得到的初始归并段的个数； s 为归并的趟数； d 为总的读/写次数。
于是上例进行外排序所需总的时间为：10 tIS + 500 tIO + 4x10000 tmg显然tIO较tmg要大的多, 因此提高外排序的效率应主要着眼于减少外存信息读写的次数d。