第十章文件、外部排序与搜索清华大学计算机系殷人昆主存储器和外存储器文件组织外排序多级索引结构可扩充散列Trie树第十章文件、外部排序与外部搜索主存储器与外部存储器外存储器与内存储器相比，优点是：价格较低永久的存储能力缺点：访问外存储器上的数据比访问内存要慢5～6个数量级要求我们在开发系统时必须考虑如何使外存访问次数达到最少。磁带（tape）磁带是一种顺序存取设备。磁带主要用于备份、存储不经常使用的数据，以及作为将数据从一个系统转移到另一个系统的脱机介质。读出头写入头磁带送带盘卷带盘磁带卷在一个卷盘上，运行时磁带经过读写磁头，把磁带上的信息读入计算机，或者把计算机中的信息写到磁带上去。数据记录在磁带带面上。在带面上并列存放有9个磁道的信息，即每一横排有9位二进制信息：8位数据加1位奇偶校验位。磁带的存储密度用BPI（BitPerInch）为单位，典型的存储密度有3种：6250BPI（=246排/mm）、1600BPI（=64排/mm）、800BPI（32排/mm）。正常走带速度为3～5m/Sec，因设备而异。数据的传送速度=存储密度走带速度／读写时间。在应用中使用文件进行数据处理的基本单位叫做逻辑记录，简称为记录；在磁带上物理地存储的记录叫做物理记录。在使用磁带或磁盘存放逻辑记录时，常常把若干个逻辑记录打包进行存放，把这个过程叫做“块化”（blocking）。经过块化处理的物理记录叫做块化记录。磁带设备是一种启停设备。磁带每次启停都有一个加速与减速的过程，在这段时间内走带不稳定，只能走空带，这段空带叫做记录间间隙IRG（InterRecordGap）或者块间间隙IBG（InterBlockGap），其长度因设备而异。磁带速度75-200英寸/秒传输速度7000-1250000字/秒1.5-16ms1.5-16ms定速加速IBG0.3～0.75英寸减速物理记录启动位置IBG0.3～0.75英寸停止位置传输开始传输完成经过时间如果每个逻辑记录是80个字符，IRG为0.75英寸，则对存储密度为1600BPI的磁带，一个逻辑记录仅占80/1600=1/20英寸。每传输一个逻辑记录磁带走过0.05英寸，接着磁带要走过一个IRG占0.75英寸。结果大部分时间都花费在走空带上，存储利用率只有1/16。如果将若干逻辑记录存放于一个块，将IRG变成IBG，可以提高存储利用率。例如，将50个有80个字符的逻辑记录放在一个块内，此块的长度将达到5080/1600=2.5英寸，存储利用率达到0.77。因此在磁带上采用按块读写。在磁带设备上读写一块信息所用时间tIO=ta+tb其中，ta是延迟时间，即读写磁头到达待读写块开始位置所需花费的时间，它与当前读写磁头所在位置有关。tb是对一个块进行读写所用时间，它等于数据传输时间加上IBG时间。磁带设备只能用于处理变化少，只进行顺序存取的大量数据。磁盘（disc）磁盘存储器通常称为直接存取设备，或随机存取设备，它访问外存上文件的任一记录的时间几乎相同。磁盘存储器可以顺序存取，也可以随机存取。目前使用较多的是活动臂硬盘组：若干盘片构成磁盘组，它们安装在主轴上，在驱动装置的控制下高速旋转。除了最上面一个盘片和最下面一个盘片的外侧盘面不用以外，其他每个盘片上下两面都可存放数据。将这些可存放数据的盘面称为记录盘面。主轴盘片活动臂（回转臂）读写磁头磁道柱面每个记录盘面上有很多磁道，数据就存放在这些磁道上。它们在记录盘面上形成一个个同心圆。每个记录盘面都有一个读写磁头。所有记录盘面的读写磁头都安装在同一个动臂上，随动臂向内或向外做径向移动，从一个磁道移到另一个磁道。任一时刻，所有记录盘面的读写磁头停留在各个记录盘面的半径相同的磁道上。运行时，由于盘面做高速旋转，磁头所在的磁道上的数据相继在磁头下，从而可以读写数据各个记录盘面上半径相同的磁道合在一起称为柱面。动臂的移动实际上是将磁头从一个柱面移动到另一个柱面上。一个磁道可以划分为若干段，称为扇区，一个扇区就是一次读写的最小数据量。这样，对磁盘存储器来说，从大到小的存储单位是：盘片组、柱面、磁道和扇区。对磁盘存储器进行一次存取所需时间：1.当有多个盘片组时，要选定某个盘片组。这是由电子线路实现的，速度很...
