【软考 文件的索引结构】直接、一级、n级

文件的索引结构及典型题型解析

一、文件索引结构核心原理

文件索引结构通过“索引表”记录数据块的磁盘地址，核心层级包括：

• 直接索引 ：索引项直接指向数据块（最快访问）。
• 一级间接索引 ：索引项指向“索引块”，索引块中存储多个数据块的地址。
• 二级间接索引 ：索引项指向“一级索引块”，一级索引块再指向多个“二级索引块”，最终由二级索引块指向数据块。
• （扩展）三级间接索引：在二级基础上再增加一层索引块嵌套。

二、基础题型：计算最大文件大小

题目背景

某文件系统采用混合索引结构，包含：8个直接索引项、1个一级间接索引项、1个二级间接索引项。已知磁盘块大小为8KB，每个地址指针占4字节。求该结构支持的最大文件大小。

解题步骤

1.** 计算单个索引块可存储的指针数** 磁盘块大小 = 8KB = 8×1024B = 8192B，每个指针4B，因此： 单个索引块的指针数 = 8192B / 4B = 2048 个。

1. 各层级索引的容量计算
   • 直接索引：8个直接项 → 8×8KB = 64KB。
   • 一级间接索引：1个索引块 → 2048×8KB = 16384KB。
   • 二级间接索引：1个一级索引块 → 2048个二级索引块 → 2048×2048×8KB = 33554432KB。
2. 总最大文件大小 总和 = 64KB + 16384KB + 33554432KB = 33570880KB（约32.02GB）。

三、典型题型案例

案例1：多级索引的容量计算

题目：某文件系统含10个直接索引、1个一级间接、1个二级间接、1个三级间接。磁盘块大小4KB，指针占4字节。求最大文件大小。

解答：

1. 单个索引块指针数 = 4×1024B / 4B = 1024 个。
2. 各层级容量：
   • 直接索引：10×4KB = 40KB。
   • 一级间接：1024×4KB = 4096KB。
   • 二级间接：1024×1024×4KB = 4194304KB。
   • 三级间接：1024×1024×1024×4KB = 4294967296KB。
3. 总和 = 40 + 4096 + 4194304 + 4294967296 = 4299165736KB（约4TB）。

案例2：索引结构的空间利用率

题目：磁盘块大小1KB，指针占2字节。某文件用5个直接块 + 1个一级间接块存储。求其磁盘空间利用率（数据区/总占用空间）。

解答：

1. 单个索引块指针数 = 1×1024B / 2B = 512 个。
2. 数据区大小：5个直接块 + 512个间接块 → (5+512)×1KB = 517KB。
3. 总占用空间：数据区 + 1个一级索引块 → 517KB + 1KB = 518KB。
4. 利用率 = 517/518 ≈ 99.8%。

案例3：逻辑块号对应的索引层级

题目：索引结构含5个直接块、1个一级间接、1个二级间接。磁盘块8KB，指针4字节。若文件逻辑块号为2050，该块在第几级索引中？

解答：

1. 单个索引块指针数 = 8×1024/4 = 2048 个。
2. 各层级覆盖的逻辑块号范围：
   • 直接索引：0~4（共5块）。
   • 一级间接：5 ~ (5+2048-1) = 5~2052（共2048块）。
   • 二级间接：2053及以后。
3. 逻辑块号2050属于5~2052，因此在一级间接索引中。

四、总结

解决索引结构问题的核心步骤：

1. 计算单个索引块的指针数（磁盘块大小 / 指针大小）。
2. 明确各层级索引的“嵌套关系”（直接→一级→二级…）。
3. 按层级计算容量或覆盖范围，再结合题目要求汇总。

通过以上案例可快速掌握此类题型的解题逻辑。