目录

2026 大纲 四（二）1 目录的基本概念、四（二）2 树形目录、四（二）3 目录的操作三条，本篇一并承担。

名字翻译成位置的那张表

file-concept 里说文件抽象的第一条性质是按名存取， inode 里说目录项被瘦成了 (文件名, inode 号) 两个字段。 但一直没说：这些目录项本身放在哪儿？

答案很朴素——放在一个文件里。目录就是一种特殊的文件， 它的内容是一张目录项表。 这一句是本节的全部起点： 目录也有 inode、也占数据块、也要按物理结构分配， 只不过读出来的字节被系统解释成一条条 (名字, inode 号)。

由这一句立刻推出两件事。

其一，按路径找一个文件要读很多次盘。 每下一级都要做两件事： 先读这一级目录的 inode（否则不知道它的数据块在哪），再读它的数据块 （才查得到下一级的名字对应哪个 inode 号）。每级 2 次磁盘 I/O， 深度 $n$ 的路径就是 $2n$ 次。这个数字直接解释了两件事—— 为什么要有 open（把这笔开销缓存成一个整数）， 以及为什么要有当前工作目录（相对路径能省掉公共前缀的全部级数）。

其二，. 和 .. 不是什么特殊符号。 它们就是两条完全遵守 (名字, inode 号) 格式的普通目录项，只是名字取得特殊—— 也就是说，它们是两个硬链接。目录的链接计数怎么算、 怎么判断"已经走到根了"，全都由这一句推出来。

交互可视化

加载可视化中...

一、目录的本质

目录本质上是一种特殊的文件，内容是一张目录项的表，每个目录项记录一个文件（或子目录）的名称到其他信息的映射——像图书馆的分类目录卡，通过书名找到书架号和层号。在使用 inode 的文件系统中，目录项的格式非常简洁：目录项 = (文件名, inode 号)。

二、目录结构的演进

单级目录

整个系统只有一个目录，所有文件都在这个目录中。

根目录
├── file_a
├── file_b
├── file_c
└── file_d

两级目录

第一级是主文件目录（MFD），每个用户对应一个条目；第二级是用户文件目录（UFD），存放该用户的所有文件。

MFD
├── 用户A → UFD_A
│            ├── file_a
│            └── file_b
└── 用户B → UFD_B
             ├── file_a  ← 不同用户可以同名
             └── file_c

树形目录（多级目录）

将目录组织成一棵树，允许用户在目录下继续创建子目录。

/（根目录）
├── home/
│   ├── alice/
│   │   ├── docs/
│   │   │   └── report.txt
│   │   └── code/
│   │       └── main.c
│   └── bob/
│       └── data.csv
└── etc/
    └── config.ini

类型	说明	示例
绝对路径	从根目录开始的完整路径	/home/alice/docs/report.txt
相对路径	从当前目录开始的路径	docs/report.txt（当前在 /home/alice）

. 和 ..

每个目录被创建时，系统都会自动在里面放两个目录项：. 指向这个目录自己的 inode，.. 指向父目录的 inode。它们就是两条普通目录项、两个硬链接，由此推出三条计数结论：空目录的链接计数是 2（父目录里一条 + 自己的 .）、目录的链接计数 = 2 + 子目录个数（每个子目录里都有一条 .. 指着它）、根目录的 . 与 .. 指向同一个 inode（这正是判断"已经走到根"的实现方式）。.. 的存在还让相对路径可以往上走（../sibling/a.txt），否则路径解析就只能单向向下。

这也解释了"硬链接不能链接目录"的边界

一般禁止用户对目录建硬链接（防止成环导致遍历死循环），但 . 和 .. 本身就是指向目录的硬链接——它们是系统自己建的、结构完全受控的两条：. 指向自己、.. 指向唯一的父目录，构成的"环"长度固定且已知，遍历程序只要跳过这两个名字就不会死循环。用户随手建的目录硬链接则可能构成任意长度的环，无法这样处理。

路径解析

以 /home/alice/docs/report.txt 为例：从根目录 / 的 inode 开始 → 读根目录的数据块找到 home 的 inode → 读 home 的数据块找到 alice 的 inode → 读 alice 的数据块找到 docs 的 inode → 读 docs 的数据块找到 report.txt 的 inode → 读该文件的 inode 获取文件信息。每一级两次磁盘 I/O（读 inode + 读数据块）。使用相对路径可以省掉公共前缀那几级的检索，这正是「当前工作目录」存在的意义。

逐级数一遍磁盘 I/O：打开一条四层路径到底要读几次盘（想看清那 2n 次分别读的是什么时展开）

设系统采用 Unix 风格 inode + 数据块，根目录的 inode 已经常驻内存（系统启动时加载），其他 inode 都在磁盘上。要打开 /usr/local/bin/cc：

步骤	读什么	I/O 次数
1	根目录 inode 已在内存	0
2	读根目录的数据块（找 usr）	1
3	读 usr 的 inode	1
4	读 usr 的数据块（找 local）	1
5	读 local 的 inode	1
6	读 local 的数据块（找 bin）	1
7	读 bin 的 inode	1
8	读 bin 的数据块（找 cc）	1
9	读 cc 的 inode（用于后续 read/write）	1
合计		8 次

通用公式：根 inode 在内存时，解析深度 $n$ 的路径（含最终文件名）$=2n$ 次磁盘 I/O；根 inode 也要读时 $=2n+1$ 次。三处最容易数错：①「打开文件」只算到读目标文件的 inode 为止，不含读它的数据块；②设置了当前工作目录后，相对路径省掉公共前缀的全部级数；③一个目录的数据块若占多个磁盘块，可能要追加 I/O。

无环图目录

在树形目录基础上，允许多个目录项指向同一个文件或子目录，目录结构从「树」变成「有向无环图（DAG）」，这就是文件共享。

上图中 alice/report.txt 和 shared/report.txt 指向同一个文件（通过硬链接或软链接实现）。

三、目录操作

操作	说明
搜索	根据文件名在目录中查找对应的目录项
创建文件	在目录中增加一个目录项
删除文件	从目录中删除一个目录项（留下的空位怎么处理见下）
创建目录	创建子目录（初始自动包含 . 和 .. 两条目录项）
删除目录	目录为空时才能删除（另有"连同内容一起删"的做法，见下）
遍历目录	列出目录中的所有文件和子目录

删除非空目录：两种做法

做法	行为	代价
不删除非空目录	目录不空就拒绝。要删必须先把里面的文件删光；若含子目录还要递归下去	安全，但用户要多做几步
可删除非空目录	一条命令连同目录中的全部文件与子目录一起删掉	方便，但很危险——一条错误命令就可能删掉整棵子树

判据是"把风险交给用户还是交给系统"：前者强迫用户逐层确认，后者把整棵子树的删除压缩成一次不可撤销的操作。

删除一个目录项之后，那个空位怎么办

方式	做法	优点	缺点
标记删除（留空位）	在目录项里置一个"已删除"标志（如把文件名首字节改成特殊值），不移动任何其他目录项	删除是 $O(1)$；已打开该文件的进程不受影响；空位可被下次创建直接复用	目录只增不减，长期使用后充斥空洞，检索时仍要扫过这些空位
移动填补（紧凑）	把最后一个目录项搬到空位上，或把后面的目录项整体前移	目录始终紧凑，检索不浪费	每次删除都要移动数据；若目录项被别处按位置引用，移动会破坏引用

实际系统几乎都选标记删除，理由和空闲空间管理选延迟合并是同一条：删除是频繁操作，必须做成常数时间；目录里的空洞留给"下次创建文件时优先复用空位"慢慢消化即可。

四、目录的实现

目录项在磁盘块中有线性表与哈希表两种组织方式，判据是单目录下的文件数：几十到几百时线性表的常数更小、实现最简单、还天然支持按存入顺序遍历；上千以上哈希表才划算，代价是要处理冲突与扩容、且不再保持任何顺序。哈希实现必须处理两件事：

① 冲突——不同文件名可能被散列到同一位置，这是必然的（文件名的取值空间远大于目录表的长度）。经典处理办法是开放定址，三步规则是：该项为空即判定"系统中无此文件"；文件名相同即命中；名字不同则把散列值加上一个与目录表长度互质的常数再试。"互质"这个条件不能省——只有互质，反复加这个常数才能不重不漏地走遍整张表，否则会在几个位置之间打转。

② 扩容——目录表是定长的，装填因子升高后冲突急剧增加。扩容意味着表长变了 → 散列函数的模数变了 → 所有已有目录项的位置全部失效，必须整表重新散列。代价很高，所以通常在装填因子超过某个阈值（如 $0.75$）时才触发、且一次扩到两倍，把摊还代价压到 $O(1)$；扩容期间目录处于不一致状态，必须加锁或做成可中断恢复的。

哈希目录的一个副作用

散列把文件名打散了，所以目录里的项不再有任何有意义的顺序——既不是按名字序，也不是按创建先后。要按名字排序列出目录内容，只能把全部目录项读出来再排序。这与散列文件不支持顺序存取是同一个原因。

因此真实系统常用混合方案：目录项仍按线性表存放（保证遍历简单、删除可标记），另外在内存里建一个哈希索引加速按名查找。

五、一个文件系统最多能装几个文件

目录项的格式一旦定死，能创建的文件数就有了上限。判据是两个独立的天花板取小：

$$\text{文件数上限}=min(\underset{\text{编号能编几个}}{\underbrace{2^{8\times (\text{inode 号字节数})}}},\underset{\text{名字能起几种}}{\underbrace{(\text{字符集大小}{)}^{\text{文件名字节数}}}})$$

左边是编号的天花板：inode 号字段有多宽，就最多能区分多少个文件本体。 右边是名字的天花板：文件名字段能拼出多少种不同的字符串。 两个条件必须同时满足，所以取小。

举个例子：目录项 64 字节，其中 4 字节存 inode 号、60 字节存文件名， 文件名由小写英文字母构成。

• 编号天花板：$2^{8\times 4}=2^{32}$
• 名字天花板：${26}^{60}$，而 $26>2^4$，故 ${26}^{60}>2^{240}$

$2^{32}$ 远小于 $2^{240}$，所以上限是 ${\mathbf{2}}^{\mathbf{32}}$。

⚠️ 绝大多数题目里，卡住的都是编号那一侧——文件名字段稍微长一点， 它能拼出的组合数就是天文数字。但判据仍然是取小，不能直接答编号那一个， 因为题目完全可以把文件名字段设成 2 个字节来反过来考。

考点速记

1. 目录是一种特殊的文件，它的内容是一张目录项表；使用 inode 的文件系统里，目录项就是 (文件名, inode 号)。
2. 三级演进各解决什么：单级（全系统一个目录，不许重名）→ 两级（MFD + UFD，不同用户可同名，但层数写死）→ 树形（任意层级，现代标准）。
3. ⚠️两级目录的"访问控制" ≠ rwx 权限：判据是隔离靠"找不到"还是靠"找到了被拒绝"。两级目录把检索起点固定在用户自己的 UFD 上 ⇒ 命名空间隔离，只有"能不能看见"一种粒度。
4. 路径解析每级 2 次磁盘 I/O：读该级目录的 inode + 读它的数据块。根 inode 在内存时深度 $n$ 的路径 $=2n$ 次；根 inode 也要读则 $=2n+1$ 次。
5. 数 I/O 最容易错的三处：①「打开文件」只算到读目标文件的 inode 为止，不含读它的数据块；②设置了当前工作目录后，相对路径省掉公共前缀的全部级数——这正是当前工作目录的主要目的：加快文件检索速度（不是省空间、也不是加快读写）；③一个目录的数据块若占多个磁盘块，可能要追加 I/O。
6. . 和 .. 就是两个硬链接，不是特殊符号。由此推出三条计数结论：空目录的链接计数是 2（父目录里一条 + 自己的 .）；目录的链接计数 $=2+$ 子目录个数（每个子目录里的 ..）；根目录的 . 与 .. 指向同一个 inode——这正是判断"已经走到根"的实现方式。
7. 无环图目录的三个麻烦都来自"一个文件可以有多个父目录"：删除时不能直接回收空间、遍历要去重、必须防止成环。
8. 删目录项留下的空位，实际系统几乎都选标记删除而不是移动填补——删除被频繁执行，必须做成常数时间；代价是目录只增不减。
9. 目录的实现：线性表 $O(n)$，文件数几十到几百时常数很小、实现最简单；哈希表 $O(1)$ 均摊，单目录上千文件以上才划算，代价是要处理冲突与扩容、且不再保持任何顺序。
10. 文件数上限 $=min($ inode 号能编多少，文件名能起多少种 $)$。

这一节在真题里被考过的形式：

五道题，每道各考一个点，没有重复题型；共同点是都能由"目录是一个内容为目录项表的文件"直接推出。

• 问设置当前工作目录的主要目的（2010-31）。答加快文件的检索速度。⚠️ 另三项各错一处：不省外存（目录项该建还得建）、不省内存（反而多存一个当前目录指针）、不加快读写（读写速度由物理结构与缓冲决定，与路径长短无关）。判据是速记第四、五条——相对路径省掉的是公共前缀那几级的 $2\times$ I/O。
• 问删除文件时不可能执行的操作（2013-23）。答删除此文件所在的目录。⚠️ 另三项都可能做：删关联的目录项（必做）、删对应的 FCB（链接计数减到 0 时）、释放关联的内存缓冲区（有缓存时）。删一个文件不会动它所在的目录本身——目录里少了一条目录项，目录还在。
• 给目录项格式，问能创建的文件数上限（2020-31）。4 字节 inode 号 + 60 字节文件名（小写字母），答 ${\mathbf{2}}^{\mathbf{32}}$。⚠️ 用速记第十条取小：编号天花板 $2^{32}$、名字天花板 ${26}^{60}$，前者远小。错项 $2^{60}$、$2^{64}$ 都是拿字节数直接当指数、忘了乘 8 或者混了两个字段。
• 问磁盘逻辑格式化程序做的工作（2017-29，与操作系统引导共享，那边讲制盘四步的完整顺序）。答建立根目录 + 初始化保存空闲块信息的数据结构。⚠️ 分区在逻辑格式化之前、确定扇区校验码位数属于物理格式化——判据回到"这是文件系统的概念还是磁盘硬件的概念"。
• 一级目录 + 一次写入不可修改的介质，问该选哪种数据块组织方式、FCB 该集中存还是与数据连续存（2011-46，大题，与文件的物理结构共享）。第一问答连续分配（一次写入所以不需要扩展，外部碎片这个唯一缺点被场景消掉），FCB 中需要起始块号 + 文件长度两个字段。第二问答集中存储——快速找文件靠的是一次 I/O 能读进多少个 FCB，集中存时一个盘块能装很多个 FCB，与数据连续存则每读一个 FCB 就要跳一次盘。

复习优先级：必须拿满，且都是短判据。 速记第四、五条（路径解析的 I/O 计数） 和第六条（. .. 是硬链接，三条计数结论）是最容易直接设问的； 第十条那个取小公式练一遍就不会错。第八、九条（标记删除、线性表 vs 哈希） 至今没考过，读懂即可。

易错：认为设置当前工作目录是为了省内存或加快读写。它省的是路径解析的磁盘 I/O，即加快检索速度。

易错：认为删除文件会删掉它所在的目录。目录里少了一条目录项而已，目录还在。

易错：算文件数上限时只看 inode 号或只看文件名。判据是两个天花板取小。

易错：把文件名字节数直接当指数。60 字节小写字母是 ${26}^{60}$，不是 $2^{60}$。

易错：认为空目录的链接计数是 1。是 2——父目录里一条 + 它自己的 .。

易错：算目录的链接计数时漏掉子目录里的 ..。$=2+$ 子目录个数。

易错：把分区、确定扇区校验码位数算进逻辑格式化。那两样一个在分区阶段、一个属物理格式化。

易错：认为两级目录提供了访问权限控制。它提供的是命名空间隔离——别人的文件根本不在你的检索表里。

教材出处

• 汤小丹《计算机操作系统》印刷版 p238（7.3.4 目录操作）：删除目录时"如果所要删除的目录是空的……就可简单地将该目录项删除"；非空目录有两种处理——"不删除非空目录……必须先删除目录中的所有文件，使之先成为空目录，然后再予以删除。如果目录中还包含有子目录，还必须采取递归调用方式来将其删除"，以及"可删除非空目录……目录中的所有文件和子目录也同时被删除"，后者"比较方便，但却比较危险"。
• 同书 p240：Hash 法检索目录时冲突的处理规则——目录项为空则表示无此文件；文件名匹配则命中；"如果在目录表的相应目录项中的文件名与指定文件名并不匹配，则表示发生了'冲突'，此时须将其 Hash 值再加上一个常数（该常数应与目录的长度值互质），形成新的索引值，再返回到第一步重新开始查找"。
• 孙钟秀、费翔林《操作系统教程》（第 6 版）印刷版 p175：每个目录创建时都自动包含两个特殊目录项——"'.' 项指出目录自身的文件目录项入口，'..' 项指出其父目录的文件目录项入口"，并明确父子目录之间正是通过文件目录项链接实现的；"如何判断文件系统的根目录呢？通常采用 '.' 和 '..' 都指向同一个文件目录项的方法来实现"。

相关知识

文件的物理结构｜硬链接和软链接｜文件元数据与索引节点｜文件的保护｜文件的逻辑结构

真题练习

相关真题（7题）

2017Q292分2013Q232分2012Q468分2011Q467分2010Q312分2009Q302分2009Q312分

上一篇文件的物理结构下一篇硬链接和软链接

相关文章

• 文件的基本概念
• 文件元数据与索引节点
• 文件的操作
• 文件的保护
• 文件的逻辑结构
• 文件的物理结构
• 硬链接和软链接
• 文件系统的全局结构
• 外存空闲空间管理
• 虚拟文件系统
• 文件系统挂载