文件目录
目录
参考资料：
文件目录也是一种数据结理构，用于标识系统中的文件及其物理地址，供检索时使用。
对目录管理的包括：实现“按名存取”、提高目录的检索速度、实现文件共享、允许文件重名等。
1 文件控制块和索引结点
为了能对一个文件进行正确的存取，必须为文件设置用于描述和控制文件的数据结构，称之为“文件控制块”。
文件管理程序可借助于文件控制块中的信息对文件施以各种操作，文件与文件控制块一一对应，文件控制块的有序集合称为文件目录，即一个文件控制块就是一个文件目录项。通常，一个文件目录也被看做是一个文件，称为目录文件。
目录也是一种数据结构，文件控制块
1.1 文件控制块 FCB（File Control Block）中的内容
基本信息包括：文件名，文件物理位置，文件逻辑结构，文件的物理结构，指示文件是顺序文件，还是链接式文件或索引文件。
- 文件逻辑结构：指文件是流式文件还是记录式文件及记录数，文件是定长记录还是变长记录等。
- 文件的物理结构，指示文件是顺序文件，还是链接式文件或索引文件。
存取控制信息：包括文件主的存取权限、核准用户的存取权限以及一般用户的存取权限。
**使用信息：**使用信息类包括文件的建立日期和时间、文件上一次修改的日期和时间，以及当前使用信息。
类似 PCB
1.2 为什么要引入索引结点？
在检索目录文件的过程中，只用到了文件名，仅当找到一个目录项时，才需从该目录项中读出该文件的物理地址。而其它一些对该文件进行描述的信息在检索目录时一概不用。显然，这些信息在检索目录时不需调入内存。
为此，便采用了把文件名与文件描述信息分开的办法，亦即，使文件描述信息单独形成一个称为索引结点的数据结构，简称为 i 结点。
在文件目录中的每个目录项仅由文件名和指向该文件所对应的 i 结点的指针所构成，有利于减少磁盘 I/O，节省系统开销。
磁盘索引结点：存放在磁盘上的索引结点。每个文件有唯一的一个磁盘索引结点，它主要包括：文件主标识符，文件类型，文件存取权限，文件物理地址，文件长度，文件连接计数，文件存取时间等。
内存索引结点：存放在内存中的索引结点。当文件被打开时，要将磁盘索引结点拷贝到内存的索引结点中，便于以后使用。在内存索引结点中又增加了：索引结点编号，锁和修改状态，访问计数，所属文件系统的逻辑设备号，链接指针等。
2 简单的目录文件
2.1 单级文件目录
单级文件目录是最简单的文件目录。在整个文件系统中只建立一张目录表，每个文件占一个目录项，目录项中含文件名、文件扩展名、文件长度、文件类型、文件物理地址以及其它文件属性。此外，为表明每个目录项是否空闲，又设置了一个状态位。单级文件目录如下图所示。
单级文件目录的优点是简单，但它只能实现目录管理中最基本的功能：按名存取。但是它查找速度慢，不允许重名，也不便于实现文件共享。
2.2 两级文件目录
为了克服单级文件目录所存在的缺点，可以为每一个用户再建立一个单独的用户文件目录 UFD(User File Directory)。这些文件目录具有相似的结构，它由用户所有文件的文件控制块组成。
此外，在系统中再建立一个主文件目录 MFD(Master File Directory)；在主文件目录中，每个用户目录文件都占有一个目录项，其目录项中包括用户名和指向该用户目录文件的指针。如下图所示，图中的主目录中示出了三个用户名，即 Wang、Zhang 和 Gao。
主目录+用户目录
优点：相对单级目录而言，两级目录，可以提高检索目录的速度，在不同的用户目录中，可以使用相同的文件名，此外，不同用户还可使用不同的文件名访问系统中的同一个共享文件。
缺点：两级目录结构虽然能有效地将多个用户隔开，但当多个用户之间要相互合作去完成一个大任务，且一用户又需去访问其他用户的文件时，这种隔离便成为一个缺点，因为这种隔离会使诸用户之间不便于共享文件。
隔离使文件不便于共享
3 树形结构目录(Tree-Structured Directory)
树形目录可以提高目录的检索速度和文件系统的性能。
主目录在这里被称为根目录，在每个文件目录中，只能有一个根目录，每个文件和每个目录都只能有一个父目录。把数据文件称为树叶，其它的目录均作为树的结点，或称为子目录。下图示出了树形结构目录。
树形目录的缺点：在树形结构目录中查找一个文件，需要按路径名逐级访问中间节点，增加了磁盘访问次数，无疑影响了查询速度。
3.1 路径名和当前目录（相对路径和绝对路径）
- 路径名(path name)
在树形结构目录中，从根目录到任何数据文件都只有一条唯一的通路。在该路径上，从树的根(即主目录)开始，把全部目录文件名与数据文件名依次地用 “/” 连接起来，即构成该数据文件唯一的路径名。
- 当前目录(Current Directory)
当一个文件系统含有许多级时，每访问一个文件，都要使用从树根开始，直到树叶为止的、包括各中间节点(目录)名的全路径名。
全路径名是相当麻烦的事，由于一个进程运行时所访问的文件大多仅局限于某个范围，因而非常不便。基于这一点，可为每个进程设置一个"当前目录"，又称为“工作目录”。进程对各文件的访问都相对于“当前目录”而进行。此时各文件所使用的路径名只需从当前目录开始，逐级经过中间的目录文件最后到达要访问的数据文件。
把从当前目录开始直到数据文件为止所构成的路径名称为相对路径名(relative path name)，而把从树根开始的路径名称为绝对路径名(absolutepathname)。
4 目录查询技术
当用户要访问一个已存文件时，系统首先利用用户提供的文件名对目录进行查询，找出该文件的文件控制块或对应索引结点。然后，根据 FCB 或索引结点中记录的文件物理地址(盘块号)，换算出文件在磁盘上的物理位置。最后，再通过磁盘驱动程序将所需文件读入内存。
首先查询目录 -> 获取文件控制块 -> 获取文件的物理地址 -> 定位物理位置 -> 通过 I/O 读入内存
目前，对目录进行查询的方式主要有两种：线性检索法和 Hash 方法。
4.1 线性检索法
线性检索法又称为顺序检索法。在单级目录中，利用用户提供的文件名，用顺序查找法直接从文件目录中找到指名文件的目录项。在树形目录中，用户提供的文件名是由多个文件分量名组成的路径名，此时需对多级目录进行查找。
假定用户给定的文件路径名是 /usr/ast/mbox，则查找 /usr/ast/mbox 文件的过程如下图所示。
4.2 Hash 方法
如果我们建立了一张 Hash 索引文件目录，便可利用 Hash 方法进行查询，即系统利用用户提供的文件名，并将它变换为文件目录的索引值，再利用该索引值到目录中去查找，这样将显著地提高检索速度。
通过索引一步到位
顺便指出，在现代操作系统中，通常都提供了模式匹配功能，即在文件名中使用了通配符 “*”、“?” 等。对于使用了通配符的文件名，此时系统便无法利用 Hash 法检索目录，因此，系统还是需要利用线性查找法查找目录。
Hash 法的优势在于精确定位，无法进行范围查找