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

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

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

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

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

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

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

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

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

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

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

稳定,只能走空带,这段空带叫做记录间间隙 IRG( Inter Record Gap)或者块间间隙IBG ( Inter block gap),其长度因设备而异。 定速 磁带速度 加速 75-200英寸渺秒 减速 1.16传输速度 15-16 700012500字秒 ms 启动位置 1传输开始 4经过时间传输完1同正位置 IBG 物理记录 IBG 03~075英寸 0.3~075英寸

稳定，只能走空带，这段空带叫做记录间间隙 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英寸 停止位置 传输开始 传输完成 经过时间

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

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

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

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

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

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

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

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