第10章外部排序优秀课件.ppt

第10章外部排序第1 页，本讲稿共28 页10.1 外存信息的特性存储器内部存储器（内存）外部存储器（外存）顺序存取设备（磁带存储器）直接存取设备（磁盘存储器）内存的存储容量小，但工作速度高；外存的存储容量大，但速度较低。第2 页，本讲稿共28 页10.1.1 磁带存储器优点：存储容量大，使用方便，价格便宜。1.特性：磁带存储器主要由磁带、读写磁头和磁带驱动器组成，如下图所示。目前常用的典型磁带长2400英尺，宽0.5英寸，厚0.002英寸。磁带表面上涂有磁性材料，可分为七道或九道磁带。七道磁带的每一横排中有六个二进制数据位和一个奇偶校验位。九道磁带的每一横排中有八个二进制数据位和一个奇偶校验位。这样的一排二进制数据位组成一个字节。第3 页，本讲稿共28 页2.分页块存储方法磁带存储器是一种典型的顺序存取设备。所谓顺序存取，就是将记录在存储器上一个接一个地依次存放，为得到第i个记录，必须先读第i-1个记录。由于磁带机不是连续运转的设备，而是一种启停设备，所以在启停时间内，不能对磁带进行正常读写，因此磁带上的信息通常分为若干记录块，块与块之间留有一定的间隙，该间隙一般为1/43/4英寸。由上可知，用磁带存储信息时需要在每段信息之间留有空隙，且此空隙占用了大量的存储空间。为了减少存储空间的浪费，通常采用把若干个记录组合成页块进行存储的办法，将记录间的间隙变成页块间的间隙。第4 页，本讲稿共28 页10.1.2 磁盘存储器优点：既能进行顺序存取，又能进行直接存取（随即存取），并且存取速度快。1.磁盘存储器的特性 磁盘存储器主要由磁盘组和磁盘驱动器组成。磁盘组由若干个盘片组成，每个盘片有上下两个面，盘面上涂有光滑的磁性物质。盘面上能够存储信息的盘面称为记录面。在记录盘面上有许多称为磁道的圆圈，信息就记载在磁道上。磁盘驱动器由主轴和读写磁头组成，每个盘面都配有一个读写磁头。第5 页，本讲稿共28 页磁盘可分为固定臂盘和活动臂盘两种。固定臂盘的每个盘面的每一磁道上都有独立的磁头，它是固定不动的，专门负责读写某一磁道上的信息。如图：2.分页块存储法 为了减少访问外存的次数，一般采用把记录组合成页块的方式来进行内外存数据的交换。一个页块（简称块）是磁盘上的一个物理记录，通常可以容纳多个逻辑记录，内存中设置的缓冲区应该与页块的大小相等。每次访问记录时，需要把一个页块读入一个缓冲区或者把一个缓冲区的数据写到一个页块。第6 页，本讲稿共28 页10.2 外排序的基本方法 最常用的外部排序方法是归并排序法。这种方法由两个阶段组成：第一阶段是把文件逐段输入到内存，用有效的内排序方法对文件的各个段进行排序，经排序的文件段称为顺串（或归并段），当它们生成后立即写到外存上，这样在外存上就形成了许多初始顺串；第二阶段是对这些顺串用某种归并方法（如2路归并法）进行多边归并，使顺串的长度逐渐由小至大，直至变成一个顺串，即整个文件有序为止。第7 页，本讲稿共28 页10.2.1 磁盘排序1.例子：假设磁盘上存有一文件，共有3600个记录（A1,A2,A3600），页块长为200个记录，供排序使用的缓冲区可提供容纳600个记录的空间，现要对该文件进行排序，排序过程可按如下步骤进行：第一步：每次将三个页块（600个记录）由外存读到内存，进行内排序，整个文件共得到6个初始顺串R1R6（每一个顺串占三个页块），然后把它们写回到磁盘上去。内排序后得到的初始顺串见p260的图10.3所示。第二步：将供内排序使用的内存缓冲区分为三块相等的部分（即每块可容纳200个记录），其中两块作为输入缓冲区，一块作为输出缓冲区，然后对各顺串进行两路归并。归并过程见p261的图10.4所示。第8 页，本讲稿共28 页2.多路归并一般说来，如果初始顺串有m个，则如图10.4所示那样的归并树就有log2m+1层，要对数据进行log2m遍扫描。采用多路归并可以减少扫描遍数，如图所示。1234 5678910111213141516图10.516个顺串归并的示例 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16第9 页，本讲稿共28 页 在k路归并中，为了确定下一个要输出的记录，就需要在k个记录中寻找关键字值最小的那个记录，这要比2路归并复杂些。如果逐个比较每个顺串的待选记录，从而选出一个关键字值最小的记录，则每选取一个记录需要进行k-1次比较。为了减少这个代价，我们可采用下面介绍的选择树的方法来实现k路归并。选择树是一种完全二叉树，下图显示了8路归并的选择树，其中叶结点为各顺串在归并过程中的当前记录（图中标出了它们各自的关键字值），其它每个结点都代表其两个子结点中（关键字值）较小的一个。因此根结点是树中的最小结点，即为下一个要输出的记录结点。这种选择树的构造可比作一种淘汰制的体育比赛，其中获胜者便是那个具有较小关键字值的记录。第10 页，本讲稿共28 页在非叶结点中，可以只存关键字值及指向相应记录的指针，而不必存放整个记录内容。由于非叶结点总是代表优胜者，所以可以把这种树称为胜方树。图10.6 8路归并程序的选择树（胜方树）图10.7 胜方树的修改第1 1 页，本讲稿共28 页 由上述过程可见，要选取关键字值最小的记录，只有第一个需要进行m-1次比较（建立胜方树），此后每个只要进行log2m次比较即可，这是由于树中保持了以前的比较结果。胜方树的缺点：在选取一个记录之后重构选择树的修改工作比较麻烦，既要查找兄弟结点，又要查找父结点。为了减少重构选择树的代价，可以采用败方树的办法来简化重构的过程。败方树：就是在比赛树（选择树）中，每个非叶结点均存放其两个子结点中的败方。第12 页，本讲稿共28 页建立过程是：从叶结点开始分别对每两个兄弟结点进行比较，败者（较大的关键字值）存放在父结点中，而胜者继续参加下一轮的比较，最终结果是每个“选手”都停在自己失败的“比赛场”上。在根结点之上有一个附加的结点，存放全局优胜者。图10.8 对应于图10.6的败方树 图10.9 败方树的修改第13 页，本讲稿共28 页 在败方树中，当输出全局优胜者记录之后，对树的修改比胜方树容易一些。修改过程如下：将新进入树的叶结点与父结点进行比较，大的存放在父结点，小的与上一级父结点再进行比较，此过程不断进行，直至到根，最后把新的全局优胜者存放到附加的结点。采用多路归并可以减少对数据的扫描遍数从而减少了输入输出量。但也应该看到，若归并的路数k增大时，缓冲区就要设置得比较大。3.初始顺串的生成其生成过程见下图。第14 页，本讲稿共28 页输入文件10，9，20，6，8，12，90，17，14，22，7，24，15，16，11，100，13，18，26，38，30，25，50，28，110，21，40，19，(a)输入文件，每个记录只列出其关键字值初始顺串1：6，8，9，10，12，14,15,16,17,20,22,24,26,30,38，50,90,100,110初始顺串2:7,11,13,18,21,25,28,40(b)生成的初始顺串(c)包含8个记录的败方树，并列出了新进入败方树的各记录的结点位置及进入的次序，用符号表示该记录不属于当前的初始顺川。图10.10 初始顺串的生成过程第15 页，本讲稿共28 页10.2.2 磁带排序 磁带排序过程基本上与磁盘排序过程相同。首先对待排序文件的各段进行内排序，产生所有的初始顺串，再把它们写回到磁带上，然后对这些顺串进行反复归并，直至成为一个顺串（即为有序文件）为止。磁带排序需充分考虑顺串的分布情况，因为磁带是顺序存取的，排序过程中寻找或等待的时间较长，所以各顺串分布在不同磁带和同一磁带的不同位置对排序效率影响极大。第16 页，本讲稿共28 页1.磁带排序的例子：设有一个文件包含3600个记录，现在要对其进行排序，可供使用的磁带机有四台，分别为T1、T2、T3、T4，可供排序用的内存空间包含存放600个记录的空间以及一些必要的工作区。设每个页块长为200个记录。为了简化讨论，我们假定初始顺串的生成是采用通常的内排序方法实现的。这样，一次可读入三个页块，对其进行排序并作为一个顺串输出。我们将采用2路归并的方法来实现顺串的归并，因而我们使用两个输入缓冲区和一个输出缓冲区，每个缓冲区能容纳200个记录。第17 页，本讲稿共28 页排序过程的具体步骤如下：第一步：把输入文件分段（每段包含600个记录）读入内存并进行内排序，生成初始顺串，然后将这些顺串轮流写到磁带机T1和T2上。见图10.11(a)。图10.11 磁带排序过程第18 页，本讲稿共28 页第二步：采用2路归并法对T1上的各顺串与T2上的各顺串进行归并，并把所产生的较大顺串轮流分布到T3和T4上（若输入文件带需要保留，则在第一步完成后把输入文件带从T4上卸下来，换上工作带）。见图10.11(b)。第三步：把T3上的顺串1和T4上的顺串2进行合并，并将结果放到T1上。见图10.11(c)。第四步：把T1上的顺串1和T3上的顺串3合并，并把结果放到T2上，即为所要求的有序文件。第19 页，本讲稿共28 页2.非平衡归并k路平衡归并的特点是：把要归并的顺串平衡均匀地分布到k台输入带上。这样，为了避免对数据进行再分配的扫描，就需要2k台磁带机，现采用非平衡归并，即不同输入带上的顺串个数不同，适当地对顺串进行非均匀分配，就可以用不到2k台磁带机来实现k路归并。用k+1台磁带机便可取得k路归并的效果，我们以三台磁带机T1、T2、T3实现2路归并为例来说明这个方法。第20 页，本讲稿共28 页 我们设初始顺串的长度为度量单位，即规定初始顺串的长度为1，用Sn来表示某台磁带机上有n个顺串，每个顺串的长度为S。步骤T1 T2 T3 说明初始分布15 13 第一步后12 23 归并到T3第二步后32 21 归并到T2第三步后51 31 归并到T1第四步后81 归并到T3图10.12 采用非平衡分布法用三台磁带机实现2路归并第21 页，本讲稿共28 页讨论如何确定顺串初始分布的问题 为了确定初始分布，就得从最后一步往前推。假设有n步，我们希望n步之后在T1上正好有一个顺串，而在T2和T3上没有顺串。要做到这点，则必须把T2中的一个顺串与T3中的一个顺串加以归并来得到这种顺串，并且T2和T3上没有别的顺串，所以在第n-1步后，T2和T3上应各有一个顺串，T2上的顺串是从T1和T3中各取一个顺串加以归并后得到，因此，在第n-2步后，在T1上应有一个顺串，在T3上应有两个顺串，就这样一步一步往前推。第22 页，本讲稿共28 页下图显示了这个前推得过程。步骤T1 T2 T3 n 1 0 0 n-1 0 1 1 n-2 1 0 2 n-3 3 2 0 n-4 0 5 3 n-5 5 0 8 n-6 13 8 0三带2路归并的顺串分布 步骤T1 T2 T3 T4 n 1 0 0 0 n-1 0 1 1 1 n-2 1 0 2 2 n-3 3 2 0 4 n-4 7 6 4 0 n-5 0 13 11 7 n-6 13 0 24 20 n-7 37 24 0 44 n-8 81 68 44 0 四带3路归并的顺串分布第23 页，本讲稿共28 页10.3 总结与提高10.3.1 主要知识点基本概念：外部排序：待排序的记录数n很大，内存容纳不下，必须借用外部存储器才能完成的排序过程。外存一般分为两类：顺序存取设备（如磁带存储器）、直接存取设备（如磁盘存储器）。磁带的存取时间主要用在定位上，读写头与所需信息的距离越远，定位时间就越长。磁盘存储器（硬盘）特点：直接存取（随机存取），高速。磁盘存储单位：盘片组，柱面，磁道，扇段。外存中把若干个记录（逻辑记录）组合成页块（物理记录）进行存储。页块（1KB8KB）是内外存数据交换的基本单位：内存缓冲区：暂存一个页块的内容。第24 页，本讲稿共28 页外部排序的基本过程：（1）生成初始顺串；（2）归并：对顺串反复进行归并，直至变成一个顺串。初始顺串的生成方法：内部排序法。所生成顺串的大小正好等于一次能放入内存中的记录个数。置换选择排序法。如果输入文件中的记录按其关键字随机排列，则所生成的初始顺串的平均长度为内存工作区大小的2倍。归并方法：二路归并法多路归并方法（1）：胜方树。了解胜方树的结构特点和重构方法。多路归并方法（2）：败方树。了解败方树的结构特点和重构方法。第25 页，本讲稿共28 页10.3.2 典型题例例10.1 最佳归并树。已知有31个长度不等的初始归并段，其中8段长度为2，8段长度为3，7段长度为5，5段长度为12，3段长度为20（单位为物理块）。请设计一个5-路最佳归并方案，并计算归并时总的读/写外存次数。第26 页，本讲稿共28 页【解】根据题目可知：31个初始归并段执行5-路归并。由于（311）MOD（51）=2 0，所以第一次归并（311）MOD（51）+1=3个长度最短的初始归并段，以后每一步都5个长度最短的初始归并段。最佳归并树如下图所示。第27 页，本讲稿共28 页 容易算出，该最佳归并树的带权路径长度为400，所以按此树进行归并，仅需对外存进行800次读/写。第28 页，本讲稿共28 页