第10章外部排序精.ppt

《第10章外部排序精.ppt》由会员分享，可在线阅读，更多相关《第10章外部排序精.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个记录。个记录。由于磁带机不是连续运转的设备，而是一种启停设备，由于磁带机不是连续运转的设备，而是一种启停设备，所以在启停时间内，不能对磁带进行正常读写，因此磁带上所以在启停时间内，不能对磁带进行正常读写，因此磁带上的信息通常分为若干记录块，块与块之间留有一定的间隙，的信息通常分为若干记录块，块与块之间留有一定的间隙，该间隙一般为该间隙一般为1/4

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

5、磁盘存储器的特性磁盘存储器的特性 磁盘存储器主要由磁盘组和磁盘驱动器组成。磁盘组磁盘存储器主要由磁盘组和磁盘驱动器组成。磁盘组由若干个盘片组成，每个盘片有上下两个面，盘面上涂有由若干个盘片组成，每个盘片有上下两个面，盘面上涂有光滑的磁性物质。光滑的磁性物质。盘面上能够存储信息的盘面称为记录面。在记录盘面盘面上能够存储信息的盘面称为记录面。在记录盘面上有许多称为磁道的圆圈，信息就记载在磁道上。磁盘驱上有许多称为磁道的圆圈，信息就记载在磁道上。磁盘驱动器由主轴和读写磁头组成，每个盘面都配有一个读动器由主轴和读写磁头组成，每个盘面都配有一个读写磁头。写磁头。第5页，本讲稿共28页磁盘磁盘可分为可分为

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

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

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

9、用的缓冲个记录，供排序使用的缓冲区可提供容纳区可提供容纳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个顺串归并的示例 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16第9页，本讲稿共28页 在在k路归并中，为了确定下一个要输出的记录，就需要路归并中，为了确定下一个要输出的记录，就需要在在k个记录中寻找关键字值最小的那个记录，这要比个记录中寻找关键字值最小的那个记录，这要比2路归并路归并复杂些。如果逐个比较每个顺串的待选记录，从而选出一个复杂些。如果逐个比较每个顺串的待选记录，从而选出一个关键字值最小的记录，则每选取一个记录需要进行关键字值最小的记录，则每选取一个记录需要

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

13、的最小结点，即为下一个要输出的记录结点。这种选择树的构造可比作一种淘汰制的体育比赛，其中获胜者便是那的构造可比作一种淘汰制的体育比赛，其中获胜者便是那个具有较小关键字值的记录。个具有较小关键字值的记录。第10页，本讲稿共28页在非叶结点中，可以只存关键字值及指向相应记录的指针，在非叶结点中，可以只存关键字值及指向相应记录的指针，而不必存放整个记录内容。由于非叶结点总是代表优胜者，而不必存放整个记录内容。由于非叶结点总是代表优胜者，所以可以把这种树称为胜方树。所以可以把这种树称为胜方树。图图10.6 8路归并程序的选择树（胜方树）路归并程序的选择树（胜方树）图图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上的顺串上的顺串1和和T4上的顺串上的顺串2进行合并，并将进行合并

23、，并将结果放到结果放到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个顺串，每个个顺串，每个顺串的长度为顺串的长度为S。步骤步骤T1 T2 T3 说明说明初始分布

25、初始分布15 13 第一步后第一步后12 23 归并到归并到T3第二步后第二步后32 21 归并到归并到T2第三步后第三步后51 31 归并到归并到T1第四步后第四步后81 归并到归并到T3图图10.12 采用非采用非平衡分布法用三台磁带机实现平衡分布法用三台磁带机实现2路归并路归并第21页，本讲稿共28页讨论如何确定顺串初始分布的问题讨论如何确定顺串初始分布的问题 为了确定初始分布，就得从最后一步往前推。假为了确定初始分布，就得从最后一步往前推。假设有设有n步，我们希望步，我们希望n步之后在步之后在T1上正好有一个顺串，而上正好有一个顺串，而在在T2和和T3上没有顺串。要做到这点，则必须把上

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

27、推得过程。步骤步骤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 主要知识

28、点主要知识点基本概念：基本概念：外部排序：待排序的记录数外部排序：待排序的记录数n很大，内存容纳不下，必须很大，内存容纳不下，必须借用外部存储器才能完成的排序过程。借用外部存储器才能完成的排序过程。外存一般分为两类：顺序存取设备（如磁带存储器）、直外存一般分为两类：顺序存取设备（如磁带存储器）、直接存取设备（如磁盘存储器）。接存取设备（如磁盘存储器）。磁带的存取时间主要用在定位上，读写头与所需信息的磁带的存取时间主要用在定位上，读写头与所需信息的距离越远，定位时间就越长。距离越远，定位时间就越长。磁盘存储器（硬盘）特点：直接存取（随机存取），高速。磁盘存储器（硬盘）特点：直接存取（随机存取），

29、高速。磁盘存储单位：盘片组，柱面，磁道，扇段。磁盘存储单位：盘片组，柱面，磁道，扇段。外存中把若干个记录（逻辑记录）组合成页块（物理记录）外存中把若干个记录（逻辑记录）组合成页块（物理记录）进行存储。页块（进行存储。页块（1KB8KB）是内外存数据交换的基本）是内外存数据交换的基本单位：单位：内存缓冲区：暂存一个页块的内容。内存缓冲区：暂存一个页块的内容。第24页，本讲稿共28页外部排序的基本过程：外部排序的基本过程：（1）生成初始顺串；）生成初始顺串；（2）归并：对顺串反复进行归并，直至变成一个顺串。）归并：对顺串反复进行归并，直至变成一个顺串。初始顺串的生成方法：初始顺串的生成方法：内部排

30、序法。所生成顺串的大小正好等于一次能放入内存内部排序法。所生成顺串的大小正好等于一次能放入内存中的记录个数。中的记录个数。置换选择排序法。如果输入文件中的记录按其关键字随机置换选择排序法。如果输入文件中的记录按其关键字随机排列，则所生成的初始顺串的平均长度为内存工作区大小排列，则所生成的初始顺串的平均长度为内存工作区大小的的2倍。倍。归并方法：归并方法：二路归并法二路归并法多路归并方法（多路归并方法（1）：胜方树。了解胜方树的结构特点和）：胜方树。了解胜方树的结构特点和重构方法。重构方法。多路归并方法（多路归并方法（2）：败方树。了解败方树的结构特点和）：败方树。了解败方树的结构特点和重构方法

31、。重构方法。第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页