11 第11章 文件与外部排序

磁盘文件的归并排序
个缓冲区。 若把内存区域等份地分为 ３个缓冲区。其中的两个为输缓 冲区，一个为输出缓冲区， 冲区，一个为输出缓冲区，可以在内存中利用简单 ２归并 路归并。 函数 ｍｅｒｇｅ（ ）实现 ２路归并。 首先， 首先，从参加归并排序的两个输入归并段 Ｒ１和 Ｒ２中分 别读入一块，放在输入缓冲区１和输入缓冲区２ 别读入一块，放在输入缓冲区１和输入缓冲区２中。然后 路归并， 在存中进行 ２路归并，归并结果顺序存放到输出缓冲区中 。 当输出缓冲区装满2５０个记录时，就输出到磁盘。 当输出缓冲区装满 ５０个记录时，就输出到磁盘。 ５０个记录时 如果归并期间某个输入缓冲区空了， 如果归并期间某个输入缓冲区空了，就立即向该缓冲区继 续装入所对应归并段的一块记录信息， 续装入所对应归并段的一块记录信息，使之于另一个输入 缓区的剩余记录归并，直到Ｒ 归并为Ｒ１２、Ｒ 缓区的剩余记录归并，直到Ｒ１和Ｒ２归并为Ｒ１２、Ｒ 归并Ｒ３４、Ｒ 、Ｒ５ 归并为Ｒ５６为止 为止。 ３和Ｒ４归并Ｒ３４、Ｒ５和Ｒ６归并为Ｒ５６为止。 再把Ｒ１２和 ３４归并为Ｒ１２３４，最后把Ｒ 再把Ｒ１２和Ｒ３４归并为Ｒ１２３４，最后把Ｒ１２３ 归并为 ５６归并为 １２３４５６。 归并为Ｒ ４和Ｒ５６归并为Ｒ１２３４５６。
K 路平衡归并与败者树
选择树 或 败者树 分析： 分析： 第一次建立选择树的比较所花时间为: 第一次建立选择树的比较所花时间为 O( K-1 ) = O ( K) 而后每次重新建造选择树所需时间为： 而后每次重新建造选择树所需时间为： O( log2K) n 个记录处理时间为初始建立选择树的 次重建选择树的时间： 时间加上 n-1 次重建选择树的时间： O((n-1) log2K)+O(K) = O ( n log2K ) 这就是k路归并一遍所需的 这就是 路归并一遍所需的CPU处理时间 路归并一遍所需的 处理时间 。归并遍数为 logkm，总时间为： ，总时间为： O(n log2K logKm) = O(n log2m) K 路归并 CPU 时间与 K 无关，选择树很好 无关，

▪ ta 延迟时间：读写头到达相应的物理块的起始 位置的时间；
▪ tw 读/写一个字符的时间；
▪ n 字符数。
由于磁带是顺序存取设备，在读一个记录时，必 须先顺序检索，直到所需信息通过读写头时才能 得到。因此检索速度很慢。
磁带主要用于处理变化少、只进行顺序存取的大 量数据。
磁盘（disc）
▪ 磁盘存储器通常称为直接存取设备，或随机存 取设备，它访问外存上文件的任一记录的时间 几乎相同。
假设“数据块”的大小为200，即每一次访问外存可 以读/写200个记录。 则对于10,000个记录，处理一遍需访问外存100次(读 和写各50次)。 1)求得10个初始归并段需访问外存100次; 2)每进行一趟归并需访问外存100次; 3)总计访问外存 100 + 4 100 = 500次
▪外排总的时间还应包括内部排序所需时间和逐趟归 并时进行内部归并的时间
外部排序总时间=产生初始归并段的时间 m*tIS +外存信息读写时间 d*tIO +内部归并所需时间 s*utmg
R1’
R2’
R3’
R4’
R5’
R1’’
R2’’
R3’’
R1’’’
R3’’’
有序文件
假设进行2路归并(即两两归并)，则：
➢第一趟由10个归并段得到5个归并段; ➢第二趟由 5 个归并段得到3个归并段; ➢第三趟由 3 个归并段得到2个归并段; ➢最后一趟归并得到整个记录的有序序列。
▪分析上述外排过程中访问外存(对外存进行读/写)的次数：
▪ 任一时刻，所有记录盘面的读写磁头停留在各 个记录盘面的半径相同的磁道上。运行时，由 于盘面做高速旋转，磁头所在的磁道上的数据 相继在磁头下，从而可以读写数据。

第11章外部排序
11.1 外存信息的存取 11.2 外部排序的方法 11.3 多路平衡归并的实现 11.4 置换-选择排序 11.5 最佳归并树
11.1 外存信息的存取
• 两种存储器:内存储器(主存)和外存储器(辅 存)。内存的信息可随机存取,且存取速度快, 但价格贵(?),容量小(?). 外存储器包括磁带和 磁盘(或磁鼓)．前者为顺序存取的设备,后者 为随机存取的设备.
• 外部排序:待排序记录的数量很大,以致内存一 次不能存纳全部记录,在排序过程中尚需对外 存进行访问的排序过程.
一．磁带信息的存取
• 磁带大多数有0.5英寸宽(1.27cm)，最长可达3600英 尺(1097.56m).
两种基本操作
• 在0.5寸,记录9位或7位二进制(称为9道或7道带， 9 轨或7轨带)。
后的文件。
11.3 多路平衡归并的实现
11.4 置换-选择排序
• 在整个排序(得到所有初始归并段)的过程中， 选择最小(或最大)关键字和输入、输出交叉 或平行进行(边输入输出,边选择最小关键字)。
• 假设初始待排文件为输入文件F真，初始归 并段文件为输出文件FO，内存工作区勾wA， FO和wA的初始状它为空，井设内存工作wA 区的容量可容纳钟个记录．则置换-选择排序 的操作过程为：
二．磁盘信息的存取
• 磁盘是一种直接存取的存储设备； • 它特征是存取时间变化； • 可以直接存取任何字符组； • 容量大、速度快，存取速度比磁带快得多； • 磁盘是一个扁平的圆盘(与电唱机的唱片类似)，盘
面上有许多饰为磁道的圆圈；
• 信息记载在磁道上。由于磁道的圆圈为许多同心 圆．所以可以直接存取。磁盘可以是单片的．也可 以由若干盘片组成盎组。每一片上有两个面。以6 片盘组为例．由于最顶上和最低下盘片的外侧面不 存信息．所以总共只有10个面可用来保存信

外排所需总的时间为： 外排所需总的时间为：
m*tIS + d*tIO + S*u*tmg = 10*tIS + 500*tIO + 4*10000*tmg
示例： 示例：
• 设有一个包含4500个对象的输入文件。现 设有一个包含4500个对象的输入文件。 个对象的输入文件 用一台其内存至多可容纳750个对象 内存至多可容纳 个对象的计 用一台其内存至多可容纳750个对象的计 算机对该文件进行排序。输入文件放在磁 算机对该文件进行排序。 盘上，磁盘每个页块可容纳250个对象 每个页块可容纳 个对象， 盘上，磁盘每个页块可容纳250个对象， 250＝ 这样全部对象可存储在 4500 / 250＝18 个 页块中。输出文件也放在磁盘上，用以存 页块中。输出文件也放在磁盘上， 放归并结果。 放归并结果。
一、外排序的基本过程
• 当对象以文件形式存放于磁盘上的时候，通常 当对象以文件形式存放于磁盘上的时候， 是按物理块存储的。 是按物理块存储的。 • 物理块也叫做页块，是磁盘存取的基本单位。 物理块也叫做页块，是磁盘存取的基本单位。
• 每个页块可以存放几个对象。操作系统按 每个页块可以存放几个对象。 页块对磁盘上的信息进行读写。 页块对磁盘上的信息进行读写。 • 本节所指的磁盘是由若干片磁盘组成的磁 盘组， 盘组，各个盘片安装在同一主轴上高速旋 转。各个盘面上半径相同的磁道构成了柱 各盘面设置一个读写磁头， 面。各盘面设置一个读写磁头，它们装在 同一动臂上， 同一动臂上，可以径向从一个柱面移到另 一个柱面上。 一个柱面上。
硬盘简介 磁盘的主要技术指标 柱面：多个盘片的同一磁道。 柱面：多个盘片的同一磁道。 目前常见的硬盘容量有 6.2GB、10GB、20GB、 、 、 、 40GB、60GB、80GB等等。 、 等等。 、 等等