殷人昆 数据结构VIP免费

第十章文件、外部排序与搜索清华大学计算机系殷人昆主存储器和外存储器文件组织外排序多级索引结构可扩充散列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个字符的逻辑记录放在一个块内，此块的长度将达到5080/1600=2.5英寸，存储利用率达到0.77。因此在磁带上采用按块读写。在磁带设备上读写一块信息所用时间tIO=ta+tb其中，ta是延迟时间，即读写磁头到达待读写块开始位置所需花费的时间，它与当前读写磁头所在位置有关。tb是对一个块进行读写所用时间，它等于数据传输时间加上IBG时间。磁带设备只能用于处理变化少，只进行顺序存取的大量数据。磁盘（disc）磁盘存储器通常称为直接存取设备，或随机存取设备，它访问外存上文件的任一记录的时间几乎相同。磁盘存储器可以顺序存取，也可以随机存取。目前使用较多的是活动臂硬盘组：若干盘片构成磁盘组，它们安装在主轴上，在驱动装置的控制下高速旋转。除了最上面一个盘片和最下面一个盘片的外侧盘面不用以外，其他每个盘片上下两面都可存放数据。将这些可存放数据的盘面称为记录盘面。主轴盘片活动臂（回转臂）读写磁头磁道柱面每个记录盘面上有很多磁道，数据就存放在这些磁道上。它们在记录盘面上形成一个个同心圆。每个记录盘面都有一个读写磁头。所有记录盘面的读写磁头都安装在同一个动臂上，随动臂向内或向外做径向移动，从一个磁道移到另一个磁道。任一时刻，所有记录盘面的读写磁头停留在各个记录盘面的半径相同的磁道上。运行时，由于盘面做高速旋转，磁头所在的磁道上的数据相继在磁头下，从而可以读写数据各个记录盘面上半径相同的磁道合在一起称为柱面。动臂的移动实际上是将磁头从一个柱面移动到另一个柱面上。一个磁道可以划分为若干段，称为扇区，一个扇区就是一次读写的最小数据量。这样，对磁盘存储器来说，从大到小的存储单位是：盘片组、柱面、磁道和扇区。对磁盘存储器进行一次存取所需时间：1.当有多个盘片组时，要选定某个盘片组。这是由电子线路实现的，速度很...