考研笔记

目录实现

4.2.3 讲的是整个命名空间的形状，这一节讲的是单个目录内部：几千个目录项怎么摆，才能按文件名快速查到。

这两层必须分开看——命名空间是树形的，不妨碍每个目录内部用哈希表来查。

机制

线性列表

用一个存储文件名和数据块指针的线性表来表示目录。

创建新文件时，必须先检索整个目录表以确定没有同名文件存在，然后在目录表末尾增加一个目录项。

删除文件时，要在目录中找到该目录项并释放它所占的空间。释放的做法有三种：把该项标记为不再使用（如把文件名置为一个特殊值，或加一个”已使用—未使用”位）；把表中最后一个目录项复制到该位置；或把所有空目录项链成一条空闲链表。

线性列表的优点是实现简单，缺点是查找必须线性扫描。 检索一个文件平均要比对一半的目录项，这正是 4.1.2 那道”3200 个目录项平均访问 100 次磁盘”的题所刻画的代价。

若采用有序表并配合折半查找可以加快检索，但代价是插入和删除时要维护有序性，需要移动大量目录项。

哈希表

用文件名作为关键字，经哈希函数直接算出目录项的位置。

优点是查找非常迅速——不需要线性扫描，一次计算即可定位。

缺点有两条：其一是必须处理冲突，两个不同的文件名可能散列到同一位置；其二是哈希表长度固定，且哈希函数依赖于这个长度，目录规模增长到超出预期时，扩容需要重建整张表并重新散列所有目录项。

路径查找是逐级的

疑问点：Linux 中目录实现的具体形态

Linux 里”文件目录实现”有没有具体的例子。

以访问 /home/he/a.txt 为例。每一级都要完整地做一次”读目录的数据块 → 在其中比对文件名 → 取出 inode 号 → 读这个 inode”：

graph TD
    S["给定路径 /home/he/a.txt"] --> R["读根目录的 inode<br/><i>位置固定，系统已知</i>"]
    R --> R2["读根目录的数据块<br/>在其中查 'home' → 得 inode 号"]
    R2 --> H["读 home 的 inode → 读其数据块<br/>在其中查 'he' → 得 inode 号"]
    H --> HE["读 he 的 inode → 读其数据块<br/>在其中查 'a.txt' → 得 inode 号"]
    HE --> F["读 a.txt 的 inode<br/>检查权限 → 建立打开文件表项 → 返回 fd"]
    classDef start fill:#fef3c7,stroke:#d97706,color:#78350f
    classDef step fill:#dbeafe,stroke:#2563eb,color:#1e3a8a
    classDef done fill:#dcfce7,stroke:#16a34a,color:#14532d
    class S start
    class R,R2,H,HE step
    class F done

路径每深一级，就多一轮”读 inode + 读数据块”。 这就是当前目录之所以能显著提速的原因，也是”路径不宜过深”这一工程经验的来源。

在 Linux 中，一个目录项（ext 系列）大致包含这几个字段：

字段含义
inode文件本体的 inode 号
rec_len本目录项的长度
name_len文件名的长度
file_type普通文件 / 目录 / 符号链接等
name文件名（变长）

注意 rec_len 和 name_len 的存在：文件名是变长的，因此目录项也是变长记录，必须靠长度字段才能逐项切分——这正是 4.1.4 中”可变长记录靠长度字段定界”的实例。删除一个目录项时，ext 的做法是把前一项的 rec_len 加大，让它”吞掉”被删项所占的空间，这就是上面”标记为不再使用”的一种具体实现。

ext4 在目录较大时会启用 HTree，即在目录内部建立一棵以文件名哈希值为键的树形索引，把线性扫描变成对数级查找。这就是”目录实现”这一层的优化，与命名空间是树形的没有关系。

目录项缓存

由于路径查找极其频繁、且同一批路径会被反复解析，系统会把最近使用过的目录项和 inode 缓存在内存中（Linux 中称为 dentry cache 与 inode cache）。命中缓存时整级查找不需要任何磁盘 I/O。

这与快表 TLB、局部性原理是同一套思路——赌的都是”刚用过的东西马上还会用”。

边界

工具显示出来的目录不是磁盘上的格式

疑问点：目录在磁盘上的实际存储形式

用编辑器打开一个目录时看到的列表（如 Vim 的 Netrw Directory Listing，列出 bin@ --> usr/bin 等条目），是否就是目录在磁盘上的存储形式。

不是。那是工具渲染出来的结果，不是磁盘上目录文件的原始内容。

实际发生的是：工具调用系统提供的读目录接口（如 getdents）取回一组结构化的目录项，再对每一项调用 stat 取得类型、权限、链接目标等信息，最后把这些信息格式化成人能读的一行行文本。

磁盘上的目录文件是一串二进制的变长记录，形如”⟨inode 号 | 记录长度 | 名字长度 | 类型 | 文件名字节⟩“紧挨着排列，中间没有换行、没有对齐、没有箭头。那些 /、@、--> 全是工具加上去的装饰——/ 表示这是目录，@ 表示这是符号链接，--> 后面是工具替你读出来的链接目标。

所以”感觉好粗糙”这个印象来自渲染层而不是存储层。 底层格式恰恰相反：它非常紧凑（变长、无冗余），只是完全不适合人直接阅读。这也正是目录文件不允许用户程序直接用普通写操作修改的原因之一——格式是文件系统的内部约定，交给应用自由解释既不安全也不通用。

顺带一提，那份列表里的 bin@ --> usr/bin、lib@ --> usr/lib 是符号链接，它们本身就是文件，内容是一个路径字符串，详见 4.2.5。

目录实现与目录结构是两层

这一条与 4.2.3 的那条辨析互为正反面，是本节的核心考点：

目录结构回答”整个命名空间是单级、两级、树形还是无环图”；目录实现回答”某一个目录内部，目录项用线性表还是哈希表组织”。

两者可以任意组合：一个树形目录系统里，每个目录内部既可以是线性表，也可以是哈希表。看到”树形目录”就想到 B+ 树，正是把这两层混在了一起。

检索目录的开销与文件的物理结构无关

计算题里常把两者叠在一起，必须分开计账：

检索目录的开销取决于目录的组织方式（线性表还是哈希表）和目录文件本身有多少个盘块。取数据块的开销取决于文件的物理结构（连续、链接还是索引）。

这是两笔独立的账，任何一道”访问磁盘几次”的题都要问清楚它问的是哪一笔，或者两笔都要。

对照速查

实现方式优点缺点
线性列表实现简单查找需线性扫描（平均比对一半）
有序表 + 折半查找变快插入删除要维护有序，需移动目录项
哈希表查找迅速需处理冲突；表长固定，扩容要重建
删除目录项的三种做法
①标记为不再使用（置特殊值或加使用位）
②把最后一个目录项复制到该位置
③把空目录项链成空闲链表
Linux 目录项字段用途
inode文件本体的 inode 号
rec_len本项长度（变长记录靠它定界）
name_len文件名长度
file_type文件类型
name文件名
层次回答什么取值
目录结构（4.2.3）命名空间的形状单级 / 两级 / 树形 / 无环图 / 通用图
目录实现（本节）单个目录内部怎么查线性表 / 哈希表 / B+ 树

考点

  • 线性列表创建文件前必须先查重名；删除的三种处理方式
  • 哈希表的两个缺点：冲突、表长固定难扩容
  • 路径每深一级多一轮”读 inode + 读数据块”
  • 目录项是变长记录，靠 rec_len 定界
  • 目录结构与目录实现是两层，可任意组合
  • 检索目录的开销与文件物理结构是两笔独立的账
  • 工具显示的目录列表是渲染结果，不是磁盘格式

链接

反向链接