数据结构第10章

第10章外部排序10.1外存信息的特性

10.2外排序的基本方法10.1外存信息的特性10.1.1磁带存储器1.磁带存储器的特性图10.1磁带运行示意图目前常用的典型磁带长2400英尺1英尺=0.3048m，宽0.5英寸1英寸=0.0254m，厚0.002英寸。磁带表面上涂有磁性材料，可分为七道或九道磁带。七道磁带的每一横排中有六个二进制数据位和一个奇偶校验位。九道磁带的每一横排中有八个二进制数据位和一个奇偶校验位。这样的一排二进制数据位组成一个字节。磁带的存储密度（每英寸带面上所存放的字节数）通常为800字节／英寸和1600字节／英寸两种，走带速度为200英寸／s。磁带存储器是一种典型的顺序存取设备。所谓顺序存取，就是将记录在存储器上一个接一个地依次存放，为得到第i个记录，必须先读第i-1个记录。磁带的存取时间主要用在定位上（即把磁带转到待读／写信息所在的物理位置上），读／写头与所需信息的距离越远，定位时间就越长，一般情况下，定位时间为20毫秒至数分钟。当磁带转到信息所在位置上时才开始真正读写数据。磁带的读写速度由走带速度和存储密度所决定，对于存储密度为800字节／英寸的磁带来说，每秒钟约可写800×200＝160000字节。由于磁带机不是连续运转的设备，而是一种启停设备，因而磁带的运转从静止到达正常的走带速度以及从正常运转到达停止都需要一定的时间。在启停时间内，不能对磁带进行正常读写，因此磁带上的信息通常分为若干记录块，块与块之间留有一定的间隙，该间隙一般为1/4～3/4英寸。2.分页块存储方法为了减少存储空间的浪费，通常采用把若干个记录组合成页块进行存储的办法，将记录间的间隙变成页块间的间隙。一般情况下，可以把记录称为逻辑记录，而把逻辑记录组合成的页块称为物理记录。对于上述例子，如果将100个记录作为一个页块，则存放1000个记录仅需长度为1000×0.05＋1000×0.6/100=56英寸显然，采用分页块存储法后，可以大大节省存储空间，而且页块越大，浪费间隙的空间越小。但是这并不等于说页块越大越好，原因是采用分页块存储后，内外存数据交换的基本单位为页块，而不是记录，因此需要在内存中开辟一个数据缓冲区来暂存一个页块的内容，以便进行输入输出操作。页块越大，则要求缓冲区越大，这势必会过多地占用内存空间，造成读写时间过长、出错概率过大等一系列的问题，所以应适当地选择页块的大小。通常一个页块取1KB～8KB为宜。10.1.2磁盘存储器1.磁盘存储器的特性磁盘存储器主要由磁盘组和磁盘驱动器组成。磁盘组由若干个盘片组成，每个盘片有上下两个面，盘面上涂有光滑的磁性物质。以6片盘组为例，由于最顶上和最底下盘片的外侧面不能使用，所以总共只有10个面可用来保存信息，能够存储信息的盘面称为记录面。在记录盘面上有许多称为磁道的圆圈，信息就记载在磁道上。磁盘驱动器由主轴和读／写磁头组成，每个盘面都配有一个读／写磁头。图10.2活动臂示意图活动臂磁盘的磁头是安装在一个可活动臂上，随着活动臂的移动，磁头可在盘面上做同步的径向移动，从一个磁道移到另一个磁道，当盘面高速旋转，磁道在读／写头下通过时，便可进行信息的读写。各记录盘面上半径相同的磁道合在一起称为一个柱面，柱面上各磁道在同一磁头位置下，即活动臂移动时，实际上是把这些磁头从一个柱面移到另一个柱面。一个磁道内还可以分为若干段，称为扇段。因此，对磁盘存储来说，由大到小的存储单位是：盘片组，柱面，磁道，扇段。以IBM2314型磁盘为例，其参数为：20个记录面／磁盘组，200个磁道／记录面，7294字节／磁道。因此，整个盘片组的容量为：7294×200×200≈29MB。磁盘的存取时间主要取决于寻查时间和等待时间。磁盘以2400～3600r/min的速度旋转，因此平均等待时间约为10ms～20ms，而平均寻查时间约为几毫秒至几十毫秒，这与CPU的处理速度相比较而言，仍是很慢的。因此，在讨论外存的数据结构及其上的操作时，要尽量设法减少访问外存的次数，以提高磁盘存取效率。2.分页块存储法为了减少访问外存的次数，一般采用把记录组合成页块的方式来进行内外存数据的交换。一个页块（简称块）是磁盘上的一个物理记录，通常可以容纳多个逻辑记录，内存中设置的缓冲区应该与页块的大小相等。每次访问记录时，需要把一个页块读入一个缓冲区或者把一个缓冲区的数据写到一个页块。由于在这种方式下仅当一个页块中的记录已处理完，接着将处理下一页的记录时才需要再次访问外存，因而大大提高了处理效率。分页块存储方法被广泛采用。10.2外排序的基本方法10.2.1磁盘排序1.磁盘排序的例子假设磁盘上存有一文件，共有3600个记录（A1,A2,A3600），页块长为200个记录，供排序使用的缓冲区可提供容纳600个记录的空间，现要对该文件进行排序，排序过程可按如下步骤进行：第一步，每次将三个页块（600个记录）由外存读到内存，进行内排序，整个文件共得到6个初始顺串R1~R6（每一个顺串占三个页块），然后把它们写回到磁盘上去，如图10.3所示。图10.3内排序后得到的初始顺串第二步图10.46个顺串的归并过程从以上归并过程可见，扫描遍数对于归并过程所需要的时间起着关键的作用，在上例中，除了在内排序形成初始顺串时需作一遍扫描外，各顺串的归并还需遍扫描把6个长为600个记录的顺串归并为3个长为1200个记录的顺串需要扫描一遍；把两个长为1200个记录的顺串归并为一个长为2400个记录的顺串需要扫描2/3遍,把一个长为2400个记录的顺串与另一个长为1200个记录的顺串归并在一起，需要扫描一遍。2.多路归并图10.516个顺串归并的示例图10.68路归并程序的选择树(胜方树)图10.7胜方树的修改图10.8对应于图10.6的败方树图10.9败方树的修改3.初始顺串的生成图10.10初始顺串的生成过程输入文件:10,9,20,6,8,12,90,1714,22,7,24,15,16,11,100,13,18,26,38,30,25,50,28,110,21,40,19,…a输入文件,每个记录只列出其关键字值图10.10初始顺串的生成过程初始顺串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)生成的初始顺串图10.10初始顺串的生成过程©包含8个记录的败方树,并列出了新进入败方树的各记录的结点位置及进入的次序,用符号√表示该记录不属于当前的初始顺串10.2.2磁带排序1.磁带排序的例子设有一个文件包含3600个记录，现在要对其进行排序，可供使用的磁带机有四台，分别为T1、T2、T3、T4，可供排序用的内存空间包含存放600个记录的空间以及一些必要的工作区设每个页块长为200个记录。为了简化讨论，我们假定初始顺串的生成是采用通常的内排序方法实现的。这样，一次可读入三个页块，对其进行排序并作为一个顺串输出。我们将采用2路归并的方法来实现顺串的归并，因而我们使用两个输入缓冲区和一个输出缓冲区，每个缓冲区能容纳200个记录。排序过程的具体步骤如下（假设必要的磁带反绕动作已经隐含并设输入文件在磁带机T4上）：图10.11磁带排序过程2.非平衡归并设初始顺串的长度为度量单位，即规定初始顺串的长度为1，用Sn来表示某台磁带机上有n个顺串，每个顺串的长度为S。假设初始顺串有八个，则在T1上分配五个顺串，在T2上分配三个顺串，然后把T2上的三个顺串与T1中的三个顺串相归并，得到三个长度为2的顺串，将它们写到T3上。下一步把T1中的两个顺串与T3中的两个顺串相归并，得到两个长度为3的顺串，把它们写到T2上。再下一步是把T3上一个长度为2的顺串与