第11章外部排序 共62页

磁盘文件的归并排序
个缓冲区。 若把内存区域等份地分为 ３个缓冲区。其中的两个为输缓 冲区，一个为输出缓冲区， 冲区，一个为输出缓冲区，可以在内存中利用简单 ２归并 路归并。 函数 ｍｅｒｇｅ（ ）实现 ２路归并。 首先， 首先，从参加归并排序的两个输入归并段 Ｒ１和 Ｒ２中分 别读入一块，放在输入缓冲区１和输入缓冲区２ 别读入一块，放在输入缓冲区１和输入缓冲区２中。然后 路归并， 在存中进行 ２路归并，归并结果顺序存放到输出缓冲区中 。 当输出缓冲区装满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 无关，选择树很好 无关，

第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等等。 、 等等。 、 等等

四、建立败者树的算法描述如下: 建立败者树的算法描述如下
void CreateLoserTree ( LoserTree &ls ) // 已知 已知b[0]到b[k-1]为完全二叉树 的叶子结点存有 个关键字 为完全二叉树ls的叶子结点存有 个关键字, 到 为完全二叉树 的叶子结点存有k个关键字 沿从叶结点到根的k条路径将 调整为败者树 沿从叶结点到根的 条路径将ls调整为败者树 条路径将 调整为败者树. { b[k].key = MINKEY; //设MINKEY为关键字最小值 为关键字最小值. 设 为关键字最小值 for ( i=0; i < k; ++i ) ls[i]=k; //设置 中“败者”的初值 设置ls中 败者”的初值. 设置 for ( i=k-1; k >= 0; - -i ) Adjust(ls,i); //依次从 依次从b[k-1],b[k-2],…,b[0]出发调整败者 出发调整败者. 依次从 出发调整败者 } // CreateLoserTree
10
11.3
多路平衡归并的实现
一、多路平衡归并的性质： 多路平衡归并的性质： •分析 m 个初始归并段，外排时采用 k−路归并，则归 分析: 个初始归并段， 分析 −路归并， 趟数减少， 并趟数为 logkm , K 大，趟数减少，读写记录的总 数将减少。 会使内部归并时间t 增大?。 数将减少。但 K 大，会使内部归并时间 mg增大 。
• 盘文件的读写时间：T i/o = tseck + tla + n×twm 盘文件的读写时间： × tseck (0.1秒) ：找道时间； tla (<25豪秒 ：等待时间 找道时间； 豪秒) 秒 豪秒 个字符/秒 ：传输时间/ 字符， 字符数 twm (105个字符 秒)：传输时间 字符，n 字符数。