illegalCreed

中文

English

中文

English

Appearance

文件分配与索引：连续、链接与 inode ​

基于通用操作系统概念 · 核于 2026-08

速查 ​

  • 核心问题：一个文件的数据存在磁盘哪些块上？如何记录这种映射？这决定是否支持随机访问、有无碎片、分配/释放效率。
  • 连续分配（Contiguous）：每个文件占一段连续的磁盘块，记录首块号 + 块数。✅ 顺序/随机访问都快（算偏移即可）；❌ 外部碎片严重（删删改改后空间被切碎，长文件放不下），需定期磁盘整理。
  • 链接分配（Linked）：每个文件是一个块链表，每块存下一块的指针，文件目录项只记首块号。✅ 无外部碎片（任意空闲块都能用）；❌ 不支持随机访问（要读第 N 块必须从头走 N 次），指针占空间，断链会丢数据。
  • 索引分配（Indexed）/ inode：为每个文件建一个索引表（inode），记录所有数据块号。✅ 支持随机访问（查索引直接定位）、无外部碎片；❌ 索引表本身占空间，大文件的索引表如何存是大问题。
  • inode（索引节点）：UNIX/Linux 的索引分配实现。每个文件一个 inode，存文件属性 + 12 个直接块指针 + 1 个一级间接 + 1 个二级间接 + 1 个三级间接指针。
  • 多级间接指针：小文件（≤12 块）用直接指针，访问最快；中/大文件用一级/二级/三级间接指针逐级索引——以可控的指针开销支持任意大小文件。
  • 大小文件寻址：以 4KB 块、4B 指针计——直接指针覆盖 48KB；一级间接 4MB；二级间接 4GB；三级间接 4TB。绝大多数文件很小，直接指针就够，所以 inode 方案对小文件高效。
  • 随机访问的本质：连续分配 = 偏移除以块大小加首块号；索引分配 = 查索引表第 N 项；链接分配不支持（必须顺序遍历）。
  • FAT（文件分配表）：链接分配的变种——把所有块的"下一块指针"集中到一张表（FAT）放内存，从而支持随机访问（查表），但表本身占内存。Windows 早期用 FAT32。
  • 分配方式选择：磁盘（HDD/SSD）普遍用索引/inode（随机访问 + 无碎片）；磁带等顺序介质才用链接/连续。

一、连续分配：快但有碎片 ​

连续分配让每个文件占据一段物理上相邻的磁盘块。文件的目录项只需记录首块号和块数：

   磁盘块号:   0    1    2    3    4    5    6    7    8
             ┌────┬────┬────┬────┬────┬────┬────┬────┬────┐
   内容:     │ A0 │ A1 │ A2 │    │ B0 │ B1 │    │    │    │
             └────┴────┴────┴────┴────┴────┴────┴────┴────┘
   文件 A: 首块=0, 块数=3    文件 B: 首块=4, 块数=2
  • 顺序访问快：磁头从首块连续读，无寻道。
  • 随机访问快：第 N 块 = 首块号 + N，直接定位。
  • 致命缺点——外部碎片：删除 B 后块 4-5 空出，但若要存 6 块的文件就放不下（中间的空洞太碎）。频繁增删后磁盘满是"小窟窿"，必须**磁盘整理（defragment）**把文件挪到一起——CD/DVD/早期磁盘用得多，SSD 上整理反而伤寿命。
  • 难增长：文件追加写时，若尾部块已被占用，要么挪整个文件，要么留外部碎片。

适用：CD-ROM、Swap 区（大小固定不增长）、磁带。通用 FS 很少纯用连续分配。

二、链接分配：无碎片但不能随机 ​

链接分配把文件做成磁盘块链表：每个数据块的末尾存下一个块的指针，目录项只记首块号（末块的指针为 NULL/-1）：

   文件 A 的链:  首块=2 → 2(下一块=5) → 5(下一块=8) → 8(下一块=-1)
        ┌────┐        ┌────┐        ┌────┐
   块2: │A0 │→5│  块5: │A1 │→8│  块8: │A2 │→-1│
        └────┘        └────┘        └────┘
  • 无外部碎片：任意空闲块都能用，磁盘空间利用率高。
  • 增长容易：追加写只需拿一个空闲块接到链尾。
  • 致命缺点——不支持随机访问：要读第 100 块必须从头顺指针读 99 次（每块可能散布在磁盘各处，磁头狂跳），慢得不可接受。这是链接分配被通用 FS 淘汰的主因。
  • 其他缺点：指针占空间（每块 4B，4KB 块约 0.1% 开销）；断链致命——一个指针损坏，后面数据全丢；可靠性差。

变种 FAT（文件分配表）：把全盘所有块的"下一块指针"集中到一张表（FAT），常驻内存，于是查第 N 块变成"在内存表里顺指针跳 N 次"——比读磁盘快，但仍是顺序跳。FAT32 是 Windows 9x/早期 U 盘的主流。

三、索引分配与 inode：UNIX/Linux 的选择 ​

索引分配为每个文件建一张索引表，列出它所有数据块的块号——像一本书的"页码索引"，查第 N 页直接看索引第 N 项：

   inode（索引表）
   ┌──────────────┐        数据块
   │ 块 0 → 200   │ ────▶  ┌────┐
   │ 块 1 → 201   │ ────▶  │... │
   │ 块 2 → 850   │ ────▶  │... │
   │ ...          │
   └──────────────┘
  • 支持随机访问：第 N 块 = 索引表第 N 项，一次查表定位。
  • 无外部碎片：任意空闲块都可用。
  • 难点——索引表怎么存：文件可能很大（几 GB），索引表也可能很大。UNIX 的解法是 inode + 多级间接指针。

四、inode 结构：多级间接指针 ​

inode（index node，索引节点） 是 UNIX/Linux 文件系统的元数据结构。每个文件唯一一个 inode（不论有多少个文件名/硬链接），它存储文件属性（大小/时间/权限/属主）+ 15 个块指针：

   inode（256B 等定长）
   ┌────────────────────────────┐
   │ 属性: 大小/权限/属主/时间... │
   ├────────────────────────────┤
   │ 0~11: 直接块指针（12 个）    │ ──▶ 数据块 0~11
   │ 12:   一级间接指针           │ ──▶ 间接块(装指针) ──▶ 数据块 12~(12+N)
   │ 13:   二级间接指针           │ ──▶ 间接块 ──▶ 间接块 ──▶ 数据块
   │ 14:   三级间接指针           │ ──▶ 三层间接 ──▶ 数据块
   └────────────────────────────┘

以块大小 4KB、指针 4B 为例（一个间接块可装 4KB/4B = 1024 个指针）：

指针类型指针数覆盖块数覆盖容量
直接（12 个）121212 × 4KB = 48 KB
一级间接（1 个）110241024 × 4KB = 4 MB
二级间接（1 个）11024 × 10241024² × 4KB ≈ 4 GB
三级间接（1 个）11024³1024³ × 4KB ≈ 4 TB

设计精髓：

  • 绝大多数文件很小（统计显示多数文件 < 几 KB），12 个直接指针就够，小文件访问只需一次读 inode——高效。
  • 大文件逐级启用间接指针：每多一级间接，寻址多一次磁盘读（读间接块），是时间换空间的取舍。
  • 随机访问大文件：算出目标块落在哪一级（直接/一级/二级/三级），再沿指针定位，仍只需 1~4 次磁盘读。
c
// 简化：在 inode 中定位第 logical_block 块的物理块号
if (logical_block < 12)
    phys = inode->direct[logical_block];          // 直接
else if (logical_block < 12 + 1024)              // 一级间接
    phys = read_indirect(inode->indirect, logical_block - 12);
else if (...)                                     // 二级、三级间接
    ...

五、对比与选型 ​

分配方式随机访问碎片增长代价代表
连续✅ 最快❌ 严重外部碎片❌ 难需磁盘整理CD-ROM、Swap
链接❌ 不支持✅ 无✅ 易指针开销、断链风险FAT（变种）、早期 FS
索引/inode✅ 支持✅ 无✅ 易索引表开销、大文件多级寻址EXT4、UFS、NTFS

通用磁盘 FS（HDD/SSD）几乎都用索引分配（inode 思路）——因为现代应用（数据库、虚拟机镜像、索引）强依赖随机访问，链接分配的"只能顺序读"无法接受。

下一步 ​

搞清数据怎么存（分配方式 + inode）后，下一步看文件怎么组织与共享——目录结构与链接（树形目录、绝对/相对路径、软链接 vs 硬链接的本质区别、空闲空间管理、EXT4/NTFS/APFS 对比）。