南京大学：《数据结构 Data Structures》课程教学资源（PPT课件讲稿）第十章 文件、外部排序与外部搜索

第十章文件、外部排序 与外部搜索 主存储器和外存储器 文件组织 多级索引结构 外排序

第十章 文件、外部排序 与外部搜索 • 主存储器和外存储器 • 文件组织 • 多级索引结构 • 外排序 1

主存储器与外存储器 主存储器又叫内存储器，简称为内存；外存储 器简称为外存。 外存储器与内存储器相比，优点是： ◆价格较低 ◆永久的存储能力 缺点： ◆访问外存储器上的数据t比访问内存要慢5~ 6个数量级 ·要求我们在开发系统时必须考虑如何使外存访 问次数达到最少。 2

主存储器与外存储器 • 主存储器又叫内存储器，简称为内存；外存储 器简称为外存。 • 外存储器与内存储器相比，优点是： ◆ 价格较低 ◆ 永久的存储能力 • 缺点： ◆ 访问外存储器上的数据比访问内存要慢5～ 6个数量级 • 要求我们在开发系统时必须考虑如何使外存访 问次数达到最少。 2

磁带(tape) 磁带是一种顺序存取设备。 。 磁带主要用于备份、存储不经常使用的数据 以及作为将数据从一个系统转移到另一个系统 的脱机介质。 送带盘 卷带盘 磁带 读出头写入头 3

磁带（tape） • 磁带是一种顺序存取设备。 • 磁带主要用于备份、存储不经常使用的数据， 以及作为将数据从一个系统转移到另一个系统 的脱机介质。 3 读出头 写入头 磁带 送带盘 卷带盘

磁带卷在一个卷盘上，运行时磁带经过读写磁 头，把磁带上的信息读入计算机，或者把计算 机中的信息写到磁带上去。 数据记录在磁带带面上。在带面上并列存放有 9个磁道的信息，即每一横排有9位二进制信 息：8位数据加1位奇偶校验位。 .磁带的存储密度用BPI(Bit Per Inch)为单位， 典型的存储密度有3种：6250BPI（=246排 /mm)、1600BPI（=64排/mm)、800BPI (32排/mm)。正常走带速度为3~5m/Sec, 因设备而异。 4

• 磁带卷在一个卷盘上，运行时磁带经过读写磁 头，把磁带上的信息读入计算机，或者把计算 机中的信息写到磁带上去。 • 数据记录在磁带带面上。在带面上并列存放有 9 个磁道的信息，即每一横排有 9 位二进制信 息：8 位数据加 1 位奇偶校验位。 • 磁带的存储密度用 BPI（Bit Per Inch）为单位， 典型的存储密度有 3 种：6250BPI（=246排 /mm）、1600BPI（=64排/mm）、800BPI （32排/mm）。正常走带速度为3～5m/Sec， 因设备而异。 4

数据的传送速度=存储密度×走带速度。 在应用中使用文件进行数据处理的基本单位叫 做逻辑记录，简称为记录；在磁带上物理地存 储的记录叫做物理记录。 在使用磁带或磁盘存放逻辑记录时，常常把若 干个逻辑记录打包进行存放，把这个过程叫做 “块化”（blocking)。经过块化处理的物理 记录叫做块化记录 磁带设备是一种启停设备。磁带每次启停都有 一个加速与减速的过程，在这段时间内走带不 5

• 数据的传送速度 = 存储密度走带速度。 • 在应用中使用文件进行数据处理的基本单位叫 做逻辑记录，简称为记录；在磁带上物理地存 储的记录叫做物理记录。 • 在使用磁带或磁盘存放逻辑记录时，常常把若 干个逻辑记录打包进行存放，把这个过程叫做 “块化”（blocking）。经过块化处理的物理 记录叫做块化记录。 • 磁带设备是一种启停设备。磁带每次启停都有 一个加速与减速的过程，在这段时间内走带不 5

稳定，只能走空带，这段空带叫做记录间间隙 IRG（Inter Record Gap)或者块间间隙IBG (Inter Block Gap),其长度因设备而异。 定速 磁带速度 加速 75-200英寸秒 减速 1.5-16 传输速度 1.5-16 ms 7000-1250000字秒 ms 启动位置 停止位置 1传输开始 {传输完成引 经过时间 1 IBG 物理记录 IBG 0.3~0.75英寸 0.3~0.75英寸 6

稳定，只能走空带，这段空带叫做记录间间隙 IRG（Inter Record Gap）或者块间间隙IBG （Inter Block Gap），其长度因设备而异。 6 磁带速度 75-200英寸/秒 传输速度 7000-1250000字/秒 1.5-16 ms 1.5-16 ms 定速 加速 IBG 0.3～0.75英寸 减速 物理记录 启动位置 IBG 0.3～0.75英寸 停止位置 传输开始 传输完成 经过时间

如果每个逻辑记录是10个字符（80bits)， IRG为0.75英寸，则对存储密度为1600BPI的 磁带，一个逻辑记录仅占80/1600=0.05英寸。 每传输一个逻辑记录磁带走过0.05英寸，接着 磁带要走过一个RG占0.75英寸。结果大部分 时间都花费在走空带上，存储利用率只有1/16。 如果将若干逻辑记录存放于一个块，将RG变 成BG,可以提高存储利用率。例如，将50个 有10个字符的逻辑记录放在一个块内，此块的 长度将达到50×80/1600=2.5英寸，存储利用率 达到0.77。因此在磁带上采用按块读写。 7

• 如果每个逻辑记录是 10个字符（80 bits）， IRG为 0.75英寸，则对存储密度为 1600BPI 的 磁带，一个逻辑记录仅占 80/1600 = 0.05英寸。 每传输一个逻辑记录磁带走过 0.05英寸，接着 磁带要走过一个IRG占0.75英寸。结果大部分 时间都花费在走空带上，存储利用率只有1/16。 • 如果将若干逻辑记录存放于一个块，将IRG变 成IBG，可以提高存储利用率。例如，将50个 有10个字符的逻辑记录放在一个块内，此块的 长度将达到5080/1600 = 2.5英寸，存储利用率 达到0.77。因此在磁带上采用按块读写。 7

.在磁带设备上读写一块信息所用时间 tro ta tp 其中，t,是延迟时间，即读写磁头到达待读写 块开始位置所需花费的时间，它与当前读写磁 头所在位置有关。是对一个块进行读写所用 时间，它等于数据传输时间加上BG时间。 磁带设备只能用于处理变化少，只进行顺序存 取的大量数据。 8

• 在磁带设备上读写一块信息所用时间 tIO = ta + tb • 其中，ta 是延迟时间，即读写磁头到达待读写 块开始位置所需花费的时间，它与当前读写磁 头所在位置有关。tb是对一个块进行读写所用 时间，它等于数据传输时间加上IBG时间。 • 磁带设备只能用于处理变化少，只进行顺序存 取的大量数据。 8

磁盘(disc) 磁盘存储器通常称为直接存取设备，或随机存 取设备。 磁盘存储器可以顺序存取，也可以随机存取。 目前使用较多的是活动臂硬盘组：若干盘片构 成磁盘组，它们安装在主轴上，在驱动装置的 控制下高速旋转。除了最上面一个盘片和最下 面一个盘片的外侧盘面不用以外，其他每个盘 片上下两面都可存放数据。将这些可存放数据 的盘面称为记录盘面

磁盘（disc） • 磁盘存储器通常称为直接存取设备，或随机存 取设备。 • 磁盘存储器可以顺序存取，也可以随机存取。 • 目前使用较多的是活动臂硬盘组：若干盘片构 成磁盘组，它们安装在主轴上，在驱动装置的 控制下高速旋转。除了最上面一个盘片和最下 面一个盘片的外侧盘面不用以外，其他每个盘 片上下两面都可存放数据。将这些可存放数据 的盘面称为记录盘面。 9

主轴 磁道 盘片 活动臂 (回转臂) 柱面 读写磁头 10

10 主轴 盘片 活动臂 （回转臂） 读写磁头 磁道 柱面