文件、外部排序与外部搜索

《文件、外部排序与外部搜索》由会员分享，可在线阅读，更多相关《文件、外部排序与外部搜索（135页珍藏版）》请在金锄头文库上搜索。

1、第十章 文件、外部排序 与外部搜索 主存储器和外存储器 文件组织 多级索引结构 外排序 1 主存储器与外存储器 主存储器 又叫 内存储器， 简称为 内存；外存储器 简称为 外存。 外存储器 与 内存储器 相比，优点是： 价格较低 永久的存储能力 缺点： 访问 外存 储器上的数据比访问 内存 要慢 56个数量级 要求我们在开发系统时必须考虑如何 使外存访问次数达到最少 。 2 磁带（ 磁带是一种 顺序存取 设备。 磁带主要用于备份、存储不经常使用的数据，以及作为将数据从一个系统转移到另一个系统的脱机介质。 3 读出头 写入头 磁带 送带盘 卷带盘 磁带卷在一个卷盘上，运行时磁带经过读写磁头，把磁

2、带上的信息读入计算机，或者把计算机中的信息写到磁带上去。 数据记录在磁带带面上。在带面上并列存放有 9 个磁道的信息，即 每一横排有 9 位二进制信息 ： 8 位数据加 1 位奇偶校验位。 磁带的存储密度用 为单位，典型的存储密度有 3 种： 6250=246排/ 1600=64排 / 80032排 /正常走带速度为 3 5m/设备而异。 4 数据的传送速度 = 存储密度 走带速度 。 在应用中使用文件进行数据处理的基本单位叫做 逻辑记录 ，简称为记录；在磁带上物理地存储的记录叫做 物理记录 。 在使用磁带或磁盘存放逻辑记录时，常常把 若干个逻辑记录打包 进行存放，把这个过程叫做“块化”（ 经

3、过块化处理的物理记录叫做 块化记录 。 磁带设备是一种启停设备。磁带每次启停都有一个加速与减速的过程，在这段时间内走带不 5 稳定，只能走空带，这段空带叫做 记录间间隙者 块间间隙 其长度因设备而异。 6 磁带速度 75秒 传输速度 7000秒 速 加速 减速 物理记录 启动位置 停止位置 传输开始 传输完成 经过时间 如果每个逻辑记录是 80个字符 ， 则对存储密度为 1600磁带，一个逻辑记录仅占 80/1600 = 每传输一个逻辑记录磁带走过 接着磁带要走过一个 结果大部分时间都花费在走空带上， 存储利用率只有 1/16。 如果将若干逻辑记录存放于一个块，将 以提高存储利用率。例如，将

4、50个有 80个字符的逻辑记录放在一个块内，此块的长度将达到 5080/1600 = 储利用率达到 此在磁带上采用 按块读写 。 7 在磁带设备上读写一块信息所用时间 其中， 延迟时间 ，即读写磁头到达待读写块开始位置所需花费的时间，它与当前读写磁头所在位置有关。 写所用时间 ，它等于数据传输时间加上 磁带设备只能用于处理变化少，只进行 顺序存取 的大量数据。 8 磁盘（ 磁盘存储器通常称为 直接存取设备 ，或 随机存取设备 ，它访问外存上文件的任一记录的时间几乎相同。 磁盘存储器可以 顺序存取 ，也可以 随机存取 。 目前使用较多的是 活动臂硬盘组 ：若干盘片构成磁盘组，它们安装在主轴上，在

5、驱动装置的控制下高速旋转。除了最上面一个盘片和最下面一个盘片的外侧盘面不用以外，其他每个盘片上下两面都可存放数据。将这些可存放数据的盘面称为 记录盘面 。 9 10 主轴 盘片 活动臂 （回转臂） 读写磁头 磁道 柱面 每个记录盘面上有很多 磁道 ，数据就存放在这些磁道上。它们在记录盘面上形成一个个同心圆。 每个记录盘面都有一个读写磁头。所有记录盘面的读写磁头都安装在同一个动臂上，随动臂向内或向外做径向移动，从一个磁道移到另一个磁道。 任一时刻，所有记录盘面的读写磁头停留在各个记录盘面的 半径相同 的磁道上。运行时，由于盘面做高速旋转，磁头所在的磁道上的数据相继在磁头下，从而可以读写数据 。

6、11 各个记录盘面上半径相同的磁道合在一起称为 柱面 。动臂的移动实际上是将磁头从一个柱面移动到另一个柱面上。 一个 磁道 可以划分为若干段，称为 扇区 ，一个扇区就是一次读写的最小数据量。这样，对磁盘存储器来说，从大到小的存储单位是：盘片组、柱面、磁道和扇区 。 对磁盘存储器进行 一次存取所需时间 ： 1. 当有多个盘片组时，要选定某个盘片组。这是由电子线路实现的，速度很快。 12 2. 选定盘片组后再选定某个柱面，并移动动臂把磁头移到此柱面上。这是 机械动作 ，速度较慢。这称为“ 寻查 （ 。 3. 选定柱面后，要进一步确定磁道，即确定由哪个读写磁头读写，由电子线路实现。 4. 确定磁道后

7、，还要确定所要读写数据在磁盘上的位置（如在哪一个扇区）。这实际上就是在等待要读写的扇区转到读写磁头下面。这是 机械动作 。这段时间一般称为旋转延迟（ 间 。 5. 真正进行读写时间。 13 在磁盘组上一次读写的时间主要为： 其中， 均寻查时间 ，是把磁头定位到要求柱面所需时间，这个时间的长短取决于磁头移过的柱面数。 均等待时间 ，是将磁头定位到指定块所需时间。 在 个扇区集结成组，称为簇 。簇是文件分配的最小单位，其大小由操作系统决定。在 件分配的最小单位和读写的最小单位是一个扇区，称为一个 块 （ 14 缓冲区（ 磁盘一次读写操作访问一个扇区，称为访问“一页”（ “一块”（ 又称为“一次访外

8、”。 为了实施磁盘读写操作，在 内存中 需要开辟一些区域，用以存放需要从磁盘读入的信息，或存放需要写出的信息。这些内存区域称为 缓冲区 。 多数操作系统至少设置两个缓冲区，一个为 输入缓冲区 ，一个为 输出缓冲区 。 15 例如，在从磁盘向内存读入一个扇区的数据时，数据被存放到输入缓冲区，如果下次需要读入同一个扇区的数据，就可以直接从缓冲区中读取数据，不需要重新读盘。 缓冲区大小应 与操作系统一次读写的块 的 大小相适应 ，这样可以通过操作系统一次读写把信息全部存入缓冲区中，或把缓冲区中的信息全部写出到磁盘。 如果缓冲区大小与磁盘上的块大小不适配，就会造成存储空间的浪费。 缓冲区的构造可以看作

9、一个先进先出的 队列 。 16 缓冲区的定义及其操作 # 2048; T * /缓冲区数组 , 缓冲区容量 : ) = 17 T x); /缓冲区输出 T& x); /缓冲区输入 ; T x) = i = 0; i T& x) i; 0; ; 19 文件组织 什么是文件 文件是存储在外存上的数据结构，一般是在逻辑上具有完整意义的一组相关信息项的有序序列。 文件分操作系统文件和数据库文件 操作系统中的文件是流式文件：是没有结构的字符流 数据库文件是具有结构的数据集合 数据结构中讨论的是数据库文件。 操作系统对文件是按 物理记录 读写的，在数据库中文件按 页块 存储和读写。 20 文件的基本概念

10、文件的组成 文件 由 记录 组成； 记录 由若干 数据项 组成。 记录是文件存取的基本单位，数据项是文件可使用的最小单位。 从不同的观点，文件记录分为 逻辑记录 和 物理记录 。前者是面向用户的基本存取单位，后者是面向外设的基本存取单位。 能够唯一标识一个记录的数据项或数据项集称为 主关键码项 ，其值称为 主关键码 ； 不唯一标识一个记录的数据项或数据项集称为次关键码项 ，其值称为 次关键码 。 21 文件结构包括文件的 逻辑结构 、文件的 存储结构 和文件的 操作 。 文件的逻辑结构是 线性结构 ，各个记录以线性方式排列。 文件的 存储结构 是指文件在外存上的组织方式，它与文件特性有关。 顺

11、序组织 直接存取组织（散列组织） 索引组织 文件的操作是 定义在逻辑结构上 的，但操作的具体实现 要在 存储结构 上进行。 22 评价一个文件组织的效率 执行文件操作所花费的时间 文件组织所需要的空间。 23 文件的操作 检索 维护 简单查询 范围查询 函数查询 布尔查询 插入 删除 修改 重构 恢复 顺序文件 ( 顺序文件中的记录按它们进入文件的先后顺序存放，其 逻辑顺序与物理顺序一致 。 如果文件的记录按主关键码有序，则称其为 顺序有序文件 ，否则称其为 顺序无序文件 。 顺序文件通常存放在顺序存取设备（如磁带）上或直接存取设备（如磁盘）上。 当存放在顺序存取设备上时只能按顺序搜索法存取；

12、当存放在直接存取设备上时，可以使用顺序搜索法、折半搜索法等存取。 24 顺序文件的存储方式 1. 连续文件 ：文件的全部记录顺序地存放于外存的一个连续的区域中。优点是存取速度快、存储利用率高、处理简单。缺点是区域大小需事先定义，不能扩充。 2. 串联文件 ：文件记录成块存放于外存中，在块中记录顺序连续存放，但 块与块之间可以不连续 ，通过块链指针顺序链接。优点是文件可以扩充、存储利用率高。缺点是影响了存取 和修改的效率。 25 直接存取文件 ( 又叫 散列文件。 利用散列技术组织文件。处理类似散列法，但它是存储在外存上的。 文件记录的 逻辑顺序与物理顺序不一定相同 。通过记录的 关键码 可直接确定该记录的地址。 使用 散列函数 把关键码集合映射到地址