第10章外部排序ppt课件

1、第十章第十章 外部排序外部排序10.1 外存信息的特性外存信息的特性10.2 外排序的基本方法外排序的基本方法10.3 总结与提高总结与提高10.1 外存信息的特性外存信息的特性存储器存储器内部存储器内部存储器（内存）（内存）外部存储器外部存储器（外存）（外存）顺序存取设备磁带存储器）顺序存取设备磁带存储器）直接存取设备磁盘存储器）直接存取设备磁盘存储器）内存的存储容量小，但工作速度高；外存的存储容量大，内存的存储容量小，但工作速度高；外存的存储容量大，但速度较低。但速度较低。10.1.1 磁带存储器磁带存储器优点：存储容量大，使用方便，价格便宜。优点：存储容量大，使用方便，价格便宜。 1.

2、特性：磁带存储器主要由磁带、读写磁头和磁带驱动器特性：磁带存储器主要由磁带、读写磁头和磁带驱动器组成，如下图所示。组成，如下图所示。目前常用的典型磁带长目前常用的典型磁带长24002400英尺，宽英尺，宽0.50.5英寸，厚英寸，厚0.0020.002英寸。磁带表面上涂有磁性英寸。磁带表面上涂有磁性材料，可分为七道或九道磁材料，可分为七道或九道磁带。带。 七道磁带的每一横排中有六个二进制数据位和一个奇偶校七道磁带的每一横排中有六个二进制数据位和一个奇偶校验位。九道磁带的每一横排中有八个二进制数据位和一个验位。九道磁带的每一横排中有八个二进制数据位和一个奇偶校验位。这样的一排二进制数据位组成一个

3、字节。奇偶校验位。这样的一排二进制数据位组成一个字节。 2. 分页块存储方法分页块存储方法磁带存储器是一种典型的顺序存取设备。所谓顺序存取，磁带存储器是一种典型的顺序存取设备。所谓顺序存取，就是将记录在存储器上一个接一个地依次存放，为得到第就是将记录在存储器上一个接一个地依次存放，为得到第i i个记录，必须先读第个记录，必须先读第i-1i-1个记录。个记录。 由于磁带机不是连续运转的设备，而是一种启停设备，由于磁带机不是连续运转的设备，而是一种启停设备，所以在启停时间内，不能对磁带进行正常读写，因此磁带上所以在启停时间内，不能对磁带进行正常读写，因此磁带上的信息通常分为若干记录块，块与块之间留

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

5、序存取，又能进行直接存取随即存取），并且存取速度快。取），并且存取速度快。 1. 磁盘存储器的特性磁盘存储器的特性 磁盘存储器主要由磁盘组和磁盘驱动器组成。磁盘组磁盘存储器主要由磁盘组和磁盘驱动器组成。磁盘组由若干个盘片组成，每个盘片有上下两个面，盘面上涂有由若干个盘片组成，每个盘片有上下两个面，盘面上涂有光滑的磁性物质。光滑的磁性物质。 盘面上能够存储信息的盘面称为记录面。在记录盘面盘面上能够存储信息的盘面称为记录面。在记录盘面上有许多称为磁道的圆圈，信息就记载在磁道上。磁盘驱上有许多称为磁道的圆圈，信息就记载在磁道上。磁盘驱动器由主轴和读写磁头组成，每个盘面都配有一个读动器由主轴和读写磁头

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

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

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

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

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

11、用遍扫描。采用多路归并可以减少扫描遍数，如下图。多路归并可以减少扫描遍数，如下图。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 图10.5 16个顺串归并的示例 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 在在k k路归并中，为了确定下一个要输出的记录，就需要路归并中，为了确定下一个要输出的记录，就需要在在k k个记录中寻找关键字值最小的那个记录，这要比个记录中寻找关键字值最小的那个记录，这要比2 2路归并路归并复杂些。如果逐个比较每个顺串的待选记录，从而选出一个复杂些。如果逐个比较每个顺串的待选记录，从而选出一个关键字值最小

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

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

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

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

16、的结点，存放全局优胜者。优胜者。 图图10.8 对应于图对应于图10.6的败方树的败方树图图10.9 败方树的修改败方树的修改 在败方树中，当输出全局优胜者记录之后，对树的修改在败方树中，当输出全局优胜者记录之后，对树的修改比胜方树容易一些。修改过程如下：将新进入树的叶结点与比胜方树容易一些。修改过程如下：将新进入树的叶结点与父结点进行比较，大的存放在父结点，小的与上一级父结点父结点进行比较，大的存放在父结点，小的与上一级父结点再进行比较，此过程不断进行，直至到根，最后把新的全局再进行比较，此过程不断进行，直至到根，最后把新的全局优胜者存放到附加的结点优胜者存放到附加的结点 。 采用多路归并可

17、以减少对数据的扫描遍数从而减少了输采用多路归并可以减少对数据的扫描遍数从而减少了输入输出量。但也应该看到，若归并的路数入输出量。但也应该看到，若归并的路数k k增大时，缓冲增大时，缓冲区就要设置得比较大。区就要设置得比较大。 3. 初始顺串的生成初始顺串的生成其生成过程见下图。其生成过程见下图。输入文件输入文件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,

18、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 初始顺串的生成过程初始顺串的生成过程10.2.2 磁带排序磁带排序 磁带排序过程基本上与磁盘排序过程相同。首先对待排磁带排序过程基本上与磁盘排序过程相同。首先对待排序文件的

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

20、一个文件包含设有一个文件包含36003600个记录，现在要对其进行排序，个记录，现在要对其进行排序，可供使用的磁带机有四台，分别为可供使用的磁带机有四台，分别为T1T1、T2T2、T3T3、T4T4，可供排，可供排序用的内存空间包含存放序用的内存空间包含存放600600个记录的空间以及一些必要的工个记录的空间以及一些必要的工作区。设每个页块长为作区。设每个页块长为200200个记录。为了简化讨论，我们假定个记录。为了简化讨论，我们假定初始顺串的生成是采用通常的内排序方法实现的。这样，一初始顺串的生成是采用通常的内排序方法实现的。这样，一次可读入三个页块，对其进行排序并作为一个顺串输出。我次可读

21、入三个页块，对其进行排序并作为一个顺串输出。我们将采用们将采用2 2路归并的方法来实现顺串的归并，因而我们使用两路归并的方法来实现顺串的归并，因而我们使用两个输入缓冲区和一个输出缓冲区，每个缓冲区能容纳个输入缓冲区和一个输出缓冲区，每个缓冲区能容纳200200个记个记录。录。 排序过程的具体步骤如下排序过程的具体步骤如下 ：第一步：把输入文件分段每段包含第一步：把输入文件分段每段包含600个记录读入内存并个记录读入内存并进行内排序，生成初始顺串，然后将这些顺串轮流写到磁带进行内排序，生成初始顺串，然后将这些顺串轮流写到磁带机机T1和和T2上。上。 见图见图10.11(a)。图图10.11 磁带

22、排序过程磁带排序过程第二步：采用第二步：采用2路归并法对路归并法对T1上的各顺串与上的各顺串与T2上的上的各顺串进行归并，并把所产生的较大顺串轮流分布各顺串进行归并，并把所产生的较大顺串轮流分布到到T3和和T4上若输入文件带需要保留，则在第一步上若输入文件带需要保留，则在第一步完成后把输入文件带从完成后把输入文件带从T4上卸下来，换上工作带）。上卸下来，换上工作带）。见图见图10.11(b)。第三步：把第三步：把T3上的顺串上的顺串1和和T4上的顺串上的顺串2进行合并，进行合并，并将结果放到并将结果放到T1上。见图上。见图10.11(c)。第四步：把第四步：把T1T1上的顺串上的顺串1 1和和

23、T3T3上的顺串上的顺串3 3合并，并把合并，并把结果放到结果放到T2T2上，即为所要求的有序文件。上，即为所要求的有序文件。 2. 非平衡归并非平衡归并k路平衡归并的特点是：把要归并的顺串平衡均匀地路平衡归并的特点是：把要归并的顺串平衡均匀地分布到分布到k台输入带上。这样，为了避免对数据进行再台输入带上。这样，为了避免对数据进行再分配的扫描，就需要分配的扫描，就需要2k台磁带机，现采用非平衡归台磁带机，现采用非平衡归并，即不同输入带上的顺串个数不同，适当地对顺并，即不同输入带上的顺串个数不同，适当地对顺串进行非均匀分配，就可以用不到串进行非均匀分配，就可以用不到2k台磁带机来实台磁带机来实现

24、现 k路归并。路归并。 用用k+1k+1台磁带机便可取得台磁带机便可取得k k路归并的效果，我路归并的效果，我们以三台磁带机们以三台磁带机T1T1、T2T2、T3T3实现实现2 2路归并为例来说路归并为例来说明这个方法。明这个方法。 我们设初始顺串的长度为度量单位，即规定初我们设初始顺串的长度为度量单位，即规定初始顺串的长度为始顺串的长度为1 1，用，用SnSn来表示某台磁带机上有来表示某台磁带机上有n n个个顺串，每个顺串的长度为顺串，每个顺串的长度为S S。 步骤步骤 T1 T2 T3 说明说明初始分布初始分布 15 13 第一步后第一步后 12 23 归并到归并到T3第二步后第二步后 3

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

26、种顺串，并且个顺串加以归并来得到这种顺串，并且T2和和T3上没有别的顺上没有别的顺串，所以在第串，所以在第n-1步后，步后，T2和和T3上应各有一个顺串，上应各有一个顺串，T2上的上的顺串是从顺串是从T1和和T3中各取一个顺串加以归并后得到，因而，在中各取一个顺串加以归并后得到，因而，在第第n-2步后，在步后，在T1上应有一个顺串，在上应有一个顺串，在T3上应有两个顺串，上应有两个顺串，就这样一步一步往前推。就这样一步一步往前推。下图显示了这个前推得过程。下图显示了这个前推得过程。 步骤步骤 T1 T2 T3 n 1 0 0 n-1 0 1 1 n-2 1 0 2 n-3 3 2 0 n-4

27、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路归并的顺串分布路归并的顺串分布10.3 总结与提高总结与提高10.3.1 主要知识点主要知识点 基本概念：基本概念： 外部排序：待排序的记录数外部排序：待排序的记录数n很大，内存容纳不下，必须很大，内存容纳不下，必须借用外部

28、存储器才能完成的排序过程。借用外部存储器才能完成的排序过程。 外存一般分为两类：顺序存取设备如磁带存储器）、直外存一般分为两类：顺序存取设备如磁带存储器）、直接存取设备如磁盘存储器）。接存取设备如磁盘存储器）。 磁带的存取时间主要用在定位上，读写头与所需信息的磁带的存取时间主要用在定位上，读写头与所需信息的距离越远，定位时间就越长。距离越远，定位时间就越长。 磁盘存储器硬盘特点：直接存取随机存取），高速。磁盘存储器硬盘特点：直接存取随机存取），高速。 磁盘存储单位：盘片组，柱面，磁道，扇段。磁盘存储单位：盘片组，柱面，磁道，扇段。 外存中把若干个记录逻辑记录组合成页块物理记录外存中把若干个记录逻辑记录组合成页块物理记录进行存储。页块进行存储。页块1KB8KB是内外存数据交换