文件系统：逻辑结构、目录、实现

概念

文件（file）是具有符号名的一组相关信息的集合——它是用户眼里最小的"存取单位"。

文件系统（file system）是操作系统中负责管理文件的那部分软件与数据结构的集合，它要解决的核心问题是 "按名存取"：

用户只写 read("a.txt", ...)，不需要知道 a.txt 在第几个盘面、第几条磁道、第几个扇区。把"名字"翻译成"物理位置"，就是文件系统的全部工作。

一句话说清它是什么：文件系统是"名字"与"盘块"之间的一层翻译官——它把一堆散落在磁盘上的物理块，伪装成一个有层次的、有名字的、可以按名访问的树。

视角	文件系统要回答的问题
面向用户	这个文件叫什么？在哪个目录下？能不能读写？
面向存储	这个文件的第 100 个字节，落在哪个盘块上？
面向整体	哪些盘块还空着？目录树长什么样？空间怎么回收？

⚠️ 与 os/31-disk.md 的分工：本章管"文件怎么组织"（逻辑结构 + 目录 + 物理分配）；下一章管"磁盘空间怎么管理"（磁盘结构 + 空闲空间管理 + 调度）。两章合起来才是完整的"文件与磁盘"。

原理

一、文件的逻辑结构：用户看到的样子

逻辑结构 = 文件内部数据怎么排，它独立于物理存储。

   无结构文件(流式)                    有结构文件(记录式)
   ┌──────────────────────────┐        ┌────────┬────────┬────────┐
   │ 一串字节，无边界          │        │ 记录1  │ 记录2  │ 记录3  │
   │ "hello world..."          │        └────────┴────────┴────────┘
   └──────────────────────────┘        （定长 或 变长）
     C 源码、可执行文件、图片            数据库表、成绩单

有结构文件按"记录怎么排"再分四类：

类型	组织方式	查找一条记录	典型场景
顺序文件	记录一个接一个（顺序存储）	定长 + 已排序 → 折半查找 $O({\log }_{2}n)$；否则顺序扫描 $O(n)$	日志、批处理数据
索引文件	建一张索引表：(关键字, 记录指针)	先查索引表（折半）再取记录	需要按键随机访问
索引顺序文件	分组：组内顺序，组间建索引	折半查索引 + 组内顺序扫，$O(\sqrt{n})$ 级	ISAM，兼顾两者
直接文件/散列文件	由关键字直接算出地址（Hash）	理想情况 $O(1)$，但有冲突	符号表、字典

⚠️ 顺序文件的定长/变长之别（高频陷阱）：

• 定长记录可以"序号 × 长度"直接定位，支持随机访问。
• 变长记录必须从头扫，每条记录还要额外存一个长度字段。 "顺序文件只能顺序访问"是错的——定长顺序文件照样能算出第 i 条记录的偏移。

二、目录：名字到 FCB 的映射

目录本质是一张表，表项叫目录项；目录项里的核心内容是文件控制块（FCB，file control block）。

FCB 里存什么（这是"文件存在的唯一标志"）：

   FCB
   ├── 基本信息: 文件名 / 物理位置 / 逻辑结构 / 物理结构
   ├── 存取控制: 读/写/执行 权限, 属主
   └── 使用信息: 建立时间 / 修改时间 / 当前打开计数

目录结构四代演进：

结构	特点	优点	缺点
单级目录	全盘一张表	实现最简单	不允许重名；n 个用户要查 n 次
两级目录	主目录（用户）+ 用户目录	不同用户可重名；便于隔离与授权	用户之间仍不能分类
树形目录	多级，支持子目录	分类清晰、层次分明；可用路径名定位	不便于文件共享（同一文件出现多份副本）
无环图目录	树 + 共享结点（硬链接/软链接）	文件可共享，只有一份副本	要维护引用计数，删除时机复杂

检索目录项的开销（必算）：单级目录有 $n$ 个目录项，查找一个文件平均要比较

$$\text{平均比较次数}=\frac{n+1}{2}$$

目录实现两法（索引结点的由来）：

   ① 目录项 = 文件名 + 完整 FCB（传统做法）
      查目录时要把整个 FCB 读进来 → 目录项很大 → 检索一个文件要读很多盘块

   ② 目录项 = 文件名 + 索引结点号（UNIX 做法）
      FCB 拆出来单独存（叫索引结点 inode），目录里只留"名字 + 编号"
      目录项瘦身到十几字节 → 一个盘块能放几百项 → 检索快得多

⚠️ "把 FCB 拆成索引结点"解决的是"目录检索慢"这一个问题，不是"省空间"（FCB 本身还得存）。它是"用一次间接寻址换目录项瘦身"，这个设计动机常被考成简答题。

三、文件的物理结构：盘块上怎么摆

盘块（block / 簇）是文件系统分配磁盘空间的最小单位，通常是扇区的整数倍（如 4 KB）。

三种分配方式（本节是真题主战场）：

   ① 连续分配
      ┌────┬────┬────┬────┬────┐
      │ b7 │ b8 │ b9 │ b10│ b11│   目录项只存 (起始块 7, 长度 5)
      └────┴────┴────┴────┴────┘
      优点: 支持随机访问(直接算), 顺序读最快
      缺点: 外部碎片; 文件增长困难

   ② 链接分配(隐式)
      ┌────┬──┐   ┌────┬──┐   ┌────┬──┐
      │ b7 │→ │   │ b3 │→ │   │ b9 │ /│
      └────┴──┘   └────┴──┘   └────┴──┘
      优点: 无外部碎片, 文件增长方便
      缺点: ★ 只能顺序访问(读第 i 块要读 i 次盘); 指针占空间; 链接断了全丢

   ③ 索引分配
      索引块: ┌────┬────┬────┬────┐
              │ b7 │ b3 │ b9 │ b2 │  → 目录项存"索引块号"
              └────┴────┴────┴────┘
      优点: 支持随机访问, 无外部碎片
      缺点: 索引块本身占空间; 大文件要"多级索引"或"混合索引"

链接分配的改良：显式链接（FAT）——把散落各块的指针集中成一张表，整张表常驻内存：

   FAT (整张表在内存)
   ┌──────┬────────┐
   │ 块号 │ 下一块 │
   ├──────┼────────┤
   │  7   │   3    │
   │  3   │   9    │
   │  9   │  EOF   │
   └──────┴────────┘
   读第 i 块: 在内存里查表 i 次 → 不需要额外读盘 → 支持"逻辑上的随机访问"

⚠️ 隐式链接 vs 显式链接（FAT）的判据只有一条：指针放在盘块里（隐式）还是放在内存表里（显式）。FAT 把"读盘 i 次"变成"查内存 i 次"，这才是它存在的意义。

四、混合索引：一个 inode 能寻址多大

真实文件系统（如 UNIX 的经典 inode）用 "直接 + 多级间接"混合：小文件走直接块（快），大文件自动下钻到间接块。

设 inode 有 13 个地址项：10 个直接 + 1 个一级间接 + 1 个二级间接 + 1 个三级间接；盘块 4 KB，块地址 4 B，则每块能存

$$\frac{4096}{4}=1024\text{ 个块号}$$

项	覆盖逻辑块数	覆盖字节数	算式
10 个直接	10	40 KB	$10\times 4096$
一级间接	1024	4 MB	$1024\times 4096$
二级间接	1048576	4 GB	${1024}^2\times 4096$
三级间接	1073741824	4 TB	${1024}^3\times 4096$

可寻址逻辑块总数 = $10+1024+1048576+1073741824=\mathbf{1074791434}$ 块，最大文件 ≈ 4.004 TB。

⚠️ 逻辑块号区间（0-based，考试默认从 0 编号）：

• 直接：0 ~ 9
• 一级间接：10 ~ 1033
• 二级间接：1034 ~ 1049609
• 三级间接：1049610 ~ 1074791433

区间边界全部是"上界 + 1"递推，写错一位整题作废。做题时先在草稿纸写下这四个区间，再代入题目给的块号。

示例

例 1：C 实现——混合索引的逻辑块定位

参数：盘块 4 KB、块地址 4 B、inode 13 项（10 直接 + 三级间接）。 要求：给定一个 0-based 逻辑块号，判断它在哪一段、要额外读几个索引块。

#include <stdio.h>

#define BLK   4096          /* 盘块大小(字节) */
#define ADR   4             /* 块地址宽度(字节) */
#define PER   (BLK / ADR)   /* 每块可存块号数 = 1024 */
#define DIRECT 10

/* 逻辑块 n(0-based) 落在哪一段？返回 "要多读的索引块个数" */
static int indirect_blocks(long n) {
    long hi_direct = DIRECT - 1;                    /* 9 */
    long hi_l1     = DIRECT + PER - 1;              /* 1033 */
    long hi_l2     = hi_l1 + (long)PER * PER;       /* 1049609 */
    /* long hi_l3 = hi_l2 + (long)PER*PER*PER;  理论最大 1074791433 */

    if (n <= hi_direct) return 0;   /* 直接块 */
    if (n <= hi_l1)     return 1;   /* 一级间接 */
    if (n <= hi_l2)     return 2;   /* 二级间接 */
    return 3;                       /* 三级间接 */
}

static const char *seg_name(int k) {
    switch (k) {
    case 0: return "直接";
    case 1: return "一级间接";
    case 2: return "二级间接";
    default: return "三级间接";
    }
}

int main(void) {
    long probes[] = {0, 9, 10, 1033, 1034, 300000, 1049609, 1049610};
    int  i, k;

    printf("盘块 %d B, 块地址 %d B -> 每块存 %d 个块号\n", BLK, ADR, PER);
    printf("直接 10 块 = %d KB; 一级 %d 块 = %d MB\n",
           DIRECT * BLK / 1024, PER, PER * BLK / 1024 / 1024);
    printf("二级 %ld 块 = %ld GB; 三级 %ld 块 = %ld TB\n\n",
           (long)PER * PER, (long)PER * PER * BLK / 1024 / 1024 / 1024,
           (long)PER * PER * PER,
           (long)PER * PER * PER * BLK / 1024 / 1024 / 1024 / 1024);

    for (i = 0; i < 8; i++) {
        k = indirect_blocks(probes[i]);
        printf("逻辑块 %ld -> %s, 索引块 %d 个, 含数据块共访存 %d 次\n",
               probes[i], seg_name(k), k, k + 1);
    }
    return 0;
}

c 本站为静态站，不提供在线运行；可复制到本地用 gcc / python 执行

预期输出：

盘块 4096 B, 块地址 4 B -> 每块存 1024 个块号
直接 10 块 = 40 KB; 一级 1024 块 = 4 MB
二级 1048576 块 = 4 GB; 三级 1073741824 块 = 4 TB

逻辑块 0 -> 直接, 索引块 0 个, 含数据块共访存 1 次
逻辑块 9 -> 直接, 索引块 0 个, 含数据块共访存 1 次
逻辑块 10 -> 一级间接, 索引块 1 个, 含数据块共访存 2 次
逻辑块 1033 -> 一级间接, 索引块 1 个, 含数据块共访存 2 次
逻辑块 1034 -> 二级间接, 索引块 2 个, 含数据块共访存 3 次
逻辑块 300000 -> 二级间接, 索引块 2 个, 含数据块共访存 3 次
逻辑块 1049609 -> 二级间接, 索引块 2 个, 含数据块共访存 3 次
逻辑块 1049610 -> 三级间接, 索引块 3 个, 含数据块共访存 4 次

⚠️ 三点说明：

1. PER 用宏而不是常量 1024——题目换页大小时只需改两个宏，这也是"参数化"这一工程习惯在算法题里的体现。
2. hi_l2 用的是二级间接的"最后一块号"，不是"块数"。10 + 1024 = 1034 是一级间接的起点、10 + 1024 - 1 = 1033 才是它的终点——"起点用加法、终点减 1"是这类题最常写错的地方。
3. 本机无 C 编译器：此段代码逐行人工审查，并用等价的 Python 实现（下例）实跑核对，8 行输出逐行一致。

例 2：Python——inode 容量、目录检索、三种分配的访存对比

import math

BLK, ADR = 4096, 4
PER = BLK // ADR
DIRECT = 10

print('=== ① 混合索引: 一个 inode 能寻址多大 ===')
segs = [('直接 10 块', DIRECT, 0),
        ('一级间接', PER, 1),
        ('二级间接', PER ** 2, 2),
        ('三级间接', PER ** 3, 3)]
tot_blocks = 0
for name, cnt, k in segs:
    size = cnt * BLK
    tot_blocks += cnt
    unit = 'B'
    v = size
    for u in ['KB', 'MB', 'GB', 'TB']:
        if v >= 1024:
            v /= 1024.0
            unit = u
    print('  %-10s %10d 块  %12d B = %8.1f %s' % (name, cnt, size, v, unit))
print('  合计可寻址 %d 块 = %d B = %.4f TB'
      % (tot_blocks, tot_blocks * BLK, tot_blocks * BLK / 1024 ** 4))
print('  32 位逻辑块号上限 %d 块 -> 本方案 %d 块，%s'
      % (2 ** 32 - 1, tot_blocks, '未超上限' if tot_blocks < 2 ** 32 else '超上限'))
print()

print('=== ② 逻辑块号区间(0-based) 与访存次数 ===')
hi_direct = DIRECT - 1
hi_l1 = DIRECT + PER - 1
hi_l2 = hi_l1 + PER ** 2
hi_l3 = hi_l2 + PER ** 3
for name, lo, hi, k in [('直接', 0, hi_direct, 0),
                        ('一级间接', DIRECT, hi_l1, 1),
                        ('二级间接', hi_l1 + 1, hi_l2, 2),
                        ('三级间接', hi_l2 + 1, hi_l3, 3)]:
    print('  %-8s 逻辑块 %10d ~ %10d  (共 %11d 块)  访存 %d 次'
          % (name, lo, hi, hi - lo + 1, k + 1))
print('  区间闭合校验: %d == %d -> %s' % (hi_l3, tot_blocks - 1, hi_l3 == tot_blocks - 1))
print()


def probe(n):
    if n <= hi_direct:
        return 0
    if n <= hi_l1:
        return 1
    if n <= hi_l2:
        return 2
    return 3


print('=== ③ 顺序查找单级目录的平均比较次数 ===')
for n in [10, 50, 100, 1000]:
    print('  目录项 %4d 个 -> 平均比较 (n+1)/2 = %7.1f 次, 最坏 %d 次'
          % (n, (n + 1) / 2.0, n))
print()

print('=== ④ 三种物理分配: 读"第 100 个逻辑块"的访存/读盘代价 ===')
N = 100
print('  文件共 %d 个逻辑块, 盘块 4 KB' % N)
print('  连续分配: 直接算地址 -> 读盘 1 次 (寻道+旋转各 1 次)')
print('  链接分配(隐式): 必须从第 1 块起沿指针走 -> 读盘 %d 次, 其中仅最后一块有用' % N)
print('  显式链接(FAT): FAT 常驻内存 -> 查内存 %d 次, 读盘仅 1 次' % N)
print('  索引分配: 读索引块 1 次 + 读数据块 1 次 -> 读盘 2 次')
print()

print('=== ⑤ 索引结点带来的"目录瘦身"收益 ===')
NFILE = 4096    # 固定 4096 个文件
ecb = 64        # 传统做法: 目录项含完整 FCB
ino = 16        # UNIX 做法: 目录项只含 文件名 + inode 号
print('  固定 %d 个文件, 盘块 %d B' % (NFILE, BLK))
t_ecb, t_ino = NFILE * ecb, NFILE * ino
avg = (NFILE + 1) / 2.0
print('    传统(每项 %d B): 目录占 %6d B = %3d KB = %2d 个盘块'
      % (ecb, t_ecb, t_ecb // 1024, t_ecb // BLK))
print('    索引结点(每项 %d B): 目录占 %6d B = %4d KB = %2d 个盘块'
      % (ino, t_ino, t_ino // 1024, t_ino // BLK))
print('    目录体积缩小到 1/%d' % (t_ecb // t_ino))
print('    平均比较 %.1f 次 -> 平均扫到 %d B (约 %d 盘块) vs %d B (约 %d 盘块)'
      % (avg, avg * ecb, math.ceil(avg * ecb / BLK), avg * ino, math.ceil(avg * ino / BLK)))

python 本站为静态站，不提供在线运行；可复制到本地用 gcc / python 执行

输出对照（真实运行结果）：

=== ① 混合索引: 一个 inode 能寻址多大 ===
  直接 10 块            10 块         40960 B =     40.0 KB
  一级间接             1024 块       4194304 B =      4.0 MB
  二级间接          1048576 块    4294967296 B =      4.0 GB
  三级间接       1073741824 块  4398046511104 B =      4.0 TB
  合计可寻址 1074791434 块 = 4402345713664 B = 4.0039 TB
  32 位逻辑块号上限 4294967295 块 -> 本方案 1074791434 块，未超上限

=== ② 逻辑块号区间(0-based) 与访存次数 ===
  直接       逻辑块          0 ~          9  (共          10 块)  访存 1 次
  一级间接     逻辑块         10 ~       1033  (共        1024 块)  访存 2 次
  二级间接     逻辑块       1034 ~    1049609  (共     1048576 块)  访存 3 次
  三级间接     逻辑块    1049610 ~ 1074791433  (共  1073741824 块)  访存 4 次
  区间闭合校验: 1074791433 == 1074791433 -> True

=== ③ 顺序查找单级目录的平均比较次数 ===
  目录项   10 个 -> 平均比较 (n+1)/2 =     5.5 次, 最坏 10 次
  目录项   50 个 -> 平均比较 (n+1)/2 =    25.5 次, 最坏 50 次
  目录项  100 个 -> 平均比较 (n+1)/2 =    50.5 次, 最坏 100 次
  目录项 1000 个 -> 平均比较 (n+1)/2 =   500.5 次, 最坏 1000 次

=== ④ 三种物理分配: 读"第 100 个逻辑块"的访存/读盘代价 ===
  文件共 100 个逻辑块, 盘块 4 KB
  连续分配: 直接算地址 -> 读盘 1 次 (寻道+旋转各 1 次)
  链接分配(隐式): 必须从第 1 块起沿指针走 -> 读盘 100 次, 其中仅最后一块有用
  显式链接(FAT): FAT 常驻内存 -> 查内存 100 次, 读盘仅 1 次
  索引分配: 读索引块 1 次 + 读数据块 1 次 -> 读盘 2 次

=== ⑤ 索引结点带来的"目录瘦身"收益 ===
  固定 4096 个文件, 盘块 4096 B
    传统(每项 64 B): 目录占 262144 B = 256 KB = 64 个盘块
    索引结点(每项 16 B): 目录占  65536 B =   64 KB = 16 个盘块
    目录体积缩小到 1/4
    平均比较 2048.5 次 -> 平均扫到 131104 B (约 33 盘块) vs 32776 B (约 9 盘块)

五条结论：

1. 直接块只覆盖 40 KB，一级间接就跳到 4 MB，二级 4 GB，三级 4 TB——每下一级，容量乘 1024。这个"指数级跳变"就是混合索引的设计精髓：小文件用便宜的直接块，大文件才付出下钻代价。
2. 逻辑块号区间必须"起点 = 上一段终点 + 1"，四段拼起来正好填满 0 ~ 1074791433（脚本最后一行 True 就是这个闭包校验）。
3. 访存次数 = 索引块个数 + 1：直接 1 次、一级间接 2 次、二级 3 次、三级 4 次——"数据块本身也要访存一次"最容易被漏掉（注意：若 inode 本身也不在内存，还要再加 1 次）。
4. 读第 100 个逻辑块的代价：连续分配 1 次、索引分配 2 次、显式链接（FAT）1 次读盘 + 100 次查内存、隐式链接 100 次读盘。这就是"链接分配不支持随机访问"的量化表述。
5. 目录项从 64 B 瘦到 16 B，同一个目录能装的项数放大 4 倍（1024 → 4096）——"瘦身"的直接收益是"检索一个文件平均要读的盘块数下降"，这在目录很大时非常明显。

考点

考点

1. 必背结论

• 文件 = 有符号名的一组相关信息的集合；FCB 是文件存在的唯一标志。
• 文件系统解决"按名存取"——用户给名字，系统负责翻译成物理位置。
• 逻辑结构 vs 物理结构：逻辑结构面向用户（文件内部怎么排），物理结构面向存储（盘块上怎么摆）——两者独立，可自由组合。
• 有结构文件四分：顺序文件（折半要求"定长 + 有序"）/ 索引文件 / 索引顺序文件（$O(\sqrt{n})$）/ 直接文件（散列，$O(1)$ 理想）。
• 目录四代：单级（不可重名）→ 两级（用户间可重名）→ 树形（分类清晰但不便共享）→ 无环图（可共享，要引用计数）。
• 单级目录平均比较次数 $(n+1)/2$，最坏 $n$ 次。
• 索引结点（inode）= 把 FCB 从目录项里拆出来单独存，目录项只剩"文件名 + 编号"——目的是加快目录检索，不是省空间。
• 三种物理分配：连续（随机访问最快、有外部碎片）/ 链接（无外部碎片、只能顺序读）/ 索引（支持随机访问、索引块占空间）。
• 显式链接（FAT）把指针集中成内存表：读第 i 块从"读盘 i 次"变成"查内存 i 次"。
• 锚点（inode 13 项 / 盘块 4 KB / 地址 4 B / 每块 1024 个块号）： 直接 10 块 = 40 KB；一级 1024 块 = 4 MB；二级 1048576 块 = 4 GB；三级 1073741824 块 = 4 TB； 可寻址 1074791434 块，最大文件 ≈ 4.0039 TB。
• 锚点（逻辑块号区间 0-based）：直接 0~9、一级间接 10~1033、二级 1034~1049609、三级 1049610~1074791433。
• 锚点（访存次数）：直接 1 次、一级间接 2 次、二级 3 次、三级 4 次（inode 不在内存时全部再加 1）。

2. 高频陷阱

• 把"逻辑结构"与"物理结构"混为一谈：错。逻辑结构是用户视角（记录怎么排），物理结构是存储视角（盘块怎么放）——同一个逻辑结构可以配任意物理结构。
• 说"顺序文件只能顺序访问"：错。定长记录的顺序文件可以用"序号 × 长度"直接定位，支持随机访问；只有变长记录才必须从头扫。
• 认为"树形目录能方便地共享文件"：错。树形目录里共享要靠"复制副本"，改一份另一份不同步——要共享必须用无环图目录（硬链接/软链接）。
• 说"目录项里必须存完整 FCB"：错。UNIX 把 FCB 拆成索引结点，目录项只存"名字 + 结点号"——检索时只需读瘦身后的目录项，FCB 真的要用时才按结点号去取。
• 把索引结点当成"省空间的手段"：不准确。FCB 本身照存，省的是目录项的体积，收益是"目录检索更快"——总空间反而可能略增（多了一层编号）。
• 算容量时把"每块能存多少块号"算错：注意是 $\text{盘块大小}÷\text{地址宽度}$，与"文件逻辑块大小"无关；盘块 4 KB + 地址 4 B → 1024 个块号，不是 4096 个。
• 逻辑块号区间"起点/终点"错位：直接块是 0~9（10 个），一级间接是 10~1033（1024 个）——写成 10~1034 就多算了一个块。10 + 1024 = 1034 是下一段的起点，不是本段的终点。
• 算访存次数漏掉数据块本身：读一个二级间接块 = 读一级索引块 + 读二级索引块 + 读数据块 = 3 次，不是 2 次。
• 认为"连续分配一定最好"：错。它有外部碎片、且文件增长困难（要么预留空间浪费，要么搬迁整个文件）——现代文件系统多采用"索引 + 区段（extent）"的折中。
• 把"盘块"与"扇区"当成同一个东西：扇区是硬件单位（通常 512 B），盘块是文件系统的分配单位（通常 4 KB = 8 个扇区）——两者相差一个整数倍。
• 说"删除文件就是把盘块清零"：错。只需把"目录项 + 索引结构 + 位示图/空闲表"里的记录清掉，盘块里的旧数据照旧存在（这既是"误删可恢复"的原理，也是"涉密数据必须覆写"的原因）。

3. 解题模板（"文件系统计算题"）

① 认参数: 盘块大小、块地址宽度 -> 每块块号数 = 盘块 / 地址宽度
② 算区间(0-based):
     直接     0        ~ (D-1)
     一级间接 D        ~ (D + P - 1)
     二级间接 (D+P)    ~ (D + P + P^2 - 1)
     三级间接 ……        直到 D + P + P^2 + P^3 - 1
     (D = 直接块数, P = 每块块号数)
③ 换算字节数: 块数 × 盘块大小
④ 定访存次数: 索引块个数 + 1 (数据块), inode 不在内存再加 1
⑤ 若问"目录检索": 单级目录平均比较 (n+1)/2 次;
     两级/树形目录按"逐级查目录"把各级的 (n_i+1)/2 相加
⑥ 若问"物理分配对比": 连续 1 次读盘; 索引 "索引块 + 数据块";
     隐式链接 i 次读盘; 显式链接 1 次读盘 + i 次查内存

4. 与相邻章节的接口

• os/31-disk.md（磁盘组织与空闲空间管理）：本章的"盘块"就是那章的分配对象；本章说"文件用哪些块"，那章说"哪些块还空着"（位示图 / 空闲表 / 成组链接）。
• os/23-virtual.md（虚拟内存）："文件按页缓存"就是虚拟内存的"文件页"；页面置换时"脏页要写回文件"，写回的就是本章的物理结构。
• os/32-io.md（I/O 管理）：读一个文件要经过"文件系统 → 设备独立性软件 → 设备驱动"——本章在最上层，那章管"怎么把请求送到设备"。
• ds/31-btree.md（B 树）：大型目录常用 B+ 树组织——Linux 的 ext4 用 H 树（B 树变体）管理大目录，这就是"目录检索快"的另一条路。
• arch/13-virtual.md（虚拟存储器）："页表"和"索引结点"是同一种思想的两个实例——都是"用一层间接把稀疏的地址空间映射到物理块"。
• lang/24-image.md（装载）：execve 读 ELF 靠的是文件系统的"随机读"——这正是"索引分配支持随机访问"在实际系统里的用途。

小结

• 文件系统 = "名字 ↔ 盘块"的翻译官，核心目标是按名存取。
• 逻辑结构（顺序 / 索引 / 索引顺序 / 散列）面向用户；物理结构（连续 / 链接 / 索引）面向盘块——两者互相独立。
• 目录四代：单级 → 两级 → 树形 → 无环图；索引结点把 FCB 从目录项里拆出来，专治"目录检索慢"。
• 锚点（inode 13 项 / 盘块 4 KB / 地址 4 B）：直接 40 KB、一级 4 MB、二级 4 GB、三级 4 TB，最大文件 ≈ 4.0039 TB。
• 锚点（逻辑块区间 0-based）：0~9 / 10~1033 / 1034~1049609 / 1049610~1074791433；访存次数 = 索引块数 + 1。
• 三种分配一句话：连续最快但有碎片、链接无碎片但只能顺序读（FAT 用内存表补救）、索引两头兼顾但索引块占空间。
• 本章是"文件与设备"这条支线的第一站：文件怎么组织（30）→ 磁盘空间怎么管理（31）→ I/O 怎么送到设备（32）→ 磁头怎么调度（33）。

下一篇：磁盘组织与空闲空间管理