是什么
-
定义: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 区) |
| 块 / 簇大小 | 1KB | 4KB | 4KB |
| 地址项指针大小 | 4B / 6B | 4B(单块容纳 项) | 4B(单块容纳 项) |
| 文件容量计算形式 | 连续预分配 直接索引累加 | 给出连乘累加表达式 | 计算累加临界阈值判定级数 |
| 核心隐藏题眼 | 起始块号 6B 冗余,优化成 4B+4B | 木桶效应:Inode 数量先枯竭 | 硬链接:同 Inode 共享数据块 |
2. 多级间接索引容量计算与级数判定流水线
设系统磁盘块大小为 ,地址指针项大小为 ,Inode 中直接地址项数为 :
-
求单块容纳的指针数 :
(若 ,则 项)
-
计算各层级独立覆盖容量:
-
直接地址项:
-
一级间接项:
-
二级间接项:
-
三级间接项:
-
-
判定文件大小 需启用哪几级间接项(临界阈值法):
-
若 :仅使用直接地址项;
-
若 :必须使用直接地址项与一级间接项;
-
若 :必须使用直接地址项、一级间接项和二级间接项;
-
超过二级上限则必须启用三级间接项。
-
3. 系统存储瓶颈:双重约束(木桶效应)模型
当系统创建大量固定大小的小文件时,决定最大文件数量的不是单一的磁盘数据容量,而是两个独立的硬件约束:
Plaintext
┌── 约束 A:数据区总块数 / 单文件占用块数
系统最大文件数 ──┤
└── 约束 B:Inode 区总块数 × 每块可存 Inode 数
★ 最终结果 = min(约束 A, 约束 B)
-
单文件占用块数:
-
系统 Inode 总数:
-
结论:每个文件必须且只能独占 1 个 Inode。若 Inode 耗尽,哪怕数据区还剩数百 GB,系统也无法新建任何文件。
4. 目录项与文件物理访问机制
-
UNIX 目录文件本质:
-
目录也是文件,其内部存储一系列紧凑的目录项,格式固定为:
-
目录项中绝对不保存文件大小、数据块号或修改时间(这些元数据全部存放在 Inode 中)。
-
-
硬链接(Hard Link)的判定依据:
-
不同的文件名如果对应相同的 Inode 号,说明它们是同一个物理文件的不同别名(硬链接)。
-
它们共享同一份数据块号和文件元数据,对其修改相互可见。
-
-
访问文件数据块的完整访盘流水线:
-
查目录:从目录文件中查得目标文件的 Inode 号;
-
读 Inode:从磁盘读取该 Inode 所在的物理块,调入内存(访盘 1 次);
-
读索引块(若为间接寻址):从 Inode 拿到间接索引块地址,读入索引块(一级需 1 次,二级需 2 次);
-
读目标数据:根据物理块号读入实际数据块(访盘 1 次)。
-
例题精析
例题 1:混合索引容量表达式、短板效应与寻道时延对比(2018 年真题第 14 题)
-
题目:
簇大小 4KB。每个 Inode 占 64B,含 11 个地址项:8 个直接项、1 个一级间接、1 个二级间接、1 个三级间接,地址项长 4B。
-
该系统支持的最大文件长度是多少?(给出计算表达式)
-
用 1M 个簇存 Inode,512M 个簇存文件数据。一个图像文件大小为 5600B,系统最多存放多少个该图像文件?
-
若文件 F1 大小为 6KB,文件 F2 大小为 40KB,获取 F1 和 F2 最后一个簇号的时间是否相同?为什么?
-
-
分析:
-
簇 4KB,地址项 4B,单块存 项。最大长度累加四级容量。
-
图像 5600B 跨 2 个簇。数据区可存 个。Inode 总数 个。短板在 Inode,取 64M。
-
F1(6KB)占 2 个簇,前 8 项直接给出,不访盘;F2(40KB)占 10 个簇,超出前 8 项直接项,第 9、10 簇在一级间接块中,必须多读 1 次磁盘索引块。
-
-
答案:
-
最大文件长度表达式为:
-
最多存放 (或 )个图像文件。
-
理由:
-
数据空间限制:每个图像文件占用 个簇,数据区最多支持 个文件;
-
Inode 空间限制:系统 Inode 总数 个,每个文件需占用 1 个 Inode;
-
系统瓶颈在于 Inode 数量不足,故最多存放 个。
-
-
-
不相同。
-
理由: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, 块 )。-
目录文件
stu中每个目录项的内容是什么? -
文件
doc占用的物理块号 是多少? -
若目录
course内容已在内存,打开course1并读入内存需读几个磁盘块?说明理由。 -
若文件
course2大小增长到 6MB,为了存取course2需要使用该文件 Inode 的哪几级间接地址项?说明理由。
-
-
分析:
-
stu下含course和doc,目录项仅存文件名和 Inode 号。 -
doc与course1拥有完全相同的 Inode 号(10),属于硬链接,共享相同的数据块号 。 -
course已在内存,查得course1为 10 号 Inode。需读磁盘取 10 号 Inode 块(1 次),再按直接地址读数据块 30(1 次),共 2 次。 -
10 个直接项覆盖 ;1 个一级间接覆盖 。两者合计 。,必须跨入二级间接项。
-
-
答案:
-
目录文件
stu包含两个目录项:-
("course", 2) -
("doc", 10)
-
-
的值为 30。
-
理由:
doc与course1的索引节点号均为 10,表明二者互为硬链接,指向同一个 Inode 和物理文件数据块,因此其物理块号相同。
-
-
需要读 2 个磁盘块。
-
理由:
-
course目录在内存,从中查得course1的 Inode 号为 10; -
第一次访盘:读取 Inode 10 所在的磁盘块调入内存;
-
第二次访盘:根据 Inode 10 中的直接地址项,读取文件数据所在的 30 号磁盘块。
-
-
-
需要使用:一级间接地址项 和 二级间接地址项。
-
理由:
-
10 个直接项可寻址:;
-
1 个一级间接项可寻址:;
-
直接项与一级间接项合计最大容量为 ;
-
因此 6MB 的文件已经超出了一级间接索引的寻址范围,必须使用二级间接地址项。
-
-
-
⚠️ 易错点
Warning
直接项数量 审题粗心:
2018 年是 8 个直接项,2022 年是 10 个直接项。严禁死记某一个固定常数,必须根据卷面题干第一段给出的数值计算。
硬链接本质理解不到位:
看到不同文件名对应相同 Inode 号时,不可认为是题目排版错误。硬链接正是通过在不同目录下设置指向同一 Inode 的目录项实现的。
间接项层级回答不完整:
问“需要使用哪几级间接地址项”时,若文件跨入二级,必须将一级间接项和二级间接项同时写出,因为索引展开是前驱依赖的,不能只写二级。
打开文件访盘次数漏算 Inode 块:
- 目录虽然已经在内存,但 Inode 节点本身常驻外存的 Inode 区。必须先访盘读取 Inode 块拿到数据块指针,才能再去访盘读取数据块。