第11章外部排序.ppt

1、第11章外部排序,11.1 外存信息的存取 11.2 外部排序的方法 11.3 多路平衡归并的实现 11.4 置换-选择排序 11.5 最佳归并树,11.1 外存信息的存取,两种存储器:内存储器(主存)和外存储器(辅存)。内存的信息可随机存取,且存取速度快,但价格贵(?),容量小(?). 外存储器包括磁带和磁盘(或磁鼓)前者为顺序存取的设备,后者为随机存取的设备. 外部排序:待排序记录的数量很大,以致内存一次不能存纳全部记录,在排序过程中尚需对外存进行访问的排序过程.,一磁带信息的存取,磁带大多数有0.5英寸宽(1.27cm)，最长可达3600英尺(1097.56m).,两种基本操作,在0.5

2、寸,记录9位或7位二进制(称为9道或7道带， 9轨或7轨带)。 9道带每一横排就可表示一个字符(8位表示一个字符，另一位作奇偶校验位)。 磁带上可记下各种文字信息或二进制信息，在磁带上信息按字符组存放，而不是按字符存放，磁带上信息的密度通常为每英寸800位或1600位或6250位(即每英寸的二进制字符数)，移动速度是每秒200英寸。 间隙IRG：磁带上相邻两组字符组(记录)之间空白区。,二磁盘信息的存取,磁盘是一种直接存取的存储设备； 它特征是存取时间变化； 可以直接存取任何字符组； 容量大、速度快，存取速度比磁带快得多； 磁盘是一个扁平的圆盘(与电唱机的唱片类似)，盘面上有许多饰为磁道的圆圈

3、； 信息记载在磁道上。由于磁道的圆圈为许多同心圆所以可以直接存取。磁盘可以是单片的也可以由若干盘片组成盎组。每一片上有两个面。以6片盘组为例由于最顶上和最低下盘片的外侧面不存信息所以总共只有10个面可用来保存信,硬盘（磁盘）阵列,多个硬盘构成阵列； 有一个管理程序，可以把阵列中的硬盘看成一个硬盘，这样，可以拥有容量非常的大的 单个虚拟硬盘；保存文件可以在这个虚拟的硬盘上进行，文件分布在不同的硬盘上。 阵列中如果一个硬盘有损坏，则影响整个虚拟硬盘上的文件。,11.2 外部排序的方法,内存中排序，外部输出归并段（子文件）。 把归并段进行归并（重新合成），形成排序后的文件。,11.3 多路平衡归并的

4、实现,11.4 置换-选择排序,在整个排序(得到所有初始归并段)的过程中，选择最小(或最大)关键字和输入、输出交叉或平行进行(边输入输出,边选择最小关键字)。 假设初始待排文件为输入文件F真，初始归并段文件为输出文件FO，内存工作区勾wA，FO和wA的初始状它为空，井设内存工作wA区的容量可容纳钟个记录则置换-选择排序的操作过程为：,置换-选择排序过程,(1)从FI输入w个记录到工作区WA。 (2)从WA中选出其中关键字取最小值的记录，记为MlNIMAX记录 (3)将MINlMAX记录输出到FO中云。 (4)若FI不空，则从FI输入下一个记录到WA中。 (5)从WA中所有关键字比MINIMAX记录的关键字大的记录中选出最小关键字记录，作为新的MINIMAX记录。 (6)重复(3)-(5)，直至在WA中选不出新的M1NMAK记录为止，由此得到一个初始归并段，输出一个归并段的结束标志到FO中去。 (7)重复(2)-(6)直至WA为空。由此得到全部初始归并段.,11.5 最佳归并树,由置换-选择生成所得的初始归并段，其各段长