文件的逻辑结构
文件管理有两层截然不同的问题：用户眼里文件内部长什么样，以及这些内容在磁盘上怎么放。
前者是逻辑结构，本节讨论；后者是物理结构，4.1.5 讨论。这两层从头到尾互不干涉——同一个逻辑结构可以配任何一种物理结构，这是本节最需要守住的边界。
机制
无结构文件与有结构文件
无结构文件又称流式文件，文件内部就是一串字符流，没有结构。文件的长度以字节为单位，操作系统不关心里面有没有”条目”、“行”、“记录”。
有结构文件又称记录式文件，由一组相似的记录组成。文件的长度以记录为单位，每条记录都由若干数据项构成。按记录长度是否固定，又分为定长记录与可变长记录。
有结构文件按记录的组织方式分类
// TODO 定长记录+变长记录
顺序文件的记录一个接一个地顺序排列。它内部又分两种组织：串结构指记录之间的顺序与关键字无关，通常按存入的时间先后排列；顺序结构指所有记录按关键字有序排列。
这个区分直接决定了查找效率：串结构只能从头顺序查找，而顺序结构因为有序，可以用折半查找。
索引文件为可变长记录文件建立一张索引表，每条记录对应一个索引项，索引项中记录了该记录的长度和指针。索引表本身按关键字排序，因而可以对索引表折半查找，从而实现对变长记录文件的随机访问。代价是索引表要占额外空间，且每条记录都要有一个索引项。
索引顺序文件是上面两者的折中，也是最常用的一种。它把记录分组，只为每组的第一条记录建立索引项。查找时先在索引表里定位到组，再在组内顺序查找。
直接文件（散列文件）通过散列函数由关键字直接算出记录的物理地址，不需要顺序查找，等值查找速度最快，但需要处理冲突，且不支持范围查询。
索引顺序文件为什么是折中的最优解
这一点用数字说话最清楚。设文件有
顺序文件顺序查找，平均要比较
索引顺序文件把记录分成
若为索引表再建一级索引（两级索引顺序文件），把结构做成
这组数字解释了索引顺序文件的地位：它用极小的空间代价，把顺序文件的线性查找变成了近似
记录成组与分解
逻辑记录通常远小于磁盘块——一条 100B 的记录，磁盘却以 512B 或 4KB 为单位读写。若一块只放一条记录，空间浪费巨大，I/O 次数也成倍增加。
记录成组指把若干条逻辑记录打包放进一个物理块，一个块中能放下的记录条数称为成组因子。记录分解则是相反的动作：读入一整块后，在内存中把其中某一条逻辑记录拆出来交给程序。
设物理块大小为
成组带来的代价是：修改一条记录也必须读入整块、在内存中改、再写回整块。 磁盘的最小读写单位是块，没有”只写 100 字节”这回事。这个代价是后面那道计算题的全部关键。
边界
”有结构”指的是操作系统知道记录边界
疑问点：有结构文件的具体形态
教材原文：“文件的逻辑结构中，有结构文件由一组相似的记录组成。” 有结构文件在实际系统中对应什么。
这个概念之所以难以落地，是因为现代通用操作系统几乎已经不提供它了。理解它的关键不是找例子，而是认清判据：
区分有结构与无结构的判据是”操作系统本身知不知道记录边界”，不是”文件内容有没有格式”。
一个 CSV 文件、一个 JSON 文件、一个 Excel 表格，内容显然是有格式的，但在 Linux 或 Windows 上它们统统是无结构文件——操作系统只把它们看作字节流，“第 3 行第 2 列”这个概念只存在于应用程序里，read 系统调用永远只能说”给我第 1000 到第 2000 个字节”。
真正的有结构文件是这样的：文件系统本身提供”读第 22 条记录”这样的调用，你不需要知道它在第几个字节。这类文件系统在 IBM 大型机（如 VSAM）和早期以磁带、批处理为背景的系统中是标准配置——因为那个年代没有数据库，成组、索引、按记录存取这些能力必须由操作系统自己提供。
后来数据库系统接管了这一切，操作系统就退回到只提供最简单的字节流抽象。这解释了为什么它在今天显得抽象：它描述的是一个操作系统与数据库尚未分家的年代。
408 中它仍是必考内容，考查方式是分类辨析（给出特征判断属于哪一类），而不是让你写代码。
记录长度可以不等
疑问点：同一文件中各记录的长度可以不相等
教材原文：“记录是对文件进行存取操作的单位，一个文件中各记录的长度可以不等。”
这句话成立，实现它的手段是把”长度”这个信息本身也存下来。 三种常见做法：
① 每条记录前加一个长度字段。 读的时候先读长度，再按这个长度读取记录体。这样即使各记录长短不一，也能一条接一条准确切分。
② 用分隔符标记记录结束。 文本文件用换行符分隔行，就是这种思路最朴素的形式。
③ 另设索引表记录每条记录的起始位置和长度。 这正是索引文件的做法——教材说索引文件”用于可变长记录文件”，原因就在这里。
为什么可变长记录必须靠索引才能随机访问：定长记录求第
逻辑结构与物理结构是两层，各由不同因素决定
疑问点：逻辑文件存放到存储介质上时组织形式的决定因素
逻辑文件存放到存储介质上时，采用的组织形式与（ ）有关。 A. 逻辑文件结构 B. 存储介质特性 C. 主存储器管理方式 D. 设备分配方式
答案 B。
题干问的是”存放到存储介质上采用的组织形式”，这说的是物理结构，而物理结构可选哪些，由介质本身的存取能力决定：
- 磁带只能顺序存取，因此在磁带上只能采用连续（顺序）结构，链接和索引都无从谈起——磁带没法”跳到第 500 块”。
- 磁盘可以随机存取，因此连续、链接、索引三种结构都可以用。
逐项排除：A 逻辑结构属于用户视角那一层，同一个顺序文件在磁盘上可以连续存放也可以链接存放，它并不限定物理组织；C 主存管理方式管的是内存，与外存文件的组织无关；D 设备分配方式解决的是”把哪台设备分给哪个进程”，属于第 5 章的内容，与文件内部结构无关。
顺序文件不等于连续分配
这是本节最高频的混淆，也是上一条的直接推论。
“顺序文件”是逻辑结构——记录在逻辑上一条接一条。“连续分配”是物理结构——盘块在磁盘上一块挨一块。
一个顺序文件完全可以采用链接分配或索引分配存放，它在磁盘上东一块西一块，但用户读到的记录顺序丝毫不变。反过来，一个无结构的流式文件也完全可以采用连续分配。
同理，“直接文件”（散列文件）与 UNIX inode 的”直接地址项”毫无关系——前者说的是用散列函数直接算出记录地址，是逻辑结构；后者说的是 inode 里不经过间接索引就指向数据块的那几个地址项，是物理结构。两个”直接”是同名异义。
修改一条记录要启动几次磁盘
疑问点：隐式链接分配下修改第 22 个逻辑记录的磁盘启动次数
- 设有一个记录文件，采用隐式链接分配方式，逻辑记录的固定长度为 100B，在磁盘上存储时采用记录成组分解技术。盘块长度为 512B。若该文件的目录项已经读入内存，则对第 22 个逻辑记录完成修改后，共启动磁盘（ ）次。 A. 3 B. 4 C. 5 D. 6
答案 D。 这道题把**逻辑结构（记录成组）和物理结构（隐式链接）**叠在一起考，必须分两步走。
第一步，用记录成组定位到”第几块”。
即第 22 条记录位于文件的第 5 个盘块，是该块内的第
第二步，用隐式链接算”读到第 5 块要几次”。
隐式链接的下一块指针藏在数据块内部，因此必须把前面的块一块一块读出来才能知道下一块在哪。目录项虽已在内存，但它只给出首块块号。所以要读第 1、2、3、4、5 块，共 5 次读。
第三步，写回。 记录成组意味着不能只写那 100B，必须把整个第 5 块写回，1 次写。
对照速查
| 无结构文件 | 有结构文件 | |
|---|---|---|
| 内部 | 字符流，无结构 | 一组相似的记录 |
| 长度单位 | 字节 | 记录 |
| 判据 | 操作系统不知道记录边界 | 操作系统知道记录边界 |
| 有结构文件子类 | 组织方式 | 查找 | 代价 |
|---|---|---|---|
| 顺序文件（串结构） | 按存入时间排列 | 只能顺序查找 | — |
| 顺序文件（顺序结构） | 按关键字有序 | 可折半查找 | 插入删除要移动记录 |
| 索引文件 | 每条记录一个索引项 | 折半查索引表 | 索引项与记录一样多 |
| 索引顺序文件 | 分组，每组首记录一个索引项 | 查索引定位组 → 组内顺序 | 最常用的折中 |
| 直接文件 / 散列文件 | 散列函数算地址 | 直接定位 | 要处理冲突，不支持范围查询 |
| 平均查找次数 | |
|---|---|
| 顺序文件 | |
| 索引顺序文件（1000×1000） | 1000 |
| 两级索引顺序文件（100×100×100） | 150 |
| 记录成组 | 公式 |
|---|---|
| 成组因子 | |
| 第 | |
| 块内序号 | |
| 代价 | 改一条记录也要读整块、写整块 |
考点
- 逻辑结构与物理结构是两层，物理组织由存储介质特性决定（选择题答案 B）
- 顺序文件 ≠ 连续分配；散列文件的”直接”≠ inode 的”直接地址项”
- 顺序文件的串结构只能顺序查找，顺序结构可折半
- 索引顺序文件最常用；
条记录：顺序 / 一级索引 1000 / 两级索引 150 - 索引文件用于可变长记录，因为变长记录算不出位置只能查表
- 记录成组三公式；改一条记录必须读整块写整块
- 成组题与隐式链接叠加时，定位块数的开销来自物理结构
链接
- 🏠 返回总览：操作系统第 4 章：文件管理总览
- ⬅️ 上一节：4.1.3 文件的操作
- ➡️ 下一节：4.1.5 文件的物理结构
- 📖 名词库：第 4 章名词库