索引文件结构与容量计算¶

这部分属于 操作系统 → 文件管理 → 文件的物理结构与索引分配。这里的“索引”记录文件数据块在磁盘上的位置；它与数据库索引、按记录建立索引的逻辑文件结构不是同一层面的概念。

1. 索引块里存什么¶

一个文件可以占用不连续的磁盘块。文件系统把文件看成按顺序排列的逻辑块，再通过索引找到各逻辑块实际位于哪个磁盘块。

数据块：存放文件内容，例如图片的二进制数据。
索引块：存放磁盘块地址，用来找到数据块或下一层索引块。
索引结点（inode）等文件元数据：保存文件属性和块地址入口。

例如，文件的逻辑块 0、1、2 分别位于磁盘块 108、25、300。读取文件时按逻辑顺序取回这些块，就能得到原来的内容，不要求磁盘块号连续。

2. 直接、一级间接、二级间接、三级间接¶

方式	查找路径	一个入口能定位的数据块数
直接地址	inode → 数据块	1
一级间接	inode → 索引块 → 数据块	q
二级间接	inode → 第一层索引块 → 第二层索引块 → 数据块	q²
三级间接	inode → 三层索引块 → 数据块	q³

q 表示 一个索引块能放多少个完整的块地址：

1	`q = ⌊索引块大小 / 一个块地址所占的字节数⌋`

⌊x⌋ 表示向下取整。剩下的空间如果不足以保存一个完整地址，就不能再算一个地址项。

下面按题目惯例使用 1 KB = 1024 B。设数据块大小为 B，inode 中有 D 个直接地址、S 个一级间接入口、T 个二级间接入口、U 个三级间接入口，则：

1 2	`最多可寻址的数据块数 = D + S × q + T × q² + U × q³ 最大文件数据长度 = 数据块数 × B`

索引块本身不算文件数据长度。 如果问的是文件实际占用的磁盘空间，才需要另外计算索引块等开销。理论最大长度还可能受到文件系统实现、地址位宽和磁盘容量限制。

3. 例题：5 个直接地址、2 个一级间接、1 个二级间接¶

题设：索引块和数据块都为 1 KB，一个块地址占 4 B。inode 有 8 个地址项：

addr[0]～addr[4]：5 个直接地址。
addr[5]、addr[6]：2 个一级间接入口。
addr[7]：1 个二级间接入口。

先求每个索引块的地址项数：

1	`q = 1024 / 4 = 256`

文件的逻辑块号从 0 开始，各入口覆盖范围如下：

地址项	方式	数据块数	文件逻辑块号范围
addr[0]～addr[4]	直接地址	5	0～4
addr[5]	一级间接	256	5～260
addr[6]	一级间接	256	261～516
addr[7]	二级间接	256² = 65536	517～66052

因此，逻辑块 4 用直接地址，逻辑块 5 开始用一级间接地址。这里的逻辑块号表示它在文件中的顺序，不是它实际占用的磁盘块号。

最大文件长度：

1 2	`(5 + 2 × 256 + 256²) × 1 KB = 66053 KB`

注意：地址项的编号与文件逻辑块号只在直接地址部分恰好对应。addr[7] 指向二级索引的入口，并不直接存放文件逻辑块 7 的磁盘地址。

4. 例题：纯二级索引，每个地址占 3 B¶

题设：文件采用二级索引，索引块和数据块大小都是 1 KB，每个磁盘块地址占 3 B。求最大文件长度。

第一步，计算每个索引块的地址项数：

1	`q = ⌊1024 / 3⌋ = 341`

341 × 3 = 1023 B，还剩 1 B，放不下另一个 3 B 的地址。

第二步，二级索引的每个分支还能再指向 341 个数据块：

1 2	`数据块数 = 341 × 341 = 116281 最大文件长度 = 116281 × 1 KB = 116281 KB`

答案为 116281 KB。二级表示两层索引，所以计算 q²，不是 2q。题目没有给出额外的直接地址或一级间接入口，就不额外加上这些容量。

5. 多级索引怎么查找¶

还是纯二级索引，每个索引块有 341 个地址项。要读取文件逻辑块 500：

500 = 1 × 341 + 159

第一层索引项下标 = 500 // 341 = 1
第二层索引项下标 = 500 % 341 = 159

下标从 0 开始，因此查找过程是：

inode 中的二级索引入口
    ↓
第一层索引块的第 2 项（下标 1）
    ↓
对应第二层索引块的第 160 项（下标 159）
    ↓
目标数据块的磁盘地址，例如磁盘块 8000

第一层的下标 0 覆盖逻辑块 0～340，下标 1 覆盖 341～681。逻辑块 500 落在第二组，组内下标就是 159。

如果题目同时有直接地址和一级间接地址，先减去它们覆盖的数据块数，再拆分二级索引下标。例如上一题的逻辑块 517 是二级部分的第一个块：

1
2
3

二级部分内的相对块号 = 517 − 5 − 2 × 256 = 0
第一层下标 = 0 // 256 = 0
第二层下标 = 0 % 256 = 0

如果给的是文件内的 字节偏移 x，则先求：

1 2	`文件逻辑块号 = x // 数据块大小块内偏移 = x % 数据块大小`

通过索引找到磁盘数据块后，再用同一个块内偏移定位该块内的数据。

6. 为什么要设计多级索引¶

一个索引块的容量有限，一级索引只能指向 q 个数据块。增加一层后，可指向的数据块数就再乘 q，从而支持更大的文件。

混合索引还能兼顾不同大小的文件：

小文件直接使用 inode 中的直接地址，避免额外索引块。
文件变大时，按需分配一级、二级等索引块。
层数越多，在索引未缓存时，定位数据所需的磁盘访问也可能越多。

不存在所有文件系统通用的“最多几级”。 题目给了几级就按几级计算；实际文件系统也可能使用区段树等其他结构。

文件的多级索引用来定位 磁盘上的文件数据块；多级页表用来转换 进程的虚拟内存地址。两者都有逐层查表的思想，但管理的对象不同。

7. 思维导图¶

--- markmap: height: 600 initialExpandLevel: 2 autoFit: true colorFreezeLevel: 2 maxWidth: 280 spacingHorizontal: 80 spacingVertical: 12 nodeMinHeight: 24 paddingX: 10 --- # 索引文件结构 ## 两类块 - 数据块：文件内容 - 索引块：数据块或下一层索引块的地址 - 文件逻辑连续，磁盘块可以不连续 ## 容量 - q = ⌊索引块大小 / 地址项大小⌋ - 一个直接地址：1 个数据块 - 一个一级间接入口：q 个 - 一个二级间接入口：q² 个 - 一个三级间接入口：q³ 个 - 数据长度不含索引块开销 ## 例题 - 1 KB 块、4 B 地址：q = 256 - 5 个直接、2 个一级、1 个二级：66053 KB - 1 KB 块、3 B 地址、纯二级：116281 KB ## 查找 - 文件字节偏移 → 逻辑块号与块内偏移 - 混合索引先确定范围，再减去前面覆盖的块数 - 二级部分：商选第一层，余数选第二层 - 找到磁盘块后，块内偏移不变

相关笔记：位示图 · 分页与地址转换。

返回操作系统章节