第10章外部排序优秀PPT.ppt

《第10章外部排序优秀PPT.ppt》由会员分享，可在线阅读，更多相关《第10章外部排序优秀PPT.ppt（28页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第10章外部排序现在学习的是第1页，共28页10.1外存信息的特性外存信息的特性存储器存储器内部存储器内部存储器（内存）（内存）外部存储器外部存储器（外存）（外存）顺序存取设备（磁带存储器）顺序存取设备（磁带存储器）直接存取设备（磁盘存储器）直接存取设备（磁盘存储器）内存的存储容量小，但工作速度高；外存的存储容量大，但速度较内存的存储容量小，但工作速度高；外存的存储容量大，但速度较低。低。现在学习的是第2页，共28页10.1.1磁带存储器磁带存储器优点：优点：存储容量大，使用方便，价格便宜。存储容量大，使用方便，价格便宜。1.特性：特性：磁带存储器主要由磁带、读写磁头和磁带驱动器组成磁带存储器

2、主要由磁带、读写磁头和磁带驱动器组成，如，如下图所示。下图所示。目前常用的典型磁带长目前常用的典型磁带长2400英尺，英尺，宽宽0.5英寸，厚英寸，厚0.002英寸。磁带英寸。磁带表面上涂有磁性材料，可分为七表面上涂有磁性材料，可分为七道或九道磁带。道或九道磁带。七道磁带的每一横排中有六个二进制数据位和一个奇偶校验位。九道七道磁带的每一横排中有六个二进制数据位和一个奇偶校验位。九道磁带的每一横排中有八个二进制数据位和一个奇偶校验位。这样的一磁带的每一横排中有八个二进制数据位和一个奇偶校验位。这样的一排二进制数据位组成一个字节。排二进制数据位组成一个字节。现在学习的是第3页，共28页2.分页块存

3、储方法分页块存储方法磁带存储器是一种典型的顺序存取设备。所谓顺序存取，就是将记磁带存储器是一种典型的顺序存取设备。所谓顺序存取，就是将记录在存储器上一个接一个地依次存放，为得到第录在存储器上一个接一个地依次存放，为得到第i个记录，必须先个记录，必须先读第读第i-1个记录。个记录。由于磁带机不是连续运转的设备，而是一种启停设备，所以在启停由于磁带机不是连续运转的设备，而是一种启停设备，所以在启停时间内，不能对磁带进行正常读写，因此磁带上的信息通常分为若干记时间内，不能对磁带进行正常读写，因此磁带上的信息通常分为若干记录块，块与块之间留有一定的间隙，该间隙一般为录块，块与块之间留有一定的间隙，该间

4、隙一般为1/41/43/43/4英寸。英寸。由上可知，用磁带存储信息时需要在每段信息之间留有空隙，且此由上可知，用磁带存储信息时需要在每段信息之间留有空隙，且此空隙占用了大量的存储空间空隙占用了大量的存储空间。为了减少存储空间的浪费，通常采为了减少存储空间的浪费，通常采用把若干个记录组合成页块进行存储的办法，将记录间的间隙用把若干个记录组合成页块进行存储的办法，将记录间的间隙变成页块间的间隙。变成页块间的间隙。现在学习的是第4页，共28页10.1.2磁盘存储器磁盘存储器优点：优点：既能进行顺序存取，又能进行直接存取（随即存取），既能进行顺序存取，又能进行直接存取（随即存取），并且存取速度快。并

5、且存取速度快。1.磁盘存储器的特性磁盘存储器的特性 磁盘存储器主要由磁盘组和磁盘驱动器组成。磁盘组由若磁盘存储器主要由磁盘组和磁盘驱动器组成。磁盘组由若干个盘片组成，每个盘片有上下两个面，盘面上涂有光滑的干个盘片组成，每个盘片有上下两个面，盘面上涂有光滑的磁性物质。磁性物质。盘面上能够存储信息的盘面称为记录面。在记录盘面上有盘面上能够存储信息的盘面称为记录面。在记录盘面上有许多称为磁道的圆圈，信息就记载在磁道上。磁盘驱动器由许多称为磁道的圆圈，信息就记载在磁道上。磁盘驱动器由主轴和读写磁头组成，每个盘面都配有一个读写磁头。主轴和读写磁头组成，每个盘面都配有一个读写磁头。现在学习的是第5页，共2

6、8页磁盘磁盘可分为可分为固定臂盘固定臂盘和和活动臂盘活动臂盘两种。固定臂盘的每个盘面的每一磁两种。固定臂盘的每个盘面的每一磁道上都有独立的磁头，它是固定不动的，专门负责读写某一磁道上的信道上都有独立的磁头，它是固定不动的，专门负责读写某一磁道上的信息。息。如图：如图：2.分页块存储法分页块存储法 为了减少访问外存的次数，一般为了减少访问外存的次数，一般采用把记录组合成页块的方式来进行采用把记录组合成页块的方式来进行内外存数据的交换。一个页块（简称内外存数据的交换。一个页块（简称块）是磁盘上的一个物理记录，通常块）是磁盘上的一个物理记录，通常可以容纳多个逻辑记录，内存中设置可以容纳多个逻辑记录，

7、内存中设置的缓冲区应该与页块的大小相等。每的缓冲区应该与页块的大小相等。每次访问记录时，需要把一个页块读入次访问记录时，需要把一个页块读入一个缓冲区或者把一个缓冲区的数据一个缓冲区或者把一个缓冲区的数据写到一个页块。写到一个页块。现在学习的是第6页，共28页10.2外排序的基本方法外排序的基本方法 最常用的外部排序方法是归并排序法。这种方法由两最常用的外部排序方法是归并排序法。这种方法由两个阶段组成：第一阶段是把文件逐段输入到内存，用有效个阶段组成：第一阶段是把文件逐段输入到内存，用有效的内排序方法对文件的各个段进行排序，经排序的文件段的内排序方法对文件的各个段进行排序，经排序的文件段称为顺串

8、（或归并段），当它们生成后立即写到外存上，称为顺串（或归并段），当它们生成后立即写到外存上，这样在外存上就形成了许多初始顺串；第二阶段是对这些这样在外存上就形成了许多初始顺串；第二阶段是对这些顺串用某种归并方法（如顺串用某种归并方法（如2路归并法）进行多边归并，使路归并法）进行多边归并，使顺串的长度逐渐由小至大，直至变成一个顺串，即整个顺串的长度逐渐由小至大，直至变成一个顺串，即整个文件有序为止。文件有序为止。现在学习的是第7页，共28页10.2.1磁盘排序磁盘排序1.1.例子：假设磁盘上存有一文件，共有例子：假设磁盘上存有一文件，共有3600个记录（个记录（A1,A2,A3600），），页块

9、长为页块长为200个记录，供排序使用的缓冲区可提供容纳个记录，供排序使用的缓冲区可提供容纳600个记录个记录的空间，现要对该文件进行排序，排序过程可按如下步骤进行：的空间，现要对该文件进行排序，排序过程可按如下步骤进行：第一步：第一步：每次将三个页块（每次将三个页块（600个记录）由外存读到内存，进行内个记录）由外存读到内存，进行内排序，整个文件共得到排序，整个文件共得到6个初始顺串个初始顺串R1R6（每一个顺串占三个（每一个顺串占三个页块），然后把它们写回到磁盘上去页块），然后把它们写回到磁盘上去。内排序后得到的初始顺内排序后得到的初始顺串见串见p260的图的图10.3所示所示。第二步：第二

10、步：将供内排序使用的内存缓冲区分为三块相等的部分（即每块将供内排序使用的内存缓冲区分为三块相等的部分（即每块可容纳可容纳200个记录），其中两块作为输入缓冲区，一块作为输出个记录），其中两块作为输入缓冲区，一块作为输出缓冲区，然后对各顺串进行两路归并。缓冲区，然后对各顺串进行两路归并。归并过程见归并过程见p261p261的图的图10.410.4所示。所示。现在学习的是第8页，共28页2.多路归并多路归并一般说来，如果初始顺串有一般说来，如果初始顺串有m个，则如图个，则如图10.4所示那样的归并树就有所示那样的归并树就有log2m+1层，要对数据进行层，要对数据进行log2m遍扫描。采用多路归并

11、可以减遍扫描。采用多路归并可以减少扫描遍数，如少扫描遍数，如图所示。图所示。12345678910111213141516图10.516个顺串归并的示例12345678910111213141516现在学习的是第9页，共28页 在在k路归并中，为了确定下一个要输出的记录，就需要在路归并中，为了确定下一个要输出的记录，就需要在k个个记录中寻找关键字值最小的那个记录，这要比记录中寻找关键字值最小的那个记录，这要比2路归并复杂些。路归并复杂些。如果逐个比较每个顺串的待选记录，从而选出一个关键字值最小的记录，如果逐个比较每个顺串的待选记录，从而选出一个关键字值最小的记录，则每选取一个记录需要进行则每选

12、取一个记录需要进行k-1次比较。为了减少这个代价，我们次比较。为了减少这个代价，我们可采用下面介绍的选择树的方法来实现可采用下面介绍的选择树的方法来实现k路归并。路归并。选择树是一种完全二叉树，下图选择树是一种完全二叉树，下图显示了显示了8路归并的选择树，其中路归并的选择树，其中叶结点为各顺串在归并过程中的当前记录（图中标出了它们各自的关叶结点为各顺串在归并过程中的当前记录（图中标出了它们各自的关键字值），其它每个结点都代表其两个子结点中（关键字值）较小的键字值），其它每个结点都代表其两个子结点中（关键字值）较小的一个。因此根结点是树中的最小结点，即为下一个要输出的记录结点。一个。因此根结点是

13、树中的最小结点，即为下一个要输出的记录结点。这种选择树的构造可比作一种淘汰制的体育比赛，其中获胜者便是那这种选择树的构造可比作一种淘汰制的体育比赛，其中获胜者便是那个具有较小关键字值的记录。个具有较小关键字值的记录。现在学习的是第10页，共28页在非叶结点中，可以只存关键字值及指向相应记录的指针，而不在非叶结点中，可以只存关键字值及指向相应记录的指针，而不必存放整个记录内容。由于非叶结点总是代表优胜者，所以可以必存放整个记录内容。由于非叶结点总是代表优胜者，所以可以把这种树称为胜方树。把这种树称为胜方树。图图10.68路归并程序的选择树（胜方树）路归并程序的选择树（胜方树）图图10.7胜方树的

14、修改胜方树的修改现在学习的是第11页，共28页由上述过程由上述过程可见，要选取关键字值最小的记录，只有可见，要选取关键字值最小的记录，只有第一个需要进行第一个需要进行m-1次比较（建立胜方树），此后每个只要次比较（建立胜方树），此后每个只要进行进行log2m次比较即可，这是由于树中保持了以前的比较结次比较即可，这是由于树中保持了以前的比较结果。果。胜方树的缺点：胜方树的缺点：在选取一个记录之后重构选择树的修在选取一个记录之后重构选择树的修改工作比较麻烦，既要查找兄弟结点，又要查找父结改工作比较麻烦，既要查找兄弟结点，又要查找父结点。为了减少重构选择树的代价，可以采用败方树的点。为了减少重构选择

15、树的代价，可以采用败方树的办法来简化重构的过程。办法来简化重构的过程。败方树：就是在比赛树（选择树）中，每个非叶结点均存放败方树：就是在比赛树（选择树）中，每个非叶结点均存放其两个子结点中的败方。其两个子结点中的败方。现在学习的是第12页，共28页建立过程是：从叶结点开始分别对每两个兄弟结点进行比较，败者建立过程是：从叶结点开始分别对每两个兄弟结点进行比较，败者（较大的关键字值）存放在父结点中，而胜者继续参加下一轮的比（较大的关键字值）存放在父结点中，而胜者继续参加下一轮的比较，最终结果是每个较，最终结果是每个“选手选手”都停在自己失败的都停在自己失败的“比赛场比赛场”上。在上。在根结点之上有

16、一个附加的结点，存放全局优胜者。根结点之上有一个附加的结点，存放全局优胜者。图图10.8对应于图对应于图10.6的败方树的败方树图图10.9败方树的修改败方树的修改现在学习的是第13页，共28页 在败方树中，当输出全局优胜者记录之后，对树的修改比胜在败方树中，当输出全局优胜者记录之后，对树的修改比胜方树容易一些。修改过程如下：将新进入树的叶结点与父结点进方树容易一些。修改过程如下：将新进入树的叶结点与父结点进行比较，大的存放在父结点，小的与上一级父结点再进行比较，行比较，大的存放在父结点，小的与上一级父结点再进行比较，此过程不断进行，直至到根，最后把新的全局优胜者存放到附加此过程不断进行，直至

17、到根，最后把新的全局优胜者存放到附加的结点的结点。采用多路归并可以减少对数据的扫描遍数从而减少了输入输出量。采用多路归并可以减少对数据的扫描遍数从而减少了输入输出量。但也应该看到，若归并的路数但也应该看到，若归并的路数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)输入文件，每个记录只列出其关键字

18、值输入文件，每个记录只列出其关键字值初始顺串初始顺串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磁带排序磁带排

19、序 磁带排序过程基本上与磁盘排序过程相同。首先对待排磁带排序过程基本上与磁盘排序过程相同。首先对待排序文件的各段进行内排序，产生所有的初始顺串，再把它们序文件的各段进行内排序，产生所有的初始顺串，再把它们写回到磁带上，然后对这些顺串进行反复归并，直至成为一写回到磁带上，然后对这些顺串进行反复归并，直至成为一个顺串（即为有序文件）为止。个顺串（即为有序文件）为止。磁带排序需充分考虑顺串的分布情况，因为磁带是磁带排序需充分考虑顺串的分布情况，因为磁带是顺序存取的，排序过程中寻找或等待的时间较长，所以顺序存取的，排序过程中寻找或等待的时间较长，所以各顺串分布在不同磁带和同一磁带的不同位置对排序效各顺

20、串分布在不同磁带和同一磁带的不同位置对排序效率影响极大。率影响极大。现在学习的是第16页，共28页1.磁带排序的例子：磁带排序的例子：设有一个文件包含设有一个文件包含3600个记录，现在要对其进行排序，个记录，现在要对其进行排序，可供使用的磁带机有四台，分别为可供使用的磁带机有四台，分别为T1、T2、T3、T4，可，可供排序用的内存空间包含存放供排序用的内存空间包含存放600个记录的空间以及一些个记录的空间以及一些必要的工作区。设每个页块长为必要的工作区。设每个页块长为200个记录。为了简化讨个记录。为了简化讨论，我们假定初始顺串的生成是采用通常的内排序方论，我们假定初始顺串的生成是采用通常的

21、内排序方法实现的。这样，一次可读入三个页块，对其进行排法实现的。这样，一次可读入三个页块，对其进行排序并作为一个顺串输出。我们将采用序并作为一个顺串输出。我们将采用2 2路归并的方法来路归并的方法来实现顺串的归并，因而我们使用两个输入缓冲区和一实现顺串的归并，因而我们使用两个输入缓冲区和一个输出缓冲区，每个缓冲区能容纳个输出缓冲区，每个缓冲区能容纳200200个记录。个记录。现在学习的是第17页，共28页排序过程的具体步骤如下排序过程的具体步骤如下：第一步：第一步：把输入文件分段（每段包含把输入文件分段（每段包含600个记录）读入内存并进行个记录）读入内存并进行内排序，生成初始顺串，然后将这些

22、顺串轮流写到磁带机内排序，生成初始顺串，然后将这些顺串轮流写到磁带机T1和和T2上上。见图见图10.11(a)。图图10.11磁带排序过程磁带排序过程现在学习的是第18页，共28页第二步：第二步：采用采用2路归并法对路归并法对T1上的各顺串与上的各顺串与T2上的各顺上的各顺串进行归并，并把所产生的较大顺串轮流分布到串进行归并，并把所产生的较大顺串轮流分布到T3和和T4上（若输入文件带需要保留，则在第一步完成后把输入文件上（若输入文件带需要保留，则在第一步完成后把输入文件带从带从T4上卸下来，换上工作带）。上卸下来，换上工作带）。见图见图10.11(b)。第三步：第三步：把把T3上的顺串上的顺串

23、1和和T4上的顺串上的顺串2进行合并，并将进行合并，并将结果放到结果放到T1上。上。见图见图10.11(c)。第四步：把第四步：把T1上的顺串上的顺串1和和T3上的顺串上的顺串3合并，并把结果合并，并把结果放到放到T2上，即为所要求的有序文件。上，即为所要求的有序文件。现在学习的是第19页，共28页2.非平衡归并非平衡归并k路路平衡归并的特点是：把要归并的顺串平衡均匀地分布到平衡归并的特点是：把要归并的顺串平衡均匀地分布到k台输入带上。这样，为了避免对数据进行再分配的扫描，台输入带上。这样，为了避免对数据进行再分配的扫描，就需要就需要2k台磁带机，现采用非平衡归并，即不同输入带台磁带机，现采用

24、非平衡归并，即不同输入带上的顺串个数不同，适当地对顺串进行非均匀分配，就上的顺串个数不同，适当地对顺串进行非均匀分配，就可以用不到可以用不到2k台磁带机来实现台磁带机来实现k路归并。路归并。用用k+1台磁带机便可取得台磁带机便可取得k路归并的效果，我们以路归并的效果，我们以三台磁带机三台磁带机T1、T2、T3实现实现2路归并为例来说明这个方路归并为例来说明这个方法。法。现在学习的是第20页，共28页 我们设初始顺串的长度为度量单位，即规定初始我们设初始顺串的长度为度量单位，即规定初始顺串的长度为顺串的长度为1，用，用Sn来表示某台磁带机上有来表示某台磁带机上有n个顺串，个顺串，每个顺串的长度为

25、每个顺串的长度为S。步骤步骤T1T2T3说明说明初始分布初始分布1513第一步后第一步后1223归并到归并到T3第二步后第二步后3221归并到归并到T2第三步后第三步后5131归并到归并到T1第四步后第四步后81归并到归并到T3图图10.12采用非采用非平衡分布法用三台磁带机实现平衡分布法用三台磁带机实现2路归并路归并现在学习的是第21页，共28页讨论如何确定顺串初始分布的问题讨论如何确定顺串初始分布的问题为了确定初始分布，就得从最后一步往前推。假设为了确定初始分布，就得从最后一步往前推。假设有有n步，我们希望步，我们希望n步之后在步之后在T1上正好有一个顺串，而在上正好有一个顺串，而在T2和

26、和T3上没有顺串。要做到这点，则必须把上没有顺串。要做到这点，则必须把T2中的一个顺串中的一个顺串与与T3中的一个顺串加以归并来得到这种顺串，并且中的一个顺串加以归并来得到这种顺串，并且T2和和T3上上没有别的顺串，所以在第没有别的顺串，所以在第n-1步后，步后，T2和和T3上应各有一上应各有一个顺串，个顺串，T2上的顺串是从上的顺串是从T1和和T3中各取一个顺串加以归中各取一个顺串加以归并后得到，因此，在第并后得到，因此，在第n-2步后，在步后，在T1上应有一个上应有一个顺串，在顺串，在T3上应有两个顺串，就这样一步一步往前推。上应有两个顺串，就这样一步一步往前推。现在学习的是第22页，共2

27、8页下图显示了这个前推得过程。下图显示了这个前推得过程。步骤步骤T1T2T3n100n-1011n-2102n-3320n-4053n-5508n-61380三带三带2路归并的顺串分布路归并的顺串分布步骤步骤T1T2T3T4n1000n-10111n-21022n-33204n-47640n-5013117n-61302420n-73724044n-88168440四带四带3路归并的顺串分布路归并的顺串分布现在学习的是第23页，共28页10.3总结与提高总结与提高10.3.1主要知识点主要知识点基本概念：基本概念：外部排序：待排序的记录数外部排序：待排序的记录数n很大，内存容纳不下，必须借用外

28、部很大，内存容纳不下，必须借用外部存储器才能完成的排序过程。存储器才能完成的排序过程。外存一般分为两类：顺序存取设备（如磁带存储器）、直接存取设外存一般分为两类：顺序存取设备（如磁带存储器）、直接存取设备（如磁盘存储器）。备（如磁盘存储器）。磁带的存取时间主要用在定位上，读写头与所需信息的距离越磁带的存取时间主要用在定位上，读写头与所需信息的距离越远，定位时间就越长。远，定位时间就越长。磁盘存储器（硬盘）特点：直接存取（随机存取），高速。磁盘存储器（硬盘）特点：直接存取（随机存取），高速。磁盘存储单位：盘片组，柱面，磁道，扇段。磁盘存储单位：盘片组，柱面，磁道，扇段。外存中把若干个记录（逻辑记

29、录）组合成页块（物理记录）进行外存中把若干个记录（逻辑记录）组合成页块（物理记录）进行存储。页块（存储。页块（1KB8KB）是内外存数据交换的基本单位：）是内外存数据交换的基本单位：内存缓冲区：暂存一个页块的内容。内存缓冲区：暂存一个页块的内容。现在学习的是第24页，共28页外部排序的基本过程：外部排序的基本过程：（1）生成初始顺串；）生成初始顺串；（2）归并：对顺串反复进行归并，直至变成一个顺串。）归并：对顺串反复进行归并，直至变成一个顺串。初始顺串的生成方法：初始顺串的生成方法：内部排序法。所生成顺串的大小正好等于一次能放入内存中的记录内部排序法。所生成顺串的大小正好等于一次能放入内存中的

30、记录个数。个数。置换选择排序法。如果输入文件中的记录按其关键字随机排置换选择排序法。如果输入文件中的记录按其关键字随机排列，则所生成的初始顺串的平均长度为内存工作区大小的列，则所生成的初始顺串的平均长度为内存工作区大小的2倍。倍。归并方法：归并方法：二路归并法二路归并法多路归并方法（多路归并方法（1）：胜方树。了解胜方树的结构特点和重构方法。）：胜方树。了解胜方树的结构特点和重构方法。多路归并方法（多路归并方法（2）：败方树。了解败方树的结构特点和重构方法。）：败方树。了解败方树的结构特点和重构方法。现在学习的是第25页，共28页10.3.2典型题例典型题例例例10.1最佳归并树。最佳归并树。

31、已知有已知有31个长度不等的初始归并段，其中个长度不等的初始归并段，其中8段长段长度为度为2，8段长度为段长度为3，7段长度为段长度为5，5段长度为段长度为12，3段段长度为长度为20（单位为物理块）。请设计一个（单位为物理块）。请设计一个5-路最佳归路最佳归并方案，并计算归并时总的读并方案，并计算归并时总的读/写外存次数。写外存次数。现在学习的是第26页，共28页【解解】根据题目可知：根据题目可知：31个初始归并段执行个初始归并段执行5-路归并。路归并。由于（由于（311）MOD（51）=20，所所以以第第一一次次归归并并（311）MOD（51）+1=3个个长长度度最最短短的的初初始归并段，以后每一步都始归并段，以后每一步都5个长度最短的初始归并段。个长度最短的初始归并段。最佳归并树如下图所示。最佳归并树如下图所示。现在学习的是第27页，共28页容容易易算算出出，该该最最佳佳归归并并树树的的带带权权路路径径长长度度为为400，所所以以按按此此树树进进行行归并，仅需对外存进行归并，仅需对外存进行800次读次读/写。写。现在学习的是第28页，共28页