目录检索算法,一个文件检索的生命流程🤔

一、 目录内检索算法

目录本质上也是一个文件，它的内容是一些目录项 (Directory Entry) 的列表。每个目录项通常包含两部分：文件名和指向该文件索引节点(i-node)的编号。目录检索算法，就是在这个列表中根据文件名查找对应目录项的方法。

主要有以下几种算法：

1. 线性查找 (Linear Search)

这是最简单、最直观的算法。

• 实现方式: 将目录中的所有目录项以线性列表的形式存储。当需要查找一个文件时，从列表的第一个目录项开始，逐个向后比较文件名，直到找到匹配的项或者搜索完整个列表。

• 优点:

  • 实现简单，易于管理。

  • 创建文件时，只需在列表末尾追加一个新的目录项即可。

• 缺点:

  • 效率低下。对于包含大量文件的目录，平均查找长度为 n/2（n为目录项数量），时间复杂度为 O(n)。当目录很大时，性能会急剧下降。

  • 删除文件后，可能会留下空洞，需要有机制来管理这些空洞（例如，标记为未使用，或移动后续项来填补），增加了管理的复杂性。

2. 哈希查找 (Hash Search)

为了提高查找效率，现代文件系统通常采用基于哈希表的方法。

• 实现方式: 目录文件本身被组织成一个哈希表。当查找一个文件时，系统会先对文件名进行哈希运算，得到一个哈希值，这个哈希值直接或间接地指向了目录项在哈希表中的位置。

• 优点:

  • 查找效率极高。在没有哈希冲突或冲突很少的情况下，查找时间复杂度接近 O(1)，几乎与目录中的文件数量无关。

• 缺点:

  • 哈希冲突处理: 必须有解决哈希冲突的机制（如链地址法、开放定址法），这增加了实现的复杂性。

  • 哈希表的大小需要预先确定或支持动态扩展，管理起来比线性列表复杂。

二、 访问文件的完整检索流程

现在我们来看一个更宏观的过程：当用户或程序需要访问一个文件（例如，通过路径 /home/user/report.txt）时，操作系统的完整检索流程是怎样的。这是一个自顶向下的、逐级解析的过程。

场景: 访问绝对路径 /home/user/report.txt

第一步：路径类型判断与起点定位

1. 操作系统首先解析路径字符串。发现它以 / 开头，这是一个绝对路径。

2. 因此，检索必须从文件系统的根目录 (/) 开始。

3. 操作系统知道根目录的i-node信息（通常其i-node编号是固定的，如2，并且这些信息存储在磁盘的**超级块(Superblock)**中），并将其读入内存。

(如果路径是相对路径，如 docs/file.c，则起点是当前进程的当前工作目录(Current Working Directory, CWD)，其i-node信息保存在进程的PCB中。)

第二步：循环解析路径分量 (Path Traversal)

这是一个循环往复的过程，直到路径的最后一个分量被处理。

循环1：解析 /home

1. 获取当前目录数据: 操作系统根据根目录的i-node，找到存放根目录内容的数据块（这些数据块里就是根目录下的所有目录项，如 (‘bin’, i-node号), (‘etc’, i-node号), (‘home’, i-node号) 等）。

2. 目录内检索: 在根目录的数据块中，使用上面讲的目录检索算法（如线性查找或哈希查找）搜索名为 "home" 的目录项。

3. 获取下一级i-node: 找到后，从该目录项中取出 "home" 目录对应的 i-node编号。

4. 加载i-node: 操作系统根据这个编号，从磁盘的i-node表中将 "home" 的i-node读入内存。

5. 权限检查: 检查当前用户是否有权限进入（执行）"home" 目录。如果有，则继续；如果没有，则返回“权限不足”错误。

循环2：解析 user

1. 获取当前目录数据: 现在，"home" 目录成了“当前目录”。操作系统根据刚刚加载的 "home" 的i-node，找到存放其内容的数据块（里面是home目录下的所有用户目录项）。

2. 目录内检索: 在 "home" 目录的数据块中，搜索名为 "user" 的目录项。

3. 获取下一级i-node: 找到后，取出 "user" 目录对应的 i-node编号。

4. 加载i-node: 将 "user" 的i-node读入内存。

5. 权限检查: 检查用户是否有权限进入 "user" 目录。

循环3：解析 report.txt

1. 获取当前目录数据: "user" 目录成了“当前目录”。根据 "user" 的i-node，找到其数据块。

2. 目录内检索: 在 "user" 目录的数据块中，搜索名为 "report.txt" 的目录项。

3. 获取最终i-node: 找到后，取出 "report.txt" 文件对应的 i-node编号。

4. 加载i-node: 将 "report.txt" 的i-node读入内存。

第三步：获得目标文件i-node并访问

• 路径字符串此时已解析完毕。最后一步得到的i-node，就是目标文件 "report.txt" 的i-node。

• 这个i-node包含了文件的所有元数据（大小、权限、时间戳等）以及最重要的——指向存放文件实际内容的数据块的指针列表。

• 操作系统现在可以根据这个最终的i-node和用户请求（读或写），进行后续的数据操作了。

补充：高速缓存的作用

为了避免每次路径解析都进行大量重复的磁盘I/O，操作系统会缓存：

• i-node缓存: 最近访问过的i-node会保存在内存中。

• 目录项缓存 (DNLC): 最近的“文件名 -> i-node编号”的解析结果也会被缓存。