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

* 第10章 外部排序 第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字节／英寸的磁带来说，每秒钟约可写800×200＝160 000字节。由于磁带机不是连续运转的设备，而是一种启停设备，因而磁带的运转从静止到达正常的走带速度以及从正常运转到达停止都需要一定的时间。 在启停时间内，不能对磁带进行正常读写，因此磁带上的信息通常分为若干记录块，块与块之间留有一定的间隙，该间隙一般为1/4～3/4英寸。 2. 分页块存储方法 为了减少存储空间的浪费，通常采用把若干个记录组合成页块进行存储的办法，将记录间的间隙变成页块间的间隙。一般情况下，可以把记录称为逻辑记录，而把逻辑记录组合成的页块称为物理记录。对于上述例子，如果将100个记录作为一个页块，则存放1000个记录仅需长度为 1000×0.05＋1000×0.6/100=56英寸 显然，采用分页块存储法后，可以大大节省存储空间，而且页块越大，浪费间隙的空间越小。但是这并不等于说页块越大越好，原因是采用分页块存储后，内外存数据交换的基本单位为页块，而不是记录，因此需要在内存中开辟一个数据缓冲区来暂存一个页块的内容，以便进行输入输出操作。 页块越大，则要求缓冲区越大，这势必会过多地占用内存空间，造成读写时间过长、出错概率过大等一系列的问题， 所以应适当地选择页块的大小。 通常一个页块取1 KB～8 KB为宜。 10.1.2 磁盘存储器 1. 磁盘存储器的特性 磁盘存储器主要由磁盘组和磁盘驱动器组成。磁盘组由若干个盘片组成，每个盘片有上下两个面，盘面上涂有光滑的磁性物质。以6片盘组为例，由于最顶上和最底下盘片的外侧面不能使用，所以总共只有10个面可用来保存信息，能够存储信息的盘面称为记录面。在记录盘面上有许多称为磁道的圆圈，信息就记载在磁道上。磁盘驱动器由主轴和读／写磁头组成，每个盘面都配有一个读／写磁头。 图10.2 活动臂示意图 活动臂磁盘的磁头是安装在一个可活动臂上，随着活动臂的移动， 磁头可在盘面上做同步的径向移动，从一个磁道移到另一个磁道， 当盘面高速旋转，磁道在读／写头下通过时，便可进行信息的读写。各记录盘面上半径相同的磁道合在一起称为一个柱面， 柱面上各磁道在同一磁头位置下，即活动臂移动时，实际上是把这些磁头从一个柱面移到另一个柱面。 一个磁道内还可以分为若干段，称为扇段。因此，对磁盘存储来说，由大到小的存储单位是： 盘片组，柱面，磁道，扇段。以IBM2314型磁盘为例，其参数为：20个记录面／磁盘组，200个磁道／记录面，7294字节／磁道。因此，整个盘片组的容量为： 7294×200×200≈29 MB。 磁盘的存取时间主要取决于寻查时间和等待时间。 磁盘以2400～3600 r/min的速度旋转，因此平均等待时间约为10 ms～20 ms， 而平均寻查时间约为几毫秒至几十毫秒，这与CPU的处理速度相比较而言，仍是很慢的。因此，在讨论外存的数据结构及其上的操作时，要尽量设法减少访问外存的次数， 以提高磁盘存取效率。 2. 分页块存储法 为了减少访问外存的次数，一般采用把记录组合成页块的方式来进行内外存数据的交换。一个