Appearance
文件的逻辑结构
考情分析
文件逻辑结构属于文件管理高频考点，在 408 真题中常以选择题形式考查各种文件结构的存取特性。属于 🔥🔥🔥 高频。
同样一堆数据，是当成字节流随便读，还是按记录分门别类地组织？不同的逻辑结构决定了用户能以什么方式、什么效率来存取文件。
逻辑结构 vs 物理结构
文件有两个层面的结构：
- 逻辑结构：从用户视角看文件的组织方式（本文内容）
- 物理结构：文件数据在磁盘上的存储方式（下一篇讲解）
逻辑结构影响用户的存取方式，物理结构影响系统的 I/O 效率。两者是独立的——同一种逻辑结构可以映射到不同的物理结构上。
无结构文件（流式文件）
文件内部没有明确的结构，就是一个字节流（byte stream）。
- 典型例子：
.txt文本文件、二进制可执行文件 - 存取方式：按字节偏移量定位
- Unix/Linux 中几乎所有文件都被视为流式文件
有结构文件（记录式文件）
文件由一组**记录（record）组成，每条记录由若干数据项（字段）**构成。记录是文件存取的基本单位。
顺序文件
记录按某种顺序排列，分为两种：
| 类型 | 排列方式 | 特点 |
|---|---|---|
| 串结构 | 按记录存入的先后顺序排列 | 检索需要逐个查找 |
| 顺序结构 | 按关键字递增/递减排列 | 可以使用折半查找 |
存取特性：
| 操作 | 串结构 | 顺序结构 |
|---|---|---|
| 顺序读取 | O(n) 遍历 | O(n) 遍历 |
| 按关键字查找 | O(n) 逐个比较 | O(log n) 折半查找 |
| 插入新记录 | 追加到末尾 O(1) | 需要移动记录以保持有序 |
| 删除记录 | 标记删除或移动 | 需要移动记录 |
顺序文件的优势
顺序文件是对批量顺序处理效率最高的文件结构。磁带只能顺序存取，因此磁带上的文件只能是顺序文件。
索引文件
为文件中的每条记录建立一个索引项，所有索引项构成索引表。索引表按关键字排序，支持折半查找快速定位。
索引表 主文件（记录区）
┌───────┬──────┐ ┌─────────────────┐
│关键字 │ 指针 │─────────► │ 记录内容... │
├───────┼──────┤ ├─────────────────┤
│关键字 │ 指针 │─────────► │ 记录内容... │
├───────┼──────┤ ├─────────────────┤
│关键字 │ 指针 │─────────► │ 记录内容... │
└───────┴──────┘ └─────────────────┘
按关键字排序 记录可以不连续特点：
- 支持随机存取和顺序存取
- 插入/删除只需修改索引表
- 代价：需要额外空间存储索引表
适用场景：记录长度不等的文件（定长记录没必要用索引，直接算偏移就行）。索引文件就像一本书的目录页——翻目录找到章节对应的页码，直接跳过去，不用从第一页翻起。
索引顺序文件
是顺序文件和索引文件的折中方案——类似字典的部首检字法：先按部首（索引）缩小范围，再在对应的笔画区内顺序查找：
- 将所有记录分成若干组
- 组内记录可以无序
- 建立一个稀疏索引表，每组一个索引项，记录该组的最大关键字和起始位置
索引表（每组一项） 主文件
┌──────┬──────┐ ┌───────────────┐
│ 组1≤15│ → │────────►│ 组1: 3条记录 │ ← 组内无序
├──────┼──────┤ ├───────────────┤
│ 组2≤30│ → │────────►│ 组2: 3条记录 │
├──────┼──────┤ ├───────────────┤
│ 组3≤50│ → │────────►│ 组3: 3条记录 │
└──────┴──────┘ └───────────────┘检索过程：
- 在索引表中折半查找，确定记录属于哪个组 — O(log(组数))
- 在组内顺序查找目标记录 — O(组大小)
若文件有 N 条记录，分成 √N 组，每组 √N 条，则平均检索长度为 √N，介于顺序文件的 N/2 和索引文件的 log₂N 之间。
多级索引顺序文件
当记录数量非常大时，可以对索引表再建索引，形成多级索引顺序文件。ISAM（索引顺序存取方法）和 VSAM 就是典型实现。
散列文件（Hash 文件）
用散列函数将关键字映射到物理存储地址。
- 检索速度最快：O(1)
- 不适合顺序存取
- 存在哈希冲突问题
四种逻辑结构对比
| 逻辑结构 | 顺序存取 | 随机存取 | 检索效率 | 适用场景 |
|---|---|---|---|---|
| 顺序文件 | 最优 | 仅顺序结构支持 | O(n) 或 O(log n) | 批量处理、磁带 |
| 索引文件 | 支持 | 支持 | O(log n) | 变长记录、随机查询 |
| 索引顺序文件 | 支持 | 支持 | O(√N) | 大量记录的折中方案 |
| 散列文件 | 不支持 | 支持 | O(1) | 快速单记录查找 |
考研高频考点
- 🔥🔥🔥 顺序文件中串结构与顺序结构的区别
- 🔥🔥🔥 索引顺序文件的检索过程和平均检索长度 √N
- 🔥🔥 四种逻辑结构各自的存取特性对比
- 🔥🔥 索引文件的索引表结构及其适用场景（变长记录）
- 🔥 散列文件的特点（最快但不支持顺序存取）
逻辑结构决定了用户怎么看数据，但数据最终要落到磁盘块上。下一篇来看文件的物理结构——连续放、链式放还是建索引？