考研笔记

目录结构

这一节讲整个文件命名空间长成什么样。四种结构不是四个并列的选项，而是一条被 4.2.1 那四条要求逐步逼出来的演进链：

单级目录（不能重名）→ 两级目录（能重名了，但共享和分类不行）→ 树形目录（层次清楚了，但共享仍不自然）→ 无环图目录（能共享了，但删除变复杂）

每一级都是在解决上一级留下的问题。按这条链读，四种结构的优缺点全部是推出来的，不需要背。

机制

单级目录结构

整个文件系统中只建立一张目录表，每个文件占一个目录项。

致命缺陷是不允许文件重名。 因为目录表是唯一的一张，两个文件同名就无法区分。在多用户系统里这完全不可接受——用户甲不能因为用户乙先建了 report.txt 就被迫改名。

此外，查找必须线性扫过整张表，文件多时极慢。

结论：单级目录只能用于单用户环境。

两级目录结构

把目录分成两层：主文件目录（MFD）记录用户名及其用户文件目录的存放位置；用户文件目录（UFD）由该用户的文件 FCB 组成。

这个结构解决了重名问题：不同用户的文件在各自的 UFD 里，两个用户可以各有一个 report.txt 而互不冲突，因为查找时先按用户名定位到 UFD，再在 UFD 内查文件名。“允许文件重名”这条要求至此才被满足。

但两级目录仍有两个问题：其一，用户之间被完全隔离，缺乏灵活性，不便于共享文件；其二，一个用户的文件全部平摊在自己的 UFD 里，无法再分类——文档、代码、图片混在一起。

多级目录结构（树形目录）

允许目录中再包含目录，于是整个命名空间成为一棵树，根目录是树根，数据文件是树叶。

访问一个文件要给出路径名，路径名是一条从根目录出发到该文件的通路上所有目录名与文件名的拼接：

绝对路径从根目录出发，如 /home/he/a.txt。相对路径从当前目录出发，如 ../note.md。

引入”当前目录”（工作目录）的意义是纯粹的性能优化：若每次都用绝对路径，访问同一目录下的一批文件时，每次都要从根目录重新逐级检索一遍。设定当前目录后，只需从当前目录出发查一级，大幅减少了磁盘访问次数。

树形目录的优点是层次清晰、便于文件分类与管理和保护。 它的问题是共享仍不自然——树的定义要求每个节点只有一个父节点，而共享意味着一个文件要能从两条不同的路径到达。

无环图目录结构

在树形目录的基础上增加一些指向同一节点的有向边，使整个目录成为一个有向无环图。

graph TD
    R["/"] --> A["用户 A"]
    R --> B["用户 B"]
    A --> A1["报告"]
    A --> S["共享数据文件<br/>count = 2"]
    B --> B1["代码"]
    B --> S
    classDef root fill:#fef3c7,stroke:#d97706,color:#78350f
    classDef usr fill:#dbeafe,stroke:#2563eb,color:#1e3a8a
    classDef sh fill:#dcfce7,stroke:#16a34a,color:#14532d
    class R root
    class A,B,A1,B1 usr
    class S sh

上图中那个被两条边指向的节点就是共享文件——它在树形目录中是不可能存在的，因为树不允许一个节点有两个父节点。

共享的关键是”系统只保留该文件的一份副本”。 若用复制的办法让两个用户各存一份，一方修改后另一方看到的就是旧数据，这不叫共享。真正的共享必须是同一个文件本体、多条访问路径。

代价出现在删除时。 若用户 A 删掉了他那条路径上的目录项，文件本体不能立刻回收——用户 B 还在用。因此系统要设置共享计数器：每增加一条共享边计数加一，每删除一个目录项计数减一，直到计数为 0 才真正删除文件本体。具体实现见 4.2.5。

通用图目录结构

若允许目录之间形成环，就得到通用图目录。 它的共享能力最强，但代价很大：遍历目录时可能陷入无限循环；回收不可达对象时简单的引用计数会失效（环上的对象引用计数永远不为 0），必须引入垃圾回收机制。

408 掌握到这个程度即可：无环图目录支持共享但必须避免环；通用图目录表达能力最强但维护复杂。

边界

树形目录不是 B+ 树

疑问点：树形目录与 B+ 树的关系

树形目录是否就是数据结构中的 B+ 树。

两者是两个不同层次上的”树”，没有关系。

“树形目录”描述的是用户命名空间的层次形态——/ 下面有 home，home 下面有 he，he 下面有若干文件。它的树形来自”目录可以嵌套目录”这一语义，与查找效率无关，节点的分支数完全由用户建了多少个子目录决定。

B+ 树（或哈希树、HTree）描述的是”某一个目录内部，几千个目录项如何组织才能快速按文件名查找”——它属于 4.2.4 目录实现的范畴，是一种索引结构。

一句话分清：树形目录是”命名空间的形状”，B+ 树是”单个目录内部的查找加速结构”。 现代文件系统（如 ext4 的 HTree、Btrfs）确实在大目录内部使用了 B 树类结构，但那是在树形目录的每一个节点内部，而不是取代树形目录本身。

这条辨析的考法是：题目问”单级/两级/树形/无环图/通用图”，答的是命名空间结构；题目问”线性表/哈希表/B+ 树”，答的是目录实现。

树形目录为什么”不便于共享”

这句教材结论容易被记成”树形目录不能共享”，但准确的说法是：树的结构本身无法表达共享。

树的定义要求每个节点有且只有一个父节点。 而共享的本质是”同一个文件能从两条不同的路径到达”，这必然意味着两个父节点。所以要支持共享，必须突破树的定义——这正是无环图目录所做的事。

绝对路径与相对路径的开销差别

两者最终都要逐级检索，差别只在于”从哪里开始”。

访问 /home/he/doc/a.txt：绝对路径要依次检索 /、home、he、doc 四级目录；若当前目录已经是 /home/he/doc，相对路径 a.txt 只需检索一级。

当同一目录下要连续访问多个文件时，这个差别会被放大若干倍——这就是”当前目录”这个概念存在的唯一理由。

两级目录的”MFD/UFD”在计算题中的处理

4.1.2 那道”3200 个目录项平均访问几次”的题里，“二级目录”四个字没有参与计算。原因是：

题目只给了一个目录项总数，没有分别给出 MFD 和 UFD 的规模，此时按”当前要查的那个目录文件”计算即可。只有当题目分别给出两级各自的目录项数时，才需要把两级的检索成本分别算出再相加。

对照速查

结构形态解决了什么遗留问题
单级目录全系统一张表—不允许重名、查找慢、不适合多用户
两级目录MFD → UFD允许重名、用户隔离不便共享、无法再分类
树形目录目录可嵌套目录层次清晰、便于分类与保护不便共享（树不允许两个父节点）
无环图目录树 + 共享边，无环支持共享（一份副本，多条路径）删除需共享计数器
通用图目录允许成环共享能力最强遍历可能死循环、引用计数失效
绝对路径相对路径
起点根目录 /当前目录
开销每次从根逐级检索只查当前目录以下的层级
意义—减少磁盘访问次数（当前目录存在的唯一理由）
问的是答的是
单级 / 两级 / 树形 / 无环图 / 通用图命名空间结构（本节）
线性表 / 哈希表 / B+ 树目录实现（4.2.4）

考点

  • 四种结构的演进链：不能重名 → 能重名不能共享 → 层次清楚仍难共享 → 能共享但删除复杂
  • 单级目录的致命伤是不允许重名；两级目录靠 MFD/UFD 解决
  • 两级目录的两个遗留问题：不便共享、无法分类
  • 树形目录不便于共享的根本原因是”树不允许两个父节点”
  • 无环图目录必须有共享计数器，计数为 0 才真正删除
  • 通用图目录的两个风险：遍历死循环、引用计数失效
  • 当前目录的意义是减少检索层级
  • 树形目录 ≠ B+ 树：命名空间形状 vs 单目录内部索引

链接

反向链接