面试题：文件系统中目录层次结构动态调整的实现机制

Question

在操作系统的文件系统里，当需要对目录层次结构进行动态调整（比如添加新目录、删除目录等操作）时，通常会涉及到哪些关键的数据结构和操作步骤？请简要阐述。

Answer 1

关键数据结构

1. 目录项（Directory Entry）：
   • 用于表示文件或子目录的基本信息，通常包含文件名、文件类型（是文件还是目录）、文件的物理地址（对于文件）或指向子目录的指针（对于目录）等。例如在 Unix - like 系统中，每个目录项是一个 dirent 结构体，其中包含文件名和 inode 号等信息。
2. 索引节点（Inode）：
   • 存储文件的元数据，如文件的所有者、权限、大小、创建时间、修改时间等，以及指向文件数据块的指针数组。对于目录来说，inode 包含指向目录项列表的指针。在 Linux 系统中，inode 是文件系统中一个重要的数据结构，每个文件和目录都有唯一的 inode。
3. 目录树（Directory Tree）：
   • 以树状结构组织目录和文件，根目录是树的根节点，每个目录可以包含多个子目录（子节点）和文件（叶节点）。这种结构方便快速定位文件和目录，通过树的遍历算法（如深度优先遍历、广度优先遍历）可以访问整个目录层次结构。

操作步骤

1. 添加新目录：
   • 创建目录项：在父目录的目录项列表中创建一个新的目录项，记录新目录的名称和类型（目录类型），并分配一个新的 inode 号。
   • 分配 inode：为新目录分配一个 inode，初始化其元数据，如设置所有者、权限等，同时初始化指向目录项列表的指针（此时为空列表）。
   • 更新目录树：将新目录作为父目录的子节点添加到目录树结构中，完成目录的添加操作。
2. 删除目录：
   • 检查目录是否为空：首先遍历目录树检查要删除的目录是否为空。如果目录不为空，通常不能直接删除（某些操作系统有强制删除非空目录的选项，但这涉及递归删除子目录和文件）。
   • 删除目录项：在父目录的目录项列表中删除该目录对应的目录项。
   • 释放 inode：回收该目录的 inode 以及其占用的磁盘空间，同时从目录树结构中移除该目录节点，完成删除操作。如果是删除非空目录，需要递归地先删除子目录和文件，再进行上述操作。