第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个面可用来保存信
• 9道带每一横排就可表示一个字符(8位表示一个字符， 另一位作奇偶校验位)。
• 磁带上可记下各种文字信息或二进制信息，在磁带 上信息按字符组存放，而不是按字符存放，磁带上 信息的密度通常为每英寸800位或1600位或6250位 (即每英寸的二进制字符数)，移动速度是每秒200英 寸。
• 间隙IRG：磁带上相邻两组字符组(记录)之间空白 区。
置换-选择排序过程
(1)从FI输入w个记录到工作区WA。 (2)从WA中选出其中关键字取最小值的记录，记为MlNIMAX
记录 (3)将MINlMAX记录输出到FO中云。 (4)若FI不空，则从FI输入下一个记录到WA中。 (5)从WA中所有关键字比MINIMAX记录的关键字大的记录中
选出最小关键字记录，作为新的MINIMAX记录。 (6)重复(3)-(5)，直至在WA中选不出新的M1N]MAK记录为止，
由此得到一个初始归并段，输出一个归并段的结束标志到 FO中去。 (7)重复(2)-(6)．直至WA为空。由此得到全部初始归并段.
课件下载后可自由编辑，如有不理解 之处可根据本节内容进行提问
Thank you for coming and listening,you can ask questions according to this section and this courseware can be downloaded and edited freely
硬盘（磁盘）阵列
• 多个硬盘构成阵列； • 有一个管理程序，可以把阵列中的硬盘看成
一个硬盘，这样，可以拥有容量非常的大的 • 单个虚拟硬盘；保存文件可以在这个虚拟的
硬盘上进行，文件分布在不同的硬盘上。 • 阵列中如果一个硬盘有损坏，则影响整个虚
拟硬盘上的文件。
Hale Waihona Puke 11.2 外部排序的方法• 内存中排序，外部输出归并段（子文件）。 • 把归并段进行归并（重新合成），形成排序