《外部排序》课件

《《外部排序》课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第十章外部排序10.1外存信息的特性10.2外排序的基本方法10.3总结与提高10.1外存信息的特性存储器内部存储器（内存）外部存储器（外存）顺序存取设备（磁带存储器）直接存取设备（磁盘存储器）内存的存储容量小，但工作速度高；外存的存储容量大，但速度较低。10.1.1磁带存储器优点：存储容量大，使用方便，价格便宜。1.特性：磁带存储器主要由磁带、读／写磁头和磁带驱动器组成，如下图所示。目前常用的典型磁带长2400英尺，宽0.5英寸，厚0.002英寸。磁带表面上涂有磁性材料，可分为七道或九道磁带。七道磁带的每一横排中有六个二进制数据位和一个奇偶校验位。九道磁带的每一横排中有八个二进制数

2、据位和一个奇偶校验位。这样的一排二进制数据位组成一个字节。2.分页块存储方法磁带存储器是一种典型的顺序存取设备。所谓顺序存取，就是将记录在存储器上一个接一个地依次存放，为得到第i个记录，必须先读第i-1个记录。由于磁带机不是连续运转的设备，而是一种启停设备，所以在启停时间内，不能对磁带进行正常读写，因此磁带上的信息通常分为若干记录块，块与块之间留有一定的间隙，该间隙一般为1/4～3/4英寸。由上可知，用磁带存储信息时需要在每段信息之间留有空隙，且此空隙占用了大量的存储空间。为了减少存储空间的浪费，通常采用把若干个记录组合成页块进行存储的办法，将记录间的间隙变成页块间的间隙。10.1.

3、2磁盘存储器优点：既能进行顺序存取，又能进行直接存取（随即存取），并且存取速度快。1.磁盘存储器的特性磁盘存储器主要由磁盘组和磁盘驱动器组成。磁盘组由若干个盘片组成，每个盘片有上下两个面，盘面上涂有光滑的磁性物质。盘面上能够存储信息的盘面称为记录面。在记录盘面上有许多称为磁道的圆圈，信息就记载在磁道上。磁盘驱动器由主轴和读／写磁头组成，每个盘面都配有一个读／写磁头。磁盘可分为固定臂盘和活动臂盘两种。固定臂盘的每个盘面的每一磁道上都有独立的磁头，它是固定不动的，专门负责读写某一磁道上的信息。如图：2.分页块存储法为了减少访问外存的次数，一般采用把记录组合成页块的方式来进行内外存数据的交

4、换。一个页块（简称块）是磁盘上的一个物理记录，通常可以容纳多个逻辑记录，内存中设置的缓冲区应该与页块的大小相等。每次访问记录时，需要把一个页块读入一个缓冲区或者把一个缓冲区的数据写到一个页块。10.2外排序的基本方法最常用的外部排序方法是归并排序法。这种方法由两个阶段组成：第一阶段是把文件逐段输入到内存，用有效的内排序方法对文件的各个段进行排序，经排序的文件段称为顺串（或归并段），当它们生成后立即写到外存上，这样在外存上就形成了许多初始顺串；第二阶段是对这些顺串用某种归并方法（如2路归并法）进行多边归并，使顺串的长度逐渐由小至大，直至变成一个顺串，即整个文件有序为止。10.2.1磁盘

5、排序1.例子：假设磁盘上存有一文件，共有3600个记录（A1,A2,…,A3600），页块长为200个记录，供排序使用的缓冲区可提供容纳600个记录的空间，现要对该文件进行排序，排序过程可按如下步骤进行：第一步：每次将三个页块（600个记录）由外存读到内存，进行内排序，整个文件共得到6个初始顺串R1~R6（每一个顺串占三个页块），然后把它们写回到磁盘上去。内排序后得到的初始顺串见p260的图10.3所示。第二步：将供内排序使用的内存缓冲区分为三块相等的部分（即每块可容纳200个记录），其中两块作为输入缓冲区，一块作为输出缓冲区，然后对各顺串进行两路归并。归并过程见p261的图10.4

6、所示。2.多路归并一般说来，如果初始顺串有m个，则如图10.4所示那样的归并树就有[log2m]+1层，要对数据进行[log2m]遍扫描。采用多路归并可以减少扫描遍数，如图所示。12345678910111213141516图10.516个顺串归并的示例12345678910111213141516在k路归并中，为了确定下一个要输出的记录，就需要在k个记录中寻找关键字值最小的那个记录，这要比2路归并复杂些。如果逐个比较每个顺串的待选记录，从而选出一个关键字值最小的记录，则每选取一个记录需要进行k-1次比较。为了减少这个代价，我们可采用下面介绍的选择树的方法来实现k路归并。选择树是一种

7、完全二叉树，下图显示了8路归并的选择树，其中叶结点为各顺串在归并过程中的当前记录（图中标出了它们各自的关键字值），其它每个结点都代表其两个子结点中（关键字值）较小的一个。因此根结点是树中的最小结点，即为下一个要输出的记录结点。这种选择树的构造可比作一种淘汰制的体育比赛，其中获胜者便是那个具有较小关键字值的记录。在非叶结点中，可以只存关键字值及指向相应记录的指针，而不必存放整个记录内容。由于非叶结点总是代表优胜者，所以可以把这种树称为胜方树。图10.68路归