是什么

  • 定义:UNIX 混合索引结构(Inode-based Hybrid Indexing)是一种将直接寻址与多级间接寻址(一级、二级、三级间接)结合的文件物理结构,配合分离式目录项(文件名 + Inode 号),兼顾了小型文件的极速读写与大型文件的超大容量扩展。

  • 大白话:

    • 小文件(直接项):像把电话号码直接存在手机通讯录的置顶位,一按就拨通(0 次额外访盘);

    • 大文件(多级间接):像套娃索引,一级间接是一张清单写满数据块号;二级间接是一张清单记录着 1024 张一级清单的地址;三级间接再套一层。文件有多大,套娃就展开到哪一层。

核心内容

1. 为什么各大真题“算出来不一样”?(全维度变体对照)

历年 408 大题在考查索引与文件结构时,常常因为题设条件的细微差异导致计算模式截然不同:

考查维度 / 题目年份2012 年(混合直接索引)2018 年真题(14 题)2022 年真题(15 题)
直接项数量 84 个直接项(非标准结构)8 个 直接项10 个 直接项(UNIX 标准)
单个 Inode 大小512B(存放在 FCB 内部)64B(独立 Inode 区)256B(独立 Inode 区)
块 / 簇大小1KB4KB4KB
地址项指针大小4B / 6B4B(单块容纳 项)4B(单块容纳 项)
文件容量计算形式连续预分配 直接索引累加给出连乘累加表达式计算累加临界阈值判定级数
核心隐藏题眼起始块号 6B 冗余,优化成 4B+4B木桶效应:Inode 数量先枯竭硬链接:同 Inode 共享数据块

2. 多级间接索引容量计算与级数判定流水线

设系统磁盘块大小为 ,地址指针项大小为 ,Inode 中直接地址项数为 :

  1. 求单块容纳的指针数 :

    (若 ,则 项)

  2. 计算各层级独立覆盖容量:

    • 直接地址项:

    • 一级间接项:

    • 二级间接项:

    • 三级间接项:

  3. 判定文件大小 需启用哪几级间接项(临界阈值法):

    • 若 :仅使用直接地址项;

    • 若 :必须使用直接地址项与一级间接项;

    • 若 :必须使用直接地址项、一级间接项和二级间接项;

    • 超过二级上限则必须启用三级间接项。

3. 系统存储瓶颈:双重约束(木桶效应)模型

当系统创建大量固定大小的小文件时,决定最大文件数量的不是单一的磁盘数据容量,而是两个独立的硬件约束:

Plaintext

               ┌── 约束 A:数据区总块数 / 单文件占用块数
系统最大文件数 ──┤
               └── 约束 B:Inode 区总块数 × 每块可存 Inode 数
               ★ 最终结果 = min(约束 A, 约束 B)
  • 单文件占用块数:

  • 系统 Inode 总数:

  • 结论:每个文件必须且只能独占 1 个 Inode。若 Inode 耗尽,哪怕数据区还剩数百 GB,系统也无法新建任何文件。

4. 目录项与文件物理访问机制

  • UNIX 目录文件本质:

    • 目录也是文件,其内部存储一系列紧凑的目录项,格式固定为:

    • 目录项中绝对不保存文件大小、数据块号或修改时间(这些元数据全部存放在 Inode 中)。

  • 硬链接(Hard Link)的判定依据:

    • 不同的文件名如果对应相同的 Inode 号,说明它们是同一个物理文件的不同别名(硬链接)。

    • 它们共享同一份数据块号和文件元数据,对其修改相互可见。

  • 访问文件数据块的完整访盘流水线:

    1. 查目录:从目录文件中查得目标文件的 Inode 号;

    2. 读 Inode:从磁盘读取该 Inode 所在的物理块,调入内存(访盘 1 次);

    3. 读索引块(若为间接寻址):从 Inode 拿到间接索引块地址,读入索引块(一级需 1 次,二级需 2 次);

    4. 读目标数据:根据物理块号读入实际数据块(访盘 1 次)。

例题精析

例题 1:混合索引容量表达式、短板效应与寻道时延对比(2018 年真题第 14 题)

  • 题目:

    簇大小 4KB。每个 Inode 占 64B,含 11 个地址项:8 个直接项、1 个一级间接、1 个二级间接、1 个三级间接,地址项长 4B。

    1. 该系统支持的最大文件长度是多少?(给出计算表达式)

    2. 用 1M 个簇存 Inode,512M 个簇存文件数据。一个图像文件大小为 5600B,系统最多存放多少个该图像文件?

    3. 若文件 F1 大小为 6KB,文件 F2 大小为 40KB,获取 F1 和 F2 最后一个簇号的时间是否相同?为什么?

  • 分析:

    • 簇 4KB,地址项 4B,单块存 项。最大长度累加四级容量。

    • 图像 5600B 跨 2 个簇。数据区可存 个。Inode 总数 个。短板在 Inode,取 64M。

    • F1(6KB)占 2 个簇,前 8 项直接给出,不访盘;F2(40KB)占 10 个簇,超出前 8 项直接项,第 9、10 簇在一级间接块中,必须多读 1 次磁盘索引块。

  • 答案:

    1. 最大文件长度表达式为:

    2. 最多存放 (或 )个图像文件。

      • 理由:

        • 数据空间限制:每个图像文件占用 个簇,数据区最多支持 个文件;

        • Inode 空间限制:系统 Inode 总数 个,每个文件需占用 1 个 Inode;

        • 系统瓶颈在于 Inode 数量不足,故最多存放 个。

    3. 不相同。

      • 理由:F1 占 2 个簇,最后一个簇号直接记录在 Inode 的直接地址项中,读入 Inode 后即可直接获取;F2 占 10 个簇,超过了 8 个直接地址项的范围,最后一个簇号存放在一级间接索引块中,必须额外访盘读取一级间接块后才能获取,因此获取 F2 最后一个簇号的时间更长。

例题 2:树状目录项、硬链接识别与间接寻址层级判定(2022 年真题第 15 题)

  • 题目:

    磁盘块 4KB,目录项由【文件名】和【索引节点号】构成。每个 Inode 占 256B,含 10 个直接项,一级、二级、三级间接项各 1 个,地址项 4B。

    目录结构:子目录 stu 包含子目录 course 和文件 doc;course 包含文件 course1 和 course2。

    已知 Inode 与物理块:stu (Inode 1, 块 10);course (Inode 2, 块 20);course1 (Inode 10, 块 30);course2 (Inode 100, 块 40);doc (Inode 10, 块 )。

    1. 目录文件 stu 中每个目录项的内容是什么?

    2. 文件 doc 占用的物理块号 是多少?

    3. 若目录 course 内容已在内存,打开 course1 并读入内存需读几个磁盘块?说明理由。

    4. 若文件 course2 大小增长到 6MB,为了存取 course2 需要使用该文件 Inode 的哪几级间接地址项?说明理由。

  • 分析:

    • stu 下含 course 和 doc,目录项仅存文件名和 Inode 号。

    • doc 与 course1 拥有完全相同的 Inode 号(10),属于硬链接,共享相同的数据块号 。

    • course 已在内存,查得 course1 为 10 号 Inode。需读磁盘取 10 号 Inode 块(1 次),再按直接地址读数据块 30(1 次),共 2 次。

    • 10 个直接项覆盖 ;1 个一级间接覆盖 。两者合计 。,必须跨入二级间接项。

  • 答案:

    1. 目录文件 stu 包含两个目录项:

      • ("course", 2)

      • ("doc", 10)

    2. 的值为 30。

      • 理由:doc 与 course1 的索引节点号均为 10,表明二者互为硬链接,指向同一个 Inode 和物理文件数据块,因此其物理块号相同。

    3. 需要读 2 个磁盘块。

      • 理由:

        • course 目录在内存,从中查得 course1 的 Inode 号为 10;

        • 第一次访盘:读取 Inode 10 所在的磁盘块调入内存;

        • 第二次访盘:根据 Inode 10 中的直接地址项,读取文件数据所在的 30 号磁盘块。

    4. 需要使用:一级间接地址项 和 二级间接地址项。

      • 理由:

        • 10 个直接项可寻址:;

        • 1 个一级间接项可寻址:;

        • 直接项与一级间接项合计最大容量为 ;

        • 因此 6MB 的文件已经超出了一级间接索引的寻址范围,必须使用二级间接地址项。

⚠️ 易错点

Warning

  • 直接项数量 审题粗心:

    • 2018 年是 8 个直接项,2022 年是 10 个直接项。严禁死记某一个固定常数,必须根据卷面题干第一段给出的数值计算。

  • 硬链接本质理解不到位:

    • 看到不同文件名对应相同 Inode 号时,不可认为是题目排版错误。硬链接正是通过在不同目录下设置指向同一 Inode 的目录项实现的。

  • 间接项层级回答不完整:

    • 问“需要使用哪几级间接地址项”时,若文件跨入二级,必须将一级间接项和二级间接项同时写出,因为索引展开是前驱依赖的,不能只写二级。

  • 打开文件访盘次数漏算 Inode 块:

    • 目录虽然已经在内存,但 Inode 节点本身常驻外存的 Inode 区。必须先访盘读取 Inode 块拿到数据块指针,才能再去访盘读取数据块。