[其它]数据结构第10章.ppt

第10章 外部排序,10.1 外存信息的特性 10.2 外排序的基本方法,10.1 外存信息的特性,10.1.1 磁带存储器 1.磁带存储器的特性 磁带存储器主要由磁带、读写磁头和磁带驱动器组成，如图10.1所示。磁带卷在带盘上，带盘安装在磁带驱动器的转轴上，当转轴正向转动时，磁带通过读写磁头，就可进行磁带信息的读写操作。,图10.1 磁带运行示意图,目前常用的典型磁带长2400英尺1英尺=0.3048 m，宽0.5英寸1英寸=0.0254 m，厚0.002英寸。磁带表面上涂有磁性材料，可分为七道或九道磁带。七道磁带的每一横排中有六个二进制数据位和一个奇偶校验位。九道磁带的每一横排中有八个二进制数据位和一个奇偶校验位。这样的一排二进制数据位组成一个字节。磁带的存储密度（每英寸带面上所存放的字节数）通常为800字节英寸和1600字节英寸两种，走带速度为200英寸s。,磁带存储器是一种典型的顺序存取设备。所谓顺序存取，就是将记录在存储器上一个接一个地依次存放，为得到第i个记录， 必须先读第i-1个记录。磁带的存取时间主要用在定位上（即把磁带转到待读写信息所在的物理位置上），读写头与所需信息的距离越远，定位时间就越长，一般情况下，定位时间为20毫秒至数分钟。当磁带转到信息所在位置上时才开始真正读写数据。磁带的读写速度由走带速度和存储密度所决定， 对于存储密度为800字节英寸的磁带来说，每秒钟约可写800200160 000字节。由于磁带机不是连续运转的设备，而是一种启停设备，因而磁带的运转从静止到达正常的走带速度以及从正常运转到达停止都需要一定的时间。 在启停时间内，不能对磁带进行正常读写，因此磁带上的信息通常分为若干记录块，块与块之间留有一定的间隙，该间隙一般为1/43/4英寸。,2. 分页块存储方法,为了减少存储空间的浪费，通常采用把若干个记录组合成页块进行存储的办法，将记录间的间隙变成页块间的间隙。一般情况下，可以把记录称为逻辑记录，而把逻辑记录组合成的页块称为物理记录。对于上述例子，如果将100个记录作为一个页块，则存放1000个记录仅需长度为,10000.0510000.6/100=56英寸,显然，采用分页块存储法后，可以大大节省存储空间，而且页块越大，浪费间隙的空间越小。但是这并不等于说页块越大越好，原因是采用分页块存储后，内外存数据交换的基本单位为页块，而不是记录，因此需要在内存中开辟一个数据缓冲区来暂存一个页块的内容，以便进行输入输出操作。 页块越大，则要求缓冲区越大，这势必会过多地占用内存空间，造成读写时间过长、出错概率过大等一系列的问题， 所以应适当地选择页块的大小。 通常一个页块取1 KB8 KB为宜。,10.1.2 磁盘存储器,1. 磁盘存储器的特性 磁盘存储器主要由磁盘组和磁盘驱动器组成。磁盘组由若干个盘片组成，每个盘片有上下两个面，盘面上涂有光滑的磁性物质。以6片盘组为例，由于最顶上和最底下盘片的外侧面不能使用，所以总共只有10个面可用来保存信息，能够存储信息的盘面称为记录面。在记录盘面上有许多称为磁道的圆圈，信息就记载在磁道上。磁盘驱动器由主轴和读写磁头组成，每个盘面都配有一个读写磁头。,图10.2 活动臂示意图,活动臂磁盘的磁头是安装在一个可活动臂上，随着活动臂的移动， 磁头可在盘面上做同步的径向移动，从一个磁道移到另一个磁道， 当盘面高速旋转，磁道在读写头下通过时，便可进行信息的读写。各记录盘面上半径相同的磁道合在一起称为一个柱面， 柱面上各磁道在同一磁头位置下，即活动臂移动时，实际上是把这些磁头从一个柱面移到另一个柱面。 一个磁道内还可以分为若干段，称为扇段。因此，对磁盘存储来说，由大到小的存储单位是： 盘片组，柱面，磁道，扇段。以IBM2314型磁盘为例，其参数为：20个记录面磁盘组，200个磁道记录面，7294字节磁道。因此，整个盘片组的容量为： 729420020029 MB。,磁盘的存取时间主要取决于寻查时间和等待时间。 磁盘以24003600 r/min的速度旋转，因此平均等待时间约为10 ms20 ms， 而平均寻查时间约为几毫秒至几十毫秒，这与CPU的处理速度相比较而言，仍是很慢的。因此，在讨论外存的数据结构及其上的操作时，要尽量设法减少访问外存的次数， 以提高磁盘存取效率。,2. 分页块存储法 为了减少访问外存的次数，一般采用把记录组合成页块的方式来进行内外存数据的交换。一个页块（简称块）是磁盘上的一个物理记录， 通常可以容纳多个逻辑记录， 内存中设置的缓冲区应该与页块的大小相等。每次访问记录时，需要把一个页块读入一个缓冲区或者把一个缓冲区的数据写到一个页块。由于在这种方式下仅当一个页块中的记录已处理完， 接着将处理下一页的记录时才需要再次访问外存，因而大大提高了处理效率。 分页块存储方法被广泛采用。,10.2 外排序的基本方法,10.2.1 磁盘排序,1. 磁盘排序的例子 假设磁盘上存有一文件，共有3600个记录（A1, A2, A3600），页块长为200个记录，供排序使用的缓冲区可提供容纳600个记录的空间，现要对该文件进行排序，排序过程可按如下步骤进行： 第一步，每次将三个页块（600个记录）由外存读到内存， 进行内排序，整个文件共得到6个初始顺串R1R6 （每一个顺串占三个页块），然后把它们写回到磁盘上去，如图10.3所示。,图10.3 内排序后得到的初始顺串,第二步，将供内排序使用的内存缓冲区分为三块相等的部分（即每块可容纳200个记录），其中两块作为输入缓冲区，一块作为输出缓冲区，然后对各顺串进行两路归并。首先归并R1和R2这两个顺串中各自的第一个页块并分别读入到两个缓冲区中，进行归并后送入输出缓冲区。当输出缓冲区装满200个记录时，就把它写回磁盘；如果归并期间某个输入缓冲区空了，便立即读入同一顺串中的下一个页块，继续进行归并，此过程不断进行，直到顺串R1和顺串R2归并为一个新的顺串为止。这个经归并后的新的顺串含有1200个记录。,在R1和R2归并完成之后，再归并R3和R4，最后归并R5和R6。到此为止，完成了对整个文件的一遍扫描，这意味着文件中的每一个记录被读写一次（即从磁盘上读入内存一次，并从内存写到磁盘一次）。经一遍扫描后形成了三个顺串，每个顺串含有6个页块（共1200个记录）。利用上述方 法，再对这三个顺串进行归并，即先将其中的两个顺串归并起来，结果得到一个含有2400个记录的顺串；然后再把该顺串和剩下的另一个含有1200个记录的顺串进行归并，从而得到最终的一个顺串，即为所要求的排序的文件。图10.4给出了这个归并过程。,图10.4 6个顺串的归并过程,从以上归并过程可见，扫描遍数对于归并过程所需要的时间起着关键的作用，在上例中，除了在内排序形成初始顺串时需作一遍扫描外，各顺串的归并还需 遍扫描 把6个长为600个记录的顺串归并为3个长为1200个记录的顺串需要扫描一遍；把两个长为1200个记录的顺串归并为一个长为2400个记录的顺串需要扫描2/3遍, 把一个长为2400个记录的顺串与另一个长为1200个记录的顺串归并在一起， 需要扫描一遍。,2. 多路归并,图10.5 16个顺串归并的示例,图10.6 8路归并程序的选择树(胜方树),图10.7 胜方树的修改,图10.8 对应于图10.6的败方树,图10.9 败方树的修改,3. 初始顺串的生成 假定内存中可以存放k个记录及在此基础上所构成的败方树，并且输入输出操作是通过输入输出缓冲区进行的。败方树方法的基本思路如下：从输入文件中取k个记录，并在此基础上建立败方树，将全局优胜者送入当前的初始顺串，并从输入文件中取下一个记录进入败方树以替代刚输入的记录结点位置。若新进入败方树的记录的关键字值小于已输出记录的关键字值，则该新进入的记录不属于当前初始顺串，而属于下一个初始顺串，因而不再参加比赛，实际上可把它看作在比赛中始终为败方，这样就不会送到当前的初始顺串中，其它（属于当前初始顺串）的记录继续进行比赛；若新进入败方树的记录的关键字值大于或等于已输出记录的关键字值，则该新进入的记录属于当前初始顺串，与其它记录继续进行比赛，比赛不断进行，直至败方树中的k个记录都已不属于当前初始顺串，于是当前初始顺串生成结束，开始生成下一个初始顺串（即把下一个初始顺串称为当前初始顺串）。这时败方树中的k个记录重新开始比赛，这k个记录都属于新的当前初始顺串，因而都参加比赛。就这样，一个初始顺串接一个初始顺串地生成，直至输入文件的所有记录取完为止。,图10.10 初始顺串的生成过程,10.2.2 磁带排序,1. 磁带排序的例子 设有一个文件包含3600个记录，现在要对其进行排序， 可供使用的磁带机有四台， 分别为T1、T2、T3、T4，可供排序用的内存空间包含存放600个记录的空间以及一些必要的工作区设每个页块长为200个记录。为了简化讨论，我们假定初始顺串的生成是采用通常的内排序方法实现的。这样，一次可读入三个页块， 对其进行排序并作为一个顺串输出。我们将采用2路归并的方法来实现顺串的归并，因而我们使用两个输入缓冲区和一个输出缓冲区，每个缓冲区能容纳200个记录。排序过程的具体步骤如下（假设必要的磁带反绕动作已经隐含 并设输入文件在磁带机T4上）：,图10.11 磁带排序过程,第一步：把输入文件分段（每段包含600个记录）读入内存并进行内排序，生成初始顺串，然后将这些顺串轮流写到磁带机T1和T2上。完成此步骤后的磁带机的状况如图10.11（a）所示。 第二步：采用2路归并法对T1上的各顺串与T2上的各顺串进行归并，并把所产生的较大顺串轮流分布到T3和T4上（若输入文件带需要保留，则在第一步完成后把输入文件带从T4上卸下来，换上工作带）。此步之后的磁带机状况如图10.11（b）所示。其中T3上的顺串1是T1上的顺串1和T2上的顺串2合并的结果，T3上的顺串3是T1上的顺串5和T2上的顺串6合并的结果，T4上的顺串2是T1上的顺串3和T2上的顺串4合并的结果。,第三步：把T3上的顺串1和T4上的顺串2进行合并，并将结果放到T1上。此步之后的磁带状况如图10.11（c）所示。 第四步：把T1上的顺串1和T3上的顺串3合并，并把结果放到T2上，即为所要求的有序文件。,上述例子采用的是2路归并法，与磁盘排序的情况一样，排序的时间主要取决于对数据的扫描遍数。采用多路归并能减少扫描的遍数，但对磁带排序来说，多路归并需要多台磁带机，为了避免过多的磁带寻找时间，要归并的顺串需要放在不同的磁带上。因此，k路归并至少需要k+1台磁带机，其中k台作为输入带，另外一台用于归并后存放输出结果。但这样需要对输出带再作一遍扫描，把输出带上的各顺串重新分配到k台磁带上，以便作为下一级归并 使用。若使用2k台磁带机，则可避免这种再分配扫描，把k台作为输入带，其余k台作为输出带，在下一级归并时，输入带与输出带的作用互相对换。上述例子就是用4台磁带机实现2路归并，T1、T2和T3、T4轮流地用作输入带和输出带。,2. 非平衡归并,设初始顺串的长度为度量单位，即规定初始顺串的长度为1，用Sn来表示某台磁带机上有n个顺串，每个顺串的长度为S。 假设初始顺串有八个，则在T1上分配五个顺串，在T2上分配三个顺串，然后把T2上的三个顺串与T1中的三个顺串相归并，得到三个长度为2的顺串，将它们写到T3上。下一步把T1中的两个顺串与T3中的两个顺串相归并，得到两个长度为3的顺串，把它们写到T2上。再下一步是把T3上一个长度为2的顺串与T2中的一个长度为3的顺串进行归并，得到一个长度为5的顺串，将其写到T1上。最后，把T1上一个长度为5的顺串与T2上一个长度为3的顺串进行归并，得到一个长度为8的顺串，把它写到T3上。至此，完成了非平衡2路归并排序。,图10.12 采用非平衡分布法用三台磁带机实现2路归并,下面我们来讨论如何确定顺串初始分布的问题。为了确定初始分布，就得从最后一步往前推。假设有n步，我们希望n步之后在T1上正好有一个顺串，