文件的逻辑结构

2026 大纲 四（一）5 文件的逻辑结构。

用户眼里的文件内部，是什么形状

前四节讲的都是文件的外部：它叫什么名字、元数据放哪、怎么打开、谁能访问。 从这一节开始转向内部——文件里面的数据是怎么组织的。

而"内部"这件事有两个互不相干的答案，取决于站在谁的角度看：

用户看到的是逻辑结构。 一个通讯录文件在用户眼里是一条条记录， 每条有姓名、电话；一个日志文件在用户眼里就是一长串字节。 用户关心的是"怎么找到第 500 条记录"。

系统看到的是物理结构。 同一个文件在系统眼里是散落在磁盘上的若干个块， 系统关心的是"文件内第 8000 个字节落在哪个盘块上"。

这两层以"文件内偏移量"为公共接口对接：用户说"我要第 500 条记录"， 逻辑结构负责把它换算成"文件内第 X 字节"；物理结构负责把"第 X 字节" 换算成"第 Y 个盘块的第 Z 个字节"。

接口一确定，两层就彻底解耦了——任何一种逻辑结构都能配任何一种物理结构， 互不限制。这一节讲上面那层，下一节讲下面那层。

本节的主线是一条被"怎么快速找到第 $k$ 条记录"推着走的链： 最朴素的顺序文件只能一条条数（$O(N)$）→ 记录定长时可以直接算偏移，于是能折半 → 可记录变长时算不出偏移，只好为每条记录建一份索引（索引文件）→ 索引表本身又变得和记录一样多，那就每组建一项（索引顺序文件）→ 干脆连查都不查，用关键字直接算出地址（散列文件）。

每一步都在拿空间或某种能力，去换定位速度。

一、逻辑结构与物理结构的分界

逻辑结构说的是"第 $k$ 条记录在文件的第几个字节"，物理结构说的是"文件的第 $x$ 个字节在磁盘的哪一块"。两者串起来才是完整映射，而中间那个"文件内偏移量"是一个公共接口——谁也不需要知道对方怎么做的，所以换一种物理结构不会让用户的记录组织失效，反之亦然。

二、无结构文件（流式文件）

文件内部没有明确结构，就是一个字节流（byte stream）：按字节偏移量定位，典型例子是 .txt 文本与二进制可执行文件。Unix/Linux 中几乎所有文件都被视为流式文件。

三、有结构文件（记录式文件）

文件由一组记录（record）组成，每条记录由若干数据项（字段）构成，记录是文件存取的基本单位。

顺序文件

类型	排列方式	特点
串结构	按记录存入的先后顺序排列	检索需要逐个查找
顺序结构	按关键字递增/递减排列	定长记录时可以使用折半查找

操作	串结构	顺序结构
顺序读取	$O(n)$ 遍历	$O(n)$ 遍历
按关键字查找	$O(n)$ 逐个比较	$O(\log n)$ 折半查找（须定长）
插入新记录	追加到末尾 $O(1)$	需要移动记录以保持有序
删除记录	标记删除或移动	需要移动记录

顺序文件是对批量顺序处理效率最高的文件结构。磁带只能顺序存取，因此磁带上的文件只能是顺序文件。

索引文件

为每条记录建一个索引项，所有索引项构成索引表。索引表按关键字排序，且索引项本身定长（关键字 + 指针），所以索引表可以折半查找。

索引表                        主文件（记录区）
┌───────┬──────┐            ┌─────────────────┐
│关键字  │ 指针 │─────────► │  记录内容...     │
├───────┼──────┤            ├─────────────────┤
│关键字  │ 指针 │─────────► │  记录内容...     │
├───────┼──────┤            ├─────────────────┤
│关键字  │ 指针 │─────────► │  记录内容...     │
└───────┴──────┘            └─────────────────┘
  按关键字排序                 记录可以不连续

"只对变长记录划算"是"折半须定长"的直接推论：

记录类型	不建索引能不能随机访问	结论
定长	能。第 $k$ 条的偏移 $=k\times L$，一步算出	建索引表纯属多余
变长	不能。不逐条扫过去就不知道第 $k$ 条在哪	只有建索引表才能随机访问

插入代价的量级对比（设文件有 $N$ 条记录）：

	顺序结构的顺序文件	索引文件
插入一条记录要做什么	为保持有序，把插入点之后的记录整体后移	记录追加到主文件末尾，只在索引表里插一个索引项
移动的数据量	平均 $\frac{N}{2}$ 条完整记录（每条几十~几百字节）	平均 $\frac{N}{2}$ 个索引项（每项十几字节）
量级差	——	索引项比记录小一到两个数量级，搬的字节数也少一到两个数量级

两者的记录条数量级是一样的，差别在"搬的是记录还是索引项"——这就是"插入/删除只需修改索引表"的准确含义：不是变成 $O(1)$，而是每次搬动的数据量小了一到两个数量级。

索引顺序文件

顺序文件与索引文件的折中——类似字典的部首检字法：先按部首（稀疏索引，每组一项）缩小到某一组，再在组内顺序查找。

索引表（每组一项）          主文件
┌──────┬──────┐         ┌───────────────┐
│ 组1起│  →  │────────►│ 组1: s 条记录  │
├──────┼──────┤         ├───────────────┤
│ 组2起│  →  │────────►│ 组2: s 条记录  │
├──────┼──────┤         ├───────────────┤
│ 组3起│  →  │────────►│ 组3: s 条记录  │
└──────┴──────┘         └───────────────┘

平均检索长度取到 √N 的完整推导，以及推广到 L 级（想看清这个结论怎么来的、或题目改成两级索引时展开）

设文件共 $N$ 条记录，每组 $s$ 条，则组数 $g={\displaystyle \frac{N}{s}}$。两段是先后串行走的，所以代价相加而不是相乘；顺序查找长度为 $m$ 的表、命中位置均匀分布时平均比较 $\frac{m}{2}$ 次，两段各套一次这个结论：

$$f(s)=\underset{\text{索引表}}{\underbrace{\frac{g}{2}}}+\underset{\text{组内}}{\underbrace{\frac{s}{2}}}=\frac{N}{2s}+\frac{s}{2}$$

$f(s)$ 是"一个随 $s$ 减小的项 + 一个随 $s$ 增大的项"——组分得越少每组就越大，两段的代价此消彼长，所以中间必有最优点。对 $s$ 求导并令其为 0：

$$f^{\prime }(s)=-\frac{N}{2s^2}+\frac{1}{2}=0⟹s^2=N⟹s=\sqrt{N}$$

（也可用均值不等式 $\frac{N}{2s}+\frac{s}{2}\ge 2\sqrt{\frac{N}{4}}=\sqrt{N}$，等号在 $\frac{N}{2s}=\frac{s}{2}$ 即 $s=\sqrt{N}$ 时取到。）代回得组数 $g={\displaystyle \frac{N}{\sqrt{N}}}=\sqrt{N}$——每组的条数与组数相等，最小值恰为

$$f(\sqrt{N})=\frac{\sqrt{N}}{2}+\frac{\sqrt{N}}{2}=\sqrt{N}$$

$\sqrt{N}$ 不是一个要背的经验值，它是"两段代价相等"这个平衡点的结果。

以 $N=262144$ 为例，$s=g=512$，平均检索长度 512；不分组的顺序文件平均要查 $\frac{N}{2}=131072$ 条，加速比 ${\displaystyle \frac{131072}{512}}=256={\displaystyle \frac{\sqrt{N}}{2}}$——加速比本身也随 $N$ 增大，文件越大越划算。验算几个非最优的分法可以看到函数在最优点两侧对称上升：

每组 $s$	组数 $g$	平均检索长度
128	2048	$1024+64=1088$
256	1024	$512+128=640$
512	512	$256+256=\mathbf{\text{512}}$
1024	256	$128+512=640$
2048	128	$64+1024=1088$

推广到 $L$ 段：把索引表本身也分组、再为它建一张高级索引表，检索就要走三段。每段长度设为 $t$，则 $t^L=N$，即 $t=\sqrt[L]{N}$，平均检索长度 ${\displaystyle \frac{L}{2}}\sqrt[L]{N}$。同一个 $N=262144$ 下两级索引 $t=\sqrt[3]{262144}=64$，平均 $3\times \frac{64}{2}=96$，比一级的 512 又快约 5.3 倍。$L$ 增大能持续降低检索长度，代价是索引表层数增多、维护更复杂。

多级索引顺序文件的实现

ISAM（索引顺序存取方法）与 VSAM 是典型实现。这类文件通常还配一个溢出区，用来存放新增、被删和被修改的记录，避免每次插入都要移动主文件里的记录。

散列文件（Hash 文件）

用散列函数把关键字直接映射到记录的物理存储地址：$\text{地址}=H(\text{关键字})$。

冲突的三类处理办法与各自代价：

方法	做法	代价	什么时候用
链地址法（拉链）	每个地址挂一条链，冲突的记录串在同一条链上	检索退化为"算一次 + 沿链找"；链上记录不连续，可能多次读盘	最常用，装填因子较高也能工作
开放定址法（线性探测等）	冲突时按固定规则探测下一个地址，直到找到空位	会产生堆积——冲突记录扎堆占用后续地址，让本来不冲突的关键字也开始冲突	记录数已知且装填因子低时
溢出区法	主区放不下的记录统一放进专门的溢出区	溢出区里通常只能顺序查找，溢出越多越慢	文件系统里用得多（与索引顺序文件的溢出区同一思路）

四、四种逻辑结构对比

逻辑结构	判据：怎么由关键字找到记录	顺序存取	随机存取	平均检索长度	适用场景
顺序文件（串结构）	从头逐条比	最优	不支持	$N/2$	批量处理、磁带
顺序文件（顺序结构）	有序，定长记录可折半	最优	仅定长记录支持	${\log }_{2}N$（定长）	批量处理 + 偶尔查找
索引文件	折半查稠密索引表，指针直达	支持	支持	${\log }_{2}N$	变长记录、随机查询
索引顺序文件	顺序查稀疏索引定位到组，组内再顺序查	支持	支持	$\sqrt{N}$（一级）	大量记录、索引表也要省空间
散列文件	算出地址，不比较	不支持	支持	$\approx 1$（无冲突时）	快速单记录查找

考点速记

1. 逻辑结构 = 用户视角的记录组织方式；物理结构 = 系统视角的磁盘块摆放方式。 两者以"文件内偏移量"为公共接口，因此可任意组合、互不限制。
2. ⚠️索引文件 ≠ 索引分配：索引文件为记录建索引表（逻辑结构）；索引分配为磁盘块建索引块（物理结构）。名字像，层次不同。
3. 顺序文件的两种排列：串结构按存入先后排、顺序结构按关键字有序排。差别只出现在"按关键字查找"与"插入"两栏——顺序读取都要遍历，都是 $O(n)$。
4. 折半查找的前提是定长记录：折半要求"取第 $k$ 条"是 $O(1)$，即偏移量能由 $k\times L$ 一步算出。⚠️变长记录即使按关键字有序也不能折半。
5. 索引文件只对变长记录划算：定长记录本来就能算偏移，加索引纯属多余。索引文件的价值不是"更快"，而是把本来做不到的随机访问变成做得到。
6. 稠密索引 vs 稀疏索引：索引文件每条记录一项（稠密，可折半直达记录）；索引顺序文件每组一项（稀疏，只定位到组、组内再顺序找，索引表小到原来的 $\frac{1}{s}$）。
7. 索引顺序文件的 $\sqrt{N}$ 是两段代价相等的平衡点：每组 $s$ 条、组数 $g=\frac{N}{s}$，两段都顺序查找时平均检索长度 $f(s)=\frac{N}{2s}+\frac{s}{2}$，求极值得 $s=\sqrt{N}$，最小值恰为 $\sqrt{N}$。
8. 推广式：分成 $L$ 段时每段长 $\sqrt[L]{N}$ 最优，平均检索长度 $\frac{L}{2}\sqrt[L]{N}$。$L=1$ 得 $\frac{N}{2}$（顺序文件）、$L=2$ 得 $\sqrt{N}$、$L=3$ 得 $\frac{3}{2}\sqrt[3]{N}$——三个结论是同一个公式的三个取值。
9. ⚠️**$\sqrt{N}$ 是"两段都顺序查找"的口径**：索引表若改用折半，第一段就变成 $O(\log )$，结论也就不是 $\sqrt{N}$ 了。
10. 散列文件：地址 $=H(\text{关键字})$，一次计算直接定位、无需比较，理想 $O(1)$；⚠️不支持顺序存取——散列故意打散了关键字之间的序关系。
11. 冲突是必然的（关键字取值空间远大于地址空间）。三类处理：链地址法（挂链）、开放定址法（探测下一空位，会堆积，让本不冲突的也开始冲突）、溢出区法。

这一节在真题里被考过的形式：

文件的逻辑结构至今不单独成题，本页下方因此没有练习区。

它在大纲里（四（一）5），不能跳过，但投入要按"读懂即可"来定，理由有两条：

第一，它是"索引文件 vs 索引分配"这个分辨点的一半。 真题在 文件的物理结构那边反复考索引分配 （2009-28、2010-30、2015-29、2018-46、2022-45、2026-46 都是）， 而选项里常出现"索引文件""索引表"这类措辞。分清楚"给记录建索引"和"给磁盘块建索引" 是两层东西，是本节最实用的产出——速记第二条。

第二，它解释了"存取方式"为什么受限。 文件的基本概念 里说"隐式链接分配的文件只能顺序存取"，本节的第一条给出了它的另一半： 逻辑结构声明成什么不重要，能不能随机存取最终由物理结构决定。

复习优先级：读懂两条即可，不必手算。 一是速记第一、二条（两层的分界、 索引文件与索引分配不是一回事），二是速记第四条（折半要定长）。 $\sqrt{N}$ 那套推导属于数据结构的内容，在操作系统的真题里至今没出现过， 时间紧时可以跳过折叠层里的推导。

易错：把"索引文件"和"索引分配"当成一回事。前者给记录建索引（逻辑结构），后者给磁盘块建索引（物理结构）。

易错：认为按关键字有序就能折半查找。折半的前提是定长记录——变长记录算不出第 $k$ 条的偏移。

易错：认为给定长记录加索引能提速。定长记录本来就能算偏移，加索引纯属多占空间多一层间接。

易错：认为散列文件什么都快。它不支持顺序存取，因为散列故意打散了关键字的序关系。

易错：认为逻辑结构决定了能不能随机存取。最终由物理结构决定——隐式链接分配的文件只能顺序存取。

教材出处

• 汤小丹《计算机操作系统》印刷版 p231（7.2.5 索引顺序文件）：一级索引顺序文件"平均只要查找 $\sqrt{N}$ 个记录数，因而其检索效率 S 比顺序文件约提高 $\sqrt{N}/2$ 倍"，并举例"有一个顺序文件含有 10000 个记录，平均须查找的记录数为 5000 个。但对于索引顺序文件，则平均只须查找 100 个记录"；两级索引顺序文件"所需查找的记录数平均为 $50+50+50=150$，或者可表示为 $(3/2)\sqrt[3]{N}$"。教材是先给结论，本篇补上了由 $f(s)=\frac{N}{2s}+\frac{s}{2}$ 求极值得到 $s=\sqrt{N}$ 的推导。
• 同书 p230：索引顺序文件"增加了溢出（overflow）文件，用它来记录新增加的、删除的和修改的记录"；索引文件的代价是"除了有主文件外，还须配置一张索引表，而且每个记录都要有一个索引项，因此增加了存储开销"。

相关知识

文件的物理结构｜文件的基本概念｜文件的保护｜目录

上一篇文件的保护下一篇文件的物理结构

相关文章

• 文件的基本概念
• 文件元数据与索引节点
• 文件的操作
• 文件的保护
• 文件的物理结构
• 目录
• 硬链接和软链接
• 文件系统的全局结构
• 外存空闲空间管理
• 虚拟文件系统
• 文件系统挂载