7.3　文件目录

本节概览：先建立「文件目录」的框架，再依次展开下列小节。

1. 文件控制块和索引结点
2. 简单的文件目录
3. 树形结构目录(Tree-Structured Directory)
4. 目录查询技术

文件控制块 FCB（File Control Block）是描述一个文件的目录项，用来对大量文件施以有效管理。通常含三类信息：基本信息、存取控制信息、使用信息。

1. 文件名：用于标识一个文件的符号名
2. 文件物理位置：指文件在外存上的存储位置
3. 文件逻辑结构：指示文件是流式文件还是记录式文件
4. 文件的物理结构：指示文件是顺序文件、链接式文件还是索引文件

存取控制信息类：包括文件主、核准用户及一般用户的存取权限。

使用信息类：包括建立日期和时间、上次修改日期和时间，以及当前使用信息（已打开该文件的进程数、是否被锁住、在内存中是否被修改但未写盘等）。不同 OS 的文件系统功能不同，可能只含上述信息的某些部分。

索引结点的引入：文件目录通常存放在磁盘上，文件很多时目录会占用大量盘块。查找时需先把目录盘块调入内存，再用文件名逐一比较；未找到还要继续调入下一盘块，开销很大。

把文件名与文件属性分开：目录项只放文件名和指向索引结点的指针，把物理地址等属性放进索引结点，可显著减少目录占用的盘块数，加快查找。

索引结点的引入：文件目录通常存放在磁盘上，文件很多时会占用大量盘块。查找目录时需将目录文件的盘块逐个调入内存，将文件名与目录项逐一比较，效率低。

引入索引结点后，目录项只保留文件名和指向索引结点的指针，大大减小目录占用空间，提高查找效率。

磁盘索引结点：存放在磁盘上，每个文件有唯一的磁盘索引结点，主要包括以下内容。

1. 文件主标识符，即拥有该文件的个用户或小组的标识符
2. 文件类型，包括正规文件、目录文件或特别文件
3. 文件存取权限，指各类用户对该文件的存取权限
4. 文件物理地址等

内存索引结点：文件被打开时将磁盘索引结点拷贝到内存，便于使用。内存索引结点中又增加了以下内容。

1. 索引结点编号，用于标识内存索引结点
2. 状态，指示 i 结点是否上锁或被修改
3. 访问计数，每当有进程访问时加 1，访问完减 1
4. 链接计数，指向该索引结点的目录项数

单级文件目录是最简单的目录结构：整个文件系统中只建立一张目录表，每个文件占一个目录项，含文件名、扩展名、长度、类型、物理地址及其它属性；并设一个状态位表明该目录项是否空闲。

1. 优点：简单
2. 缺点：查找速度慢
3. 不允许重名
4. 不便于实现文件共享

为克服单级目录的缺点，可为每个用户建立一个单独的用户文件目录 UFD（User File Directory），由该用户所有文件的 FCB 组成，结构与单级目录相似。

再在系统中建立一个主文件目录 MFD（Master File Directory）：每个用户目录文件在 MFD 中占一个目录项，含用户名和指向该用户目录文件的指针。

目录操作主要包括创建、删除、改变、移动和链接。

1. 创建目录
2. 删除目录（① 不删除非空目录；② 可删除非空目录）
3. 改变目录
4. 移动目录
5. 链接（Link）操作

路径名（path name）：在树形结构目录中，从根目录到任何数据文件都只有一条唯一的通路。从树根开始，把路径上全部目录文件名与数据文件名依次用「/」连接起来，即构成该数据文件唯一的路径名。

当前目录（Current Directory）：当文件系统含许多级时，每访问一个文件都要使用从根到叶的全路径名太繁琐。系统允许用户指定某目录为当前目录，访问时从当前目录开始即可。

现代 OS 中最通用且实用的目录是树形结构目录，可明显提高检索速度和文件系统性能。

主目录称为根目录，每个文件系统只有一个根；每个文件和每个目录都只能有一个父目录。数据文件作为树叶，其它目录作为树的结点（子目录）。

Hash 检索法：建立一张 Hash 索引文件目录项，按文件名计算出 Hash 值，定位到相应桶，再在桶内进行线性查找。

优点是检索速度快；冲突时需处理溢出（如拉链法或开放定址法），并要考虑目录的动态扩充。