王道考研数据结构第六章 数据处理与存储支持服务知识点精要

王道考研数据结构第六章主要聚焦于数据处理与存储支持服务，这部分内容是数据管理、文件组织以及外部存储技术的基础，对于理解大型系统中数据的有效组织和高效访问至关重要。本章的核心在于理解如何在外部存储（如磁盘）上组织和存取大量数据，其知识体系围绕文件的逻辑结构、物理结构、操作以及相关支持技术展开。

一、 基本概念与文件逻辑结构

1. 文件与记录：文件是存储在外存上的、由大量性质相同的记录组成的集合。记录是文件中可操作的基本数据单位，由若干数据项（字段）构成。每个记录通常包含一个能唯一标识该记录的关键字（Key）。
2. 文件的逻辑结构：指用户或应用程序所看到的文件组织形式。

• 流式文件：文件内容被视为一个无结构的字符流（如文本文件、源程序文件）。

• 记录式文件：文件由若干逻辑记录组成，记录可顺序或按关键字存取。这是本章讨论的重点。

二、 文件的物理结构（存储结构）

文件的物理结构定义了记录在外存上的实际存储与组织方式，直接影响存取效率。主要类型有：

1. 顺序文件（顺序结构）：记录按其进入文件的先后顺序连续存放。

• 特点：批量存取（尤其是顺序存取）效率高，但插入、删除记录困难，通常需重组文件。

• 顺序查找：可从头开始依次查找，也可针对有序顺序文件进行折半查找（需支持随机存取）。

1. 索引文件：由主文件（数据区） 和索引表两部分构成。索引表本身是一个文件，其记录由关键字和对应主文件记录地址组成，并按关键字有序。

• 特点：适合随机存取和关键字查找。查找时先在有序索引表中快速定位（如折半查找），再根据地址访问主文件记录。

• 多级索引：当索引表很大时，可为其再建立索引，形成树形结构（如ISAM）。

1. 索引顺序文件（ISAM, VSAM）：是顺序文件和索引文件的结合，在实践中应用广泛。

• ISAM（索引顺序存取方法）：采用静态索引结构，由主索引、柱面索引、磁道索引和多级主文件（柱面、磁道）构成。插入记录时使用溢出区，删除记录做标记。定期需重组文件以恢复性能。

• VSAM（虚拟存储存取方法）：采用B+树动态索引结构。文件由索引集、顺序集（叶子节点，包含全部关键字和指针）和数据集组成。插入、删除灵活，无需重组文件，存取路径与设备物理特性无关。

1. 散列文件（直接存取文件）：根据记录的关键字，通过散列函数直接计算其在外存上的存储地址（通常是桶Bucket的地址）。

• 特点：随机存取速度极快，但散列冲突不可避免，处理冲突会降低效率（常用链地址法，将同义词记录链在同一桶内或溢出桶中）。不支持顺序存取和范围查询。

三、 文件的操作

1. 检索（查找）：

• 顺序存取：存取下一个逻辑记录。

• 直接存取：存取第i个逻辑记录。

• 按关键字存取：存取关键字等于给定值的记录。

1. 插入：将新记录写入文件。
2. 删除：从文件中删去指定记录。
3. 修改：更改指定记录的部分字段值。
4. 排序：按指定关键字对文件中的记录进行排序，是许多操作（如高效检索、归并）的基础。

四、 存储支持服务与多路归并

处理海量数据（超出内存容量）时，需要借助外部存储和特定的算法。

1. 外排序：对大文件进行排序，数据主要存放在外存，排序过程中需要在内存与外存之间多次交换数据。
2. 归并排序思想：是外排序的核心。先将大文件分割成若干能装入内存的子文件（段），分别调入内存进行内排序，形成初始归并段（顺串） 写回外存。然后对这些归并段进行多路归并，最终合并成一个有序文件。
3. 多路平衡归并：

• 过程：一次性将k个归并段中当前最小的记录比较选出，送入输出缓冲区，写回磁盘。减少归并趟数，从而减少I/O次数。k越大，趟数越少。

• 败者树：一种高效实现多路归并选择最小/最大值的数据结构。能在k个记录中选择最小者，其比较时间复杂度仅为O(log₂k)，有效减少了关键字的比较次数。

1. 置换-选择排序：用于生成初始归并段。在内存工作区容量为w的情况下，可以生成平均长度大于2w的初始归并段，从而进一步减少初始归并段数量，缩短后续归并趟数。
2. 最佳归并树（哈夫曼树的应用）：当初始归并段长度不等时，通过构造以归并段长度为权值的k叉哈夫曼树，可以确定最优的归并顺序，使总的I/O次数最少。

五、 知识要点与考查重点

• 理解与比较：深刻理解顺序、索引、索引顺序、散列四种文件物理结构的原理、优缺点及适用场景（如顺序存取 vs 随机存取，静态 vs 动态）。
• 掌握操作效率：能分析在不同文件结构下进行检索、插入、删除等操作的大致时间开销（与I/O次数相关）。
• 聚焦外排序：掌握多路平衡归并的过程、败者树的作用与构建、置换-选择排序生成初始归并段的流程，以及最佳归并树的构造与应用。这是考研中的高频计算和设计题考点。
• 联系前后章节：本章的索引技术与前面的查找表（特别是B树/B+树）、散列技术紧密相关；外排序中的归并与内排序算法一脉相承。

第六章将数据结构的视角从内存扩展到外存，阐述了在存储层次中管理大规模数据集的经典方法与支持服务，是构建数据库、文件系统等复杂软件的重要基石。复习时需在理解概念的基础上，重点掌握其设计思想与算法流程。