第10章文件、外部排序与有哪些信誉好的足球投注网站详解.ppt

第十章 文件、外部排序与有哪些信誉好的足球投注网站 清华大学计算机系 第十章 文件、外部排序与外部有哪些信誉好的足球投注网站 主存储器和外存储器 文件组织 外排序 多级索引结构 可扩充散列 Trie树 主存储器与外部存储器 外存储器与内存储器相比，优点是： 价格较低 永久的存储能力 缺点： 访问外存储器上的数据比访问内存要慢5～6个数量级 要求我们在开发系统时必须考虑如何使外存访问次数达到最少。 磁带（tape） 磁带是一种顺序存取设备。 磁带主要用于备份、存储不经常使用的数据，以及作为将数据从一个系统转移到另一个系统的脱机介质。 磁带卷在一个卷盘上，运行时磁带经过读写磁头，把磁带上的信息读入计算机，或者把计算机中的信息写到磁带上去。 数据记录在磁带带面上。在带面上并列存放有 9 个磁道的信息，即每一横排有 9 位二进制信息：8 位数据加 1 位奇偶校验位。 磁带的存储密度用 BPI（Bit Per Inch）为单位，典型的存储密度有 3 种：6250BPI（=246排/mm）、1600BPI（=64排/mm）、800BPI（32排/mm）。正常走带速度为3～5m/Sec，因设备而异。 数据的传送速度 = 存储密度?走带速度／读写时间。 在应用中使用文件进行数据处理的基本单位叫做逻辑记录，简称为记录；在磁带上物理地存储的记录叫做物理记录。 在使用磁带或磁盘存放逻辑记录时，常常把若干个逻辑记录打包进行存放，把这个过程叫做“块化”（blocking）。经过块化处理的物理记录叫做块化记录。 磁带设备是一种启停设备。磁带每次启停都有一个加速与减速的过程，在这段时间内走带不 稳定，只能走空带，这段空带叫做记录间间隙IRG（Inter Record Gap）或者块间间隙IBG（Inter Block Gap），其长度因设备而异。 如果每个逻辑记录是 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） 磁盘存储器通常称为直接存取设备，或随机存取设备，它访问外存上文件的任一记录的时间几乎相同。 磁盘存储器可以顺序存取，也可以随机存取。 目前使用较多的是活动臂硬盘组：若干盘片构成磁盘组，它们安装在主轴上，在驱动装置的控制下高速旋转。除了最上面一个盘片和最下面一个盘片的外侧盘面不用以外，其他每个盘片上下两面都可存放数据。将这些可存放数据的盘面称为记录盘面。 每个记录盘面上有很多磁道，数据就存放在这些磁道上。它们在记录盘面上形成一个个同心圆。 每个记录盘面都有一个读写磁头。所有记录盘面的读写磁头都安装在同一个动臂上，随动臂向内或向外做径向移动，从一个磁道移到另一个磁道。 任一时刻，所有记录盘面的读写磁头停留在各个记录盘面的半径相同的磁道上。运行时，由于盘面做高速旋转，磁头所在的磁道上的数据相继在磁头下，从而可以读写数据 各个记录盘面上半径相同的磁道合在一起称为柱面。动臂的移动实际上是将磁头从一个柱面移动到另一个柱面上。 一个磁道可以划分为若干段，称为扇区，一个扇区就是一次读写的最小数据量。这样，对磁盘存储器来说，从大到小的存储单位是：盘片组、柱面、磁道和扇区。 对磁盘存储器进行一次存取所需时间： 当有多个盘片组时，要选定某个盘片组。这是由电子线路实现的，速度很快。 选定盘片组后再选定某个柱面，并移动动臂把磁头移到此柱面上。这是机械动作，速度较慢。这称为“寻查（seek）”。 选定柱面后，要进一步确定磁道，即确定由哪个读写磁头读写，由电子线路实现。 ‘确定磁道后，还要确定所要读写数据在磁盘上的位置（如在哪一个扇区）。这实际上就是在等待要读写的扇区转到读写磁头下面。这是机械动作。这段时间一般称为旋转延迟（rotational delay）时。 真正进行读写时间。 在磁盘组上一次读写的时间主要为： tio＝tseek＋tlatency＋trw 其中，tseek是平均寻查时间，是把磁头定位到要求柱面所需时间，这个时间的长短取