11-5
1 外存信息的存取
• 磁盘信息的存取 磁盘是一种直接存取的存储设备(DASD）。 • 页块的读写时间：TI/O = tseek + tlatency + n twm
– tseek：寻道时间 – tlatency：等待时间 – twm：传输时间
11-6
2 外部排序的方法
• 外部排序基本上由两个相对独立的阶段组成：
11-13
3 多路平衡归并的实现
• 胜者树及其使用 胜者进入下一轮, 快地挑出亚军、第三名 …… 。
IS
11-10
2 外部排序的方法
• d和“归并过程”的关系： 若对上例进行5路平衡归并： R1 R2 R3 R4 R5 R1’ R6 R7 R8 R9 R10 R2’
有序文件 仅需两趟归并, 总的读/写次数便减少为： 2x100+100=300, 比2路归并减少了200次的读/写。对 同一文件, 进行外排序时所需读/写外存的次数和归并 的趟数s成正比。一般情况下, 对m个初始归并段进行k 路平衡归并时, 归并的趟数s=floor(logkm). 可见：若能增加k或减少m便能减少s, 因此减少d.
floor(logkm)(k-1)(n-1)tmg = floor(log2m/log2k)(k-1)(n-1)tmg
• 由于(k-1)/log2k 随 k 的增长而增长, 这将抵消由于增大 k而减少外存信息读写时间所得效益。
11-12
3 多路平衡归并的实现
• 在进行k路归并时利用“败者树(Tree of Loser)”, 则可使在k个记录中选出关键字 最小的记录时仅需进行floor(log2k)次比较, 从而使总的归并时间变为： floor(log2m)(n-1)tmg 与k无关, 不再随k的增长而增长。
11-11
3 多路平衡归并的实现
• 对于2路归并, 令两个归并段上有u个记录, 每得到 归并后的一个记录, 仅需一次比较即可, 因此得到 含u个记录的归并段需进行u-1次比较。 • 对于k路归并, 令u个记录分布在k个归并段上, 显 然, 归并后的第一个记录应是k个归并段中关键字 最小的记录, 这需要进行k-1次比较, 得到u个记录 的归并段, 共需(u-1)(k-1)次比较。由此, 对n个记录的 文件进行外排序时, 在内部归并过程中进行的总的 比较次数为s(k-1)(n-1)。假设所得初始归并段为m个, 则 归并过程中进行比较的总的时间为：
11-7
2 外部排序的方法
• 例：一文件含10000记录, 通过10次内部排序得到10个初 始归并段R1…R10, 其中每一段都含有1000个记录。 然后作两两归并：
R1 R2 R3 R4 R5 R6 R7 R8 R9 R10
R1’
R2’
R3’
R4’
R5’
R3’’ R2’’’
R1’’ R1’’’
R2’’ 有序文件
记录 1 记录 2 记录 3
11-4
1 外存信息的存取
• 在磁带上读写一块信息所需的时间由两部分组 成： TI/O = ta + n tw
– ta为延迟时间, 即读/写头到达传输信息所在物理 快起始位置所需时间； – tw为传输一个字符的时间。
显然, 延迟时间和信息在磁带上的位置、 当前读/写头所在的位置有关。 所以磁带便宜、可反复使用、是一种顺序 存取设备, 但查找费时、速度慢（尤其是查找 末端记录时）。
数据结构
外部排序
本章内容 1 外存信息的存取 2 外部排序的方法 3 多路平衡归并的实现 4 置换-选择排序
5 最佳归并树
1 外存信息的存取
• 常用的外存储器分类：
– 顺序存取的设备（如磁带）； – 随机存取的设备（如磁盘）。
常用的外存储器是磁表面存储器, 信息记 录在一薄层磁性材料的表面上, 这层材料附着 于载体表面, 随着载体作高速旋转或直线运动, 在运动过程中用磁头进行读或写。 外存信息的存取特点, 决定了外部排序的 策略选择。
11-3
1 外存信息的存取
• 磁带信息的存取 磁带存储器的工作原理和磁带录音机一样, 不 同之处在于它存储的是数字信息而不是模拟信息。 磁带上的信息在横向分布、纵向分布以及首尾 标志等都一定的格式。
– 以1/2英寸九道的磁带为例, 每一横排就可表示一个 字符（8位+1个校验位）。 – 纵向按区进行存储, 区的长度不固定, 但有一个范围, 例如2到4096字节, 相邻区之间有一定长度的间隔 （IBG, Inter Block Gap）, 作为磁带起停之用。
11-9
2 外部排序的方法
• 外部排序所需总的时间 = 内部排序（产生初始归并段）所需的时间(m × t ) + 外存信息读写的时间(d × tIO) +内部归并所需的时间(s × utmg) • 其中： tIS 是为得到一个初始归并段进行内部排序所需时间的均值； tIO 是进行一次外存读/写时间的均值； utmg 是对u个记录进行内部归并所需时间； m 为经过内部排序之后得到的初始归并段的个数； s 为归并的趟数； d 为总的读/写次数。 • 于是上例进行外排序所需总的时间为：10 tIS + 500 tIO + 4x10000 tmg 显然tIO较tmg要大的多, 因此提高外排序的效率应主要着眼于减 少外存信息读写的次数d。
– 首先, 按可用内存大小, 将外存上含n个记录的文 件分成若干长度为l的子文件或段(segment), 依次 读入内存并利用有效的内部排序方法对它们进行排 序, 并将排序后得到的有序子文件重新写入外存, 通常称这些有序子文件为归并段或顺串(run)； – 然后, 对这些归并段进行逐躺归并, 使归并段（有 序的子文件）逐渐由小至大, 直到得到整个有序文 件为止。
• 由10个初始归并段到一个有序文件, 共进行了4趟归并, 每一趟都从m个归并段得到ceil(m/2)个归并段。这种归 并方法称为2-路平衡归并。
11-8
2 外部排序的方法
• 外存上信息的读/写是以“物理块”为单位 进行的, 假设每个物理块可以容纳200个记 录, 则每一趟归并需进行50次“读”和50 次“写”, 4趟归并加上内部排序时所需进 行的读/写使得在外排序中总共需进行500 次读/写。