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