《殷人昆 数据结构》由会员分享，可在线阅读，更多相关《殷人昆 数据结构（233页珍藏版）》请在金锄头文库上搜索。
1、第十章 文件、外 部排序与搜索清华大学计算机系殷人昆1n主存储器和外存储器 n文件组织 n外排序 n多级索引结构 n可扩充散列nTrie树 第十章 文件、外部排序 与外部搜索2主存储器与外部存储器n外存储器与内存储器相比，优点是：u价格较低u永久的存储能力n缺点：u访问外存储器上的数据比访问内存要慢5 6个数量级n要求我们在开发系统时必须考虑如何使外存 访问次数达到最少。3磁带（tape）n磁带是一种顺序存取设备。n磁带主要用于备份、存储不经常使用的数据 ，以及作为将数据从一个系统转移到另一个 系统的脱机介质。 读出头写入头磁带送带盘卷带盘4n磁带卷在一个卷盘上，运行时磁带经过读写 磁头，把磁
2、带上的信息读入计算机，或者把 计算机中的信息写到磁带上去。n数据记录在磁带带面上。在带面上并列存放 有 9 个磁道的信息，即每一横排有 9 位二进 制信息：8 位数据加 1 位奇偶校验位。n磁带的存储密度用 BPI（Bit Per Inch）为单 位，典型的存储密度有 3 种：6250BPI（ =246排/mm）、1600BPI（=64排/mm）、 800BPI（32排/mm）。正常走带速度为3 5m/Sec，因设备而异。5n数据的传送速度 = 存储密度走带速度读 写时间。n在应用中使用文件进行数据处理的基本单位 叫做逻辑记录，简称为记录；在磁带上物理 地存储的记录叫做物理记录。n在使用磁带或
3、磁盘存放逻辑记录时，常常把 若干个逻辑记录打包进行存放，把这个过程 叫做“块化”（blocking）。经过块化处理的 物理记录叫做块化记录。n磁带设备是一种启停设备。磁带每次启停都 有一个加速与减速的过程，在这段时间内走 带不6稳定，只能走空带，这段空带叫做记录间间 隙IRG（Inter Record Gap）或者块间间隙 IBG（Inter Block Gap），其长度因设备而 异。磁带速度 75-200英寸/秒 传输速度 7000-1250000字/秒1.5-16 ms1.5-16 ms定速加速IBG 0.30.75英寸减速物理记录启动位置IBG 0.30.75英寸停止位置 传输开始传输完
4、成 经过时间7n如果每个逻辑记录是 80个字符，IRG为 0.75 英寸，则对存储密度为 1600BPI 的磁带，一 个逻辑记录仅占 80/1600 = 1/20英寸。每传输 一个逻辑记录磁带走过 0.05英寸，接着磁带 要走过一个IRG占0.75英寸。结果大部分时 间都花费在走空带上，存储利用率只有1/16 。n如果将若干逻辑记录存放于一个块，将IRG 变成IBG，可以提高存储利用率。例如，将 50个有80个字符的逻辑记录放在一个块内， 此块的长度将达到5080/1600 = 2.5英寸，存 储利用率达到0.77。因此在磁带上采用按块 读写。8n在磁带设备上读写一块信息所用时间 tIO =
5、ta + tbn其中，ta 是延迟时间，即读写磁头到达待读 写块开始位置所需花费的时间，它与当前读 写磁头所在位置有关。tb是对一个块进行读 写所用时间，它等于数据传输时间加上IBG 时间。n磁带设备只能用于处理变化少，只进行顺序 存取的大量数据。9磁盘（disc）n磁盘存储器通常称为直接存取设备，或随机 存取设备，它访问外存上文件的任一记录的 时间几乎相同。n磁盘存储器可以顺序存取，也可以随机存取 。n目前使用较多的是活动臂硬盘组：若干盘片 构成磁盘组，它们安装在主轴上，在驱动装 置的控制下高速旋转。除了最上面一个盘片 和最下面一个盘片的外侧盘面不用以外，其 他每个盘片上下两面都可存放数据。
6、将这些 可存放数据的盘面称为记录盘面。 10主轴盘片活动臂 （回转臂）读写磁头磁道柱面11n每个记录盘面上有很多磁道，数据就存放在 这些磁道上。它们在记录盘面上形成一个个 同心圆。 n每个记录盘面都有一个读写磁头。所有记录 盘面的读写磁头都安装在同一个动臂上，随 动臂向内或向外做径向移动，从一个磁道移 到另一个磁道。n任一时刻，所有记录盘面的读写磁头停留在 各个记录盘面的半径相同的磁道上。运行时 ，由于盘面做高速旋转，磁头所在的磁道上 的数据相继在磁头下，从而可以读写数据 12n各个记录盘面上半径相同的磁道合在一起称 为柱面。动臂的移动实际上是将磁头从一个 柱面移动到另一个柱面上。 n一个磁道
7、可以划分为若干段，称为扇区，一 个扇区就是一次读写的最小数据量。这样， 对磁盘存储器来说，从大到小的存储单位是 ：盘片组、柱面、磁道和扇区。n对磁盘存储器进行一次存取所需时间： 当有多个盘片组时，要选定某个盘片组。 这是由电子线路实现的，速度很快。13选定盘片组后再选定某个柱面，并移动动 臂把磁头移到此柱面上。这是机械动作， 速度较慢。这称为“寻查（seek）”。选定柱面后，要进一步确定磁道，即确定 由哪个读写磁头读写，由电子线路实现。 确定磁道后，还要确定所要读写数据在磁 盘上的位置（如在哪一个扇区）。这实际 上就是在等待要读写的扇区转到读写磁头 下面。这是机械动作。这段时间一般称为 旋转延
8、迟（rotational delay）时。真正进行读写时间。 14n在磁盘组上一次读写的时间主要为：tiotseektlatencytrwn其中，tseek是平均寻查时间，是把磁头定位 到要求柱面所需时间，这个时间的长短取决 于磁头移过的柱面数。tlatency是平均等待时间 ，是将磁头定位到指定块所需时间。trw是传 送一个扇区数据所需的时间。n在MS-DOS系统中，多个扇区集结成组，称 为簇。簇是文件分配的最小单位，其大小由 操作系统决定。在UNIX系统中不使用簇， 文件分配的最小单位和读写的最小单位是一 个扇区，15称为一个块（block）。n磁盘一次读写操作访问一个扇区，称为访问“ 一
9、页”（page）或“一块”（block），又称为“ 一次访外”。n为了实施磁盘读写操作，在内存中需要开辟 一些区域，用以存放需要从磁盘读入的信息 ，或存放需要写出的信息。这些内存区域称 为缓冲区）。多数操作系统至少设置两个缓 冲区，一个为输入缓冲区；一个为输出缓冲 区。 缓冲区（buffer）16n例如在从磁盘向内存读入一个扇区的数据时 ，数据被存放到输入缓冲区，如果下次需要 读入同一个扇区的数据，就可以直接从缓冲 区中读取数据，不需要重新读盘。n缓冲区大小应与操作系统一次读写的块的大 小相适应，这样可以通过操作系统一次读写 把信息全部存入缓冲区中，或把缓冲区中的 信息全部写出到磁盘。n如果缓
10、冲区大小与磁盘上的块大小不适配， 就会造成内存空间的浪费。n缓冲区的构造可以看作一个先进先出的队列 。 17缓冲区的定义及其操作 #include #include const int DefaultSize = 2048; template struct buffer T *data;/缓冲区数组int current, maxSize;/当前指针, 缓冲区容量 buffer (int sz = DefaultSize) : maxSize(sz), current(0) data = new Tsz; assert (data != NULL); buffer() delete data;
11、 18void OutputInfo (ostream /缓冲区输 出void InputInfo (istream /缓冲区输 入 ;template void buffer:OutputInfo (ostream i void buffer:InputInfo (istreamcurrent = 0; ;20文件组织n什么是文件u文件是存储在外存上的数据结构。u文件分操作系统文件和数据库文件 操作系统中的文件是流式文件：是没有 结构的字符流 数据库文件是具有结构的数据集合u数据结构中讨论的是数据库文件。n操作系统对文件是按物理记录读写的，在数 据库中文件按页块存储和读写。文件的基本概念21
12、文件的组成n文件由记录组成；记录由若干数据项组成。n记录是文件存取的基本单位，数据项是文件可 使用的最小单位。n从不同的观点，文件记录分为逻辑记录和物理 记录。前者是面向用户的基本存取单位，后者 是面向外设的基本存取单位。n能够唯一标识一个记录的数据项或数据项集称 为主关键码项，其值称为主关键码；n不唯一标识一个记录的数据项或数据项集称为 次关键码项，其值称为次关键码。22n文件结构包括文件的逻辑结构、文件的存储 结构和文件的操作。n文件的逻辑结构是线性结构，各个记录以线 性方式排列。n文件的存储结构是指文件在外存上的组织方 式，它与文件特性有关。u 顺序组织u 索引组织u 直接存取组织（散列
13、组织）n文件的操作是定义在逻辑结构上的，但操作 的具体实现要在存储结构上进行。23n评价一个文件组织的效率u执行文件操作所花费的时间u文件组织所需要的空间。文件的操作检索维护简单查询 范围查询 函数查询 布尔查询 插入 删除 修改 重构 恢复24顺序文件 (Sequential File )n顺序文件中的记录按它们进入文件的先后顺 序存放，其逻辑顺序与物理顺序一致。n如果文件的记录按主关键码有序，则称其为 顺序有序文件，否则称其为顺序无序文件。n顺序文件通常存放在顺序存取设备（如磁带 ）上或直接存取设备（如磁盘）上。n当存放在顺序存取设备上时只能按顺序搜索 法存取；当存放在直接存取设备上时，可
14、以 使用顺序搜索法、折半搜索法等存取。25n顺序文件的存储方式 n连续文件：文件的全部记录顺序地存放外 存的一个连续的区域中。优点是存取速度 快、存储利用率高、处理简单。缺点是区 域大小需事先定义，不能扩充。 n串联文件：文件记录成块存放于外存中， 在块中记录顺序连续存放，但块与块之间 可以不连续，通过块链指针顺序链接。优 点是文件可以扩充、存储利用率高。缺点 是影响了存取和修改的效率。26直接存取文件 (Direct Access File)n文件记录的逻辑顺序与物理顺序不一定相同 。通过记录的关键码可直接确定该记录的地 址。n利用散列技术组织文件。处理类似散列法， 但它是存储在外存上的。n
15、使用散列函数把关键码集合映射到地址集合 时，往往会产生地址冲突，处理冲突有两种 处理方式：u按桶散列u可扩充散列 27(1) 按桶散列n文件中的记录成组存放，若干个记录组成一 个存储单位，称之为桶。假若一个桶能存放 m个记录，则m个互为同义词的记录可以存 放在同一地址的桶中。当第m+1个同义词出 现时，才发生“溢出”。 (a) 溢出链u当发生“溢出”时，将第m+1个同义词存放 到“溢出桶”。并称存放前m个同义词的桶 为“基桶”。溢出桶和基桶大小相同。当在 基桶中检索不成功，就循指针到溢出桶中 检索。 28n在这种散列文件中删除记录时，因为可能需 要重新链接，所以只需做一个逻辑删除标记 即可，待系统做周期性重构时再做物理删除 。桶大小为3的溢出桶链表示例 070 512 204 246 O1 597 177 262 157 116 613 285 635 208 O2 923 076 0 1 2 3 4 5 6O1 O2 O3 O4 O5 O6 O7015 337 988 O3 817 117 390 O4 575 540 435 362 基桶编号 基桶区 溢出桶编号 溢出桶区29(b) 分布式溢出空间u溢出桶按照一定的 间隔分布在基桶之间 。如果有一个基桶溢 出了，系统就将记录 存放在下一个溢出桶 中。 u如果溢出桶自己溢 出了，
