数据结构第十一章外部排序.doc

第十一章 外部排序前面讨论的排序方法，在整个排序过程中，不涉及数据的内外存交换，待排序的记录存放在存储器中,对一个大型文件,我们不能将其全部记录都放入内存中实现排序，甚至仅将每个记录的排序码放到内存也是不可能的，此时必需借助外存来实现排序（分类）外部存贮设备计算机通常配备两种存储器：内存储器（主存）和外存储器（辅存）内存储器的存取速度快，能随机存取,但价格贵,容量小外存储器存取速度慢,存储量大,有海量存储器之称外存储器包括磁带，磁盘，光盘等，前者为顺序存取设备，后者为随机存取设备下面分别以磁带，磁盘为例进行介绍磁带（magnetic tapes）磁带是薄薄涂上一层磁性材料的一条窄带目前使用的典型磁带的尺寸和规格为：厚*宽*长=0.002英寸*0.5英寸*2400英尺，分七道和九道两种七道磁带有六个二进制数据（信息）位和一个奇偶校验位；九道磁带有八个二进制数据（信息）和一个奇偶校验位常用的存储密度如表11.1所示:磁带存储密度（byteser inch)七道七道九道九道2005568001600表11.1我们将每英寸磁带上可写入的位数称为磁带密度（tape density）磁带的读出和写入是用磁带机实现的，将磁带盘放在磁带机上，驱动器控制磁带盘转动，带动磁带向前移动。

通过读写头就可以读出磁带上的信息或者把信息写入磁带中磁带的存取时间主要花费在将磁带转到所需要的位置上，磁带不是连续转动的设备,工作时它不断的启停,并且启动和停止都需要一定的时间，大约为5毫秒，如图11.2所示磁带从停止状态启动后，要经过一个加速过程才能达到正常的读写速度同样，一个读出或写入完成后，从运动状态到完全停止,还要经过一个减速过程由于启停需要一个缓冲时间，因此在磁带上所存的数据记录之间必须空出一段间隙IRG（Inter Record），一般IRG=0.6英寸速度启动时间约5ms停止时间约5ms正常读写速度时间物理记录IRQ图11.2 磁带的启停和IRQ在磁带上，用户所使用的数据（或信息）通常是按照逻辑记录（也简称记录，值得注意的是这里的记录或逻辑记录与本书前面提到的意义全然不同）存放的假定共有1000个记录，每个记录包含80个字符，每个记录之间的IRG取0. 6英寸，磁带密度为每英寸1600个字符显然，每个记录需要0.05 英寸加上1000个IRG总共占用磁带长度为650英寸，其中用于存放数据的磁带长度仅为50英寸，可见磁带的有效利用率为7.69%若要提高对磁带的有效利用率，关键在于减少IRG的数量。

这可采用组块方法来解决，即将若干块记录组合成较大的块（又称之为物理记录），并且只在块间保留IRG,对于上例,我们把100个记录组合成一个块，则存贮信息（加上IRG）共占用磁带长度为：10*0.6*1000*0.05=56英寸可见组块方法可大大减少所需磁带长度,提高磁带利用效率组块方法还可减少I/O操作因一次I/O操作可把整个块都读入内存缓冲区中,然后再从缓冲区中选取所需的记录当然,也不能说块越大越好实际上,若块越大，则所需的内存缓冲区就越大，从而过多的耗费内存空间另外,块越大,会造成读写时间过长,增加出错的概率通常1个块的大小取1k字节至8k字节为宜磁带是一种典型的顺序存取的存储设备存取时间与读写头的当前位置到所读信息的位置的距离有关，距离越大，所需存取的时间就越长如果读写头位于第k和第k+1个块之间的IRG上，用户欲读取第k+m个块中的信息，则必须让磁带向前运动，跳过中间的m-1个块和m-1 个IRG后才能开始读第k+m块上的信息，这正是顺序存取的主要缺陷，它使检索和修改信息都很不方便因此磁带主要用于处理很少需要修改的并进行顺序存取的信息磁盘(disk)磁盘是一种直接存取的外存储器磁盘和磁带不同，它不但能进行顺序存取，而且能直接存取任何记录。

它的存取速度比磁带快的多磁盘分硬盘和软盘两种，硬盘的容量比软盘的大得多，而且其存取速度也比软盘快的多，此处只对硬盘加以介绍磁盘是一个扁平的圆盘(与电唱机的唱片类似)，盘面上有许多称为磁道的圆圈信息就记载在磁道上由于磁道的圆圈为许多同心圆，所以可以直接存取磁盘可以是单片的，也可以由若干盘片组成盘组每个盘片包括上下两个盘面以6片盘组为例，由于最上面和最下面不存信息，所以总共只有10个面用来保存信息其中一个盘面也叫做一个记录面，每一个记录面有一个读(写)头，所有的读(写)头是固定在一起同时同步移动的 在一个记录面上读(写)头的轨迹叫做磁道（track），换句话说，磁道就是记录面上的圆环，各记录面上半径相同的磁道总和称为一个圆“柱面”，每一个面有200～400道在磁盘上标明一个具体信息必须用一个三维地址：（柱面号，盘面号，块号）其中柱面号确定读写头的径向运动,即将磁头定位到正确圆柱面而块号确定信息在盘面圆圈上的位置磁盘信息的读写包括如下三个时间：⑴寻找时间（ts):将磁头定位到正确圆柱面所用的时间，这取决于磁头越过圆柱面的个数，也就是活动臂径向移动所用时间;⑵等待时间（t1）:等待要访问信息转道磁头下所用时间；⑶传输时间（trw）:读写所需信息所用时间。

磁盘的寻找时间ts最大约为 0.1秒;由于磁盘旋转速度很快,约2400～3600转/分，则等待时间最长不超过25毫秒（旋转一圈所需时间）；又磁盘传输率一般在10==5字符/秒和5*10===5字符/秒之间，则在磁盘上读写信息的时间主要在巡查时间上因此，在磁盘上存放信息时应将相关信息放在同一柱面上或临近柱面上，以求在读写信息时尽量减少磁头来回移动次数，以免不必要的巡查时间11.1 外排序的主要过程在外排序中最常用的方法是归并排序法这种方法基本上要经历两个不同阶段进行分类，已经分类的文件段通常叫做归并段(顺串)，记作R整个文件经过逐段排序后，一段一段的写回到某个外存设备上，这样，外存上就形成了许多初始归并段；第二阶段是对这些初始归并段使用某种归并方法，进行多次归并，最后在外存上形成了整个文件的单一归并段，这样就完成了这个文件的外部排序现在我们举例说明磁盘文件归并排序的基本过程假设有一个存在于磁盘的包含4500个记录的文件，依次为A1,A2,...,A4500,若磁盘的读写单位为250个记录的数据块，而内存最多只能为外部分类提供750个记录的空间，则对此文件进行归并分类的过程可以分为如下两个阶段：⑴ 每次从输入文件上输入三个数据块,共有750个记录，采用堆垒或快速分类法对其进行内部分类,如此处理一遍以后,整个文件就变成6个初始归并段R1～R6,把R1～R6写回到磁盘上。

⑵将能容纳750个记录的内存空间划分为三个等份，其中两份用作两个输入缓冲区，一份用作输出缓冲区先归并R1和R2：每次从R1和R2中分别读出一块250个记录的信息传送到输入缓冲区，并把两个缓冲区的记录归并到输出缓冲区当输出缓冲区装满250个记录时，就写回到磁盘上(为了节省时间，假定写回到暂存工作磁盘上)，如果工作期间，某个输入缓冲区空了，就立即向该缓冲区继续装入所对应归并段的下一块记录信息，使之与另一输入缓冲区的剩余记录进行归并，直到把R1和R2归并为一个归并段R1'为止 类似的，再归并R3,R4为R2'，R5,R6为R3'此时，就形成了3个都包含1500个记录的归并段R1',R2'和R3'，再把R1'和R2'归并为R1''(包含3000个记录）最后把R1''和R3'归并为R2''(包含4500个记录)于是就得到了已分类的文件整个归并过程如图11.4所示从 以上看出，外部归并的主要过程可概括为如下两个操作：⑴输入--进行内部分类，产生初始归并段--输出⑵输入--归并--输出归并段R1R2R3R4R5R6R1’R2’R3’R1’’R1’’’ 在整个外部分类过程中，操作⑴进行一趟操作⑵要进行若干趟。

假设tio为对整个文件进行输入和输出所需要的时间,tm为对整个文件执行一趟操作⑵归并所需要的时间；tis为对整个文件执行一趟操作⑴内部分类所需要的时间如果对输入文件进行外部归并分类时，操作⑵执行m遍，那么所需的总的时间是：（2ti0+tis）+m(2ti0+tm)为了节省磁盘文件外部归并分类的时间，我们需要从如下三个方面来研究磁盘文件的外部分类技术:⑴k路归并:一种减少文件归并趟数的方法⑵缓冲区的处理:巧妙的运用缓冲区,以便使I/o和cpu处理尽可能地并行操作⑶归并段的产生:研究一种较好的产生初始归并段的方法§11.2 K路归并若能减少文件归并的趟数，就能减少磁盘文件外部归并的时间这里介绍的减少归并趟数的一种方法是k路归并所谓的k路归并，就是把k个分类文件联合成一个文件，也就是每次从k个归并段中，取出一个记录，在k个记录中选择关键字最小的记录我们利用一种置换选择法，即利用一棵选择树来从k个记录中，选取最小记录为了引入选择树的概念，先谈谈题外的话,也就是大家都熟悉的单淘汰赛单淘汰赛是把参加比赛的运动员两两相比，然后再将胜者两两相比比赛中运动员只要输掉一次就被淘汰掉，始终保持不败的那个运动员成为这轮比赛的冠军。

比如７个运动员参加单淘汰赛，我们可以把竞赛程序表画成一棵二叉树，如图11.5所示其叶子表示参加比赛的运动员，非终端的节点表示比赛中的胜者，根节点表示这轮比赛的冠军DDGADFGABCDEF图11.5 单淘汰赛的二叉树在这种比赛规则下，有一个很有用的结论：如果运动员D在夺得冠军之后，加入另一运动员D‘，那么在D’和除D之外的运动员中再要选拔一个冠军，不必进行所有的比赛，而只要举行那些有D参加的比赛就行了（因为只有被D打败的运动员才可能成为冠军）如果我们把这种思想运用于K路归并，每一个节点表示一个记录，进行一次单淘汰赛后，得出一个最小的记录作为输出记录，当冠军输出以后，将冠军所在的归并段的下一个记录替代这个冠军，重新按照上述方法进行比赛，又得到一个冠军，作为下一个输出记录可以想象，这种方法将会减少关键字的比较次数根据单淘汰赛的竞赛程序，我们引入选择树的概念：100110150…182023…111617…155051…15203031…182022…151617…2527… 1 2 3 4 5 6 7 8图11.6 选择树66891090176889962017所谓选择树，是一棵完全二叉树，其叶子表示记录，非终端节点表示两个孩子中的较小记录，根是所有记录中的最小记录。

如下图11.6所示，它是一棵对8个归并段进行8路归并的选择树对选择树，我们是利用二叉树的顺序表示法来表示的由于记录一般都相当大，所以非叶节点只包含指向所表示记录的指针，而每个叶节点表示对应归并段最前面的一个记录的关键字下面来描述其归并的过程：如图11.7所示这时选择树的根节点所表示的记录6是8个记录中最小的于是，将关键字6的记录，作为归并结果输出输出以后，再把记录6所在的归并段4的下一个记录15，送到它的叶子上为了确定下一个输出记录，我们需沿着节点11到根节点的路径在兄弟节点之间进行比。