zhouqijie

文件目录

目录管理是文件系统中重要的一部分软件。目录管理的主要任务：

  1. 对大量文件实施有效管理，即需要采用合理的数据结构记录好所有文件的属性信息。
  2. 实现按名存取。
  3. 提高对目录的检索速度，
  4. 支持文件共享和文件重名。



1、文件目录的基本概念

文件控制块(FCB)：

为了能对文件进行正确存取，必须为文件设置用于描述和控制文件的数据结构，称为文件控制块(File Control Block,FCB)。

每当创建一个文件时，系统都要为其建立一个FCB，FCB和文件一一对应。这样，每个文件有两部分组成：FCB和文件体。

  1. 有关文件存取控制的信息。（例如文件名、用户名、文件主存取权限、授权者存取权限，文件存取类型）
  2. 有关文件的结构的信息。（如文件的逻辑结构例如记录类型、记录数、记录长度、成组因子数等；文件的物理结构例如文件所在设备名、文件物理结构类、记录存放在外存的位置或文件索引位置）
  3. 有关文件索引的信息。（已打开文件的进程数、文件被修改的情况、文件最大和当前大小）
  4. 有关文件管理的信息。（文件建立日期、最近修改如期、文件访问日期、文件保留期限）

有了FCB，就可以建立文件名和外存空间中物理地址的对应关系，从而实现按名存取。系统存取文件时，先找到其FCB，从FCB中再找到文件物理位置就能存取文件信息。

文件目录和目录文件：

为了加快文件的查找速度，通常把FCB集中起来管理，文件控制块的有序集合称为文件目录(Directory)，每个FCB就是一个目录项。

文件目录也是以文件的形式保存在外存上的，这就形成了目录文件。因此文件目录的目录项有两种，一种是目录文件的FCB，一种是普通文件的FCB。

目录文件永远不会空，他至少包含两个目录项：当前目录.和父目录项..。

当用户要求存取某个文件时，系统需要逐层从外存查找目录文件的内容，最终找到所寻找的文件。所以文件目录和FCB是实现“按名存取”的重要数据结构。



2、目录文件的组织

目录文件的组织是指按目录项的设计和FCB的存储组织方法。不同的组织方法直接影响检索文件的速度，对整个文件系统的效率、性能、可靠性都有很大影响。

常用的组织方法有三种。

FCB线性表：

FCB线性表的方式最简单也最早使用。目录文件中直接存放该目录下所有文件和子目录文件FCB信息，组成了一个FCB线性表。

这样组织FCB，当文件很多时，目录文件本省可能占用大量的盘块数，使得目录检索速度很慢。

索引节点：

在检索目录文件过程中，其实只用到文件名，仅当找到一个目录项时，才从该目录项中读出该文件的物理地址，而其他文件描述信息在检索目录时用不到，不需要调入内存。
因此为了减少检索文件访问的物理块数，UNIX文件系统把文件目录项中的文件名和其他描述信息分开，后者单独组成定长的一个数据结构，称为索引节点”i-node”。这样每个文件都有一个唯一的索引节点，一个文件系统中所有文件的索引节点都集中存放在文件存储器上的索引节点区，并对每个索引节点编号，称索引节点号。

文件名 索引节点号
file1 1
file2 32

由于访问某一文件的过程，会频繁涉及文件的索引节点，不断地在内外存之间引用它，系统消耗很大。因此，在系统占用的内存区专门开辟一张表，即活动i节点表。活动索引节点除了文件的静态信息外，还需要增加文件使用中的动态信息。
当文件打开时，若在活动i-node表中找不到其索引节点，就要申请一个内存i节点，把外存i节点的内容复制到这个内存i节点中，随之就用这个内存i节点来控制文件读写。
通常，在最后一个用户关闭此文件后，内存i节点的内容被写到外存i节点中，然后释放内存i节点。

哈希表组织：

以上两种目录文件都是线性表组织目录项的，检索时都是采用线性搜索算法。
除此之外，目录文件还可以用哈希表存储，采用散列法管理FCB，即目录文件采用以文件名为关键字的直接文件的组织形式。

实现方法是目录文件每个目录项中存放一个块号，每个目录项都设一个序号下标，哈希函数以文件名来计算散列函数值，以该值定位目录文件中的目录项，然后找到块号所指块中的文件FCB。

该方法可以大幅度地减少目录搜索时间。插入和删除目录项都很简单，只需要考虑两个目录项冲突的情况，主难点是选择合适的哈希表长度与适当的哈希函数。

其他：

除了线性表和哈希表两种检索目录的数据结构，还可以采用其他的数据结构，例如B+树。NTFS文件系统就使用了B+树来存储大目录的索引信息。

B+树是一种平衡树。对于存储在磁盘上的数据来说，平衡树是一种理想的分类组织方式，这是因为它可以使得查找一个数据项所需的磁盘访问次数减到最小。

由于使用B+树存储文件，文件按顺序排列，所以可以快速地查找目录，并且可以快速返回已经排好的文件名。同时，因为B+树是向宽度扩展而不是深度扩展，NTFS的快速查找时间不会随着目录增大而增加。



3、目录的结构

目录结构的组织，不但关系到文件系统的检索速度，还关系到文件的共享性和安全性。因此设计好的目录结构是文件系统的重要内容。

目前的目录结构分为单级目录、二级目录、多级目录、图状目录结构。

单级目录：

单级目录是最简单的目录结构。整个文件系统仅维护一张总的目录表，系统中所有文件都在该表中。

优点:
实现简单。

缺点：

  1. 不允许文件重名。
  2. 文件查找速度慢。
  3. 不便于文件共享。

多级层次目录：

二级目录把系统中的目录分为一个主目录(MFD)和多个用户目录(UFD)。二级目录基本克服了单级目录的缺点，提高了检索速度，并部分地允许文件重名。
二级目录加以扩展形成多级层次目录，也称为树状目录，它可以明显地提高对目录的检索速度和文件系统的性能。

在多级层次结构目录中，根目录是唯一的，从根目录到任何数据文件都只有一条通路。
在该路径上，从根开始，把全部目录文件名和数据文件名，依次用/连接起来，即构成了该数据文件的路径名(PathName)。
系统中每个文件都有唯一的路径名，这种从根开始的路径名也成为绝对路径名(Absolute Path Name)。

当访问一个文件时，都采用绝对路径名访问文件是相当麻烦的，同时由于一个进程运行所访问的文件，大多局限在某个范围，因而非常不便。所以可以为每个进程设置一个当前目录(Current Directory)。
此时各文件使用的路径名，只需从当前目录开始，逐级经过中间的目录文件，最后到达要访问的数据文件，经过的路径称为相对路径(Relative Path)。

优点:

  1. 既方便用户查找文件，又可以把不同类型和不同用途的文件分类。
  2. 允许文件重名。
  3. 利用多级层次结构关系，可以更方便地指定保护文件的存取权限。

缺点：
不能直接支持文件或目录的共享。

图状目录结构：

为了使文件或目录可以被不同的目录所共享，对多级层次目录机构进行扩展，形成图状目录结构。如果允许文件被共享，即允许一个文件有多个父目录，不同的目录可以以相同或不同的文件名共享同一个文件。
这样形成的目录结构图不会出现环，所以是一个有向无环图目录机构。除了允许文件被共享，还支持目录被共享。则目录结构图中就可能出现环。

Linux系统支持多父目录，但其中一个是主父目录，它是文件的拥有者，且文件被物理存储在此目录下，其他父目录通过link方式来连接和引用文件，并且允许任一父目录删除共享文件。
Window系统实现被称为“快捷方式”的多父目录连接。

目录的检索：

Cre：不同的结构有不同的检索方式。



4、文件目录操作

类似文件操作，文件系统也提供一系列处理文件目录的系统调用和操作指令。

（END）