一、导语

● 本文脉络：

① 介绍文件常用的逻辑结构：流式文件和记录式文件。

② 介绍文件常用的存取方法：顺序存取、直接存取和索引存取。

③ 介绍文件常见的物理结构：连续文件、串连文件和索引文件。

④ 介绍文件存储空间的管理方法。

⑤ 介绍文件的目录管理。（只作了解即可）

● 文件系统：操作系统中负责存取和管理信息的模块，它用统一的方式管理用户和系统信息的存储、检索、更新、共享和保护，并为用户提供了一整套方便有效的文件使用和操作方法。

▼小编：我们电脑的文件夹那些内部算法、处理机制等(例如：文件夹的新建与搜索)，就源自于本章。

二、文件系统的基础知识点

● 操作系统的功能包括：硬件资源和软件资源的管理。硬件资源的管理包括处理机管理、存储器管理、设备管理；软件资源的管理则包括对系统中程序和数据的管理。

为什么要学文件系统？

● 大量程序和数据，通常是以文件的形式存放在外存中的，需要的时候将其调入内存。因为用户使用计算机遇到的首要问题是如何保存程序和数据，然后是如何查找、复制、修改、删除它们。这些工作对于用户而言，是不能胜任也是不愿意承担的。计算机系统中的文件系统负责这些工作。文件系统是操作系统的重要组成部分，是操作系统中最直接、最常见的部分。

● 一个完善的文件系统必须具有以下功能：

① 辅助存储空间的管理。为了合理地存放文件，必须对磁盘等辅助空间进行统一管理。在用户创建新文件时为其分配空闲区，在用户删除或修改某个文件时，回收和调整存储区。

② 实现按名存取。需要有一个用户可见的文件的逻辑结构（就相当于，我们在文件夹里面能看到的 “文件名”，这是我们为它取的方便我们看的名字），用户按照文件逻辑结构所给的方式进行信息的存取和加工。

③ 文件的存放形式。为便于存放和加工信息，文件在存储设备上应按一定的顺序存放。这种存放方式被称为文件的物理结构。

④ 文件的查找。完成对存储设备上的文件信息的查找功能。

⑤ 文件的共享和保护。完成文件的共享和保护功能。

2.1 文件、记录和数据项

● 基于文件系统的概念可将 数据的组成 分为数据项、记录和文件三级。文件的三级结构如下图所示：

● 数据项：描述一个实体某种属性的字符集。数据项是数据组织中可以命名的最小单位，即原子数据，又称为数据元素或字段。例如，用于描述一个学生的基本数据项有：学号、姓名、性别、年龄、所在系等。

● 记录：一组相关数据项的集合。它用于描述一个实体在某个方面的属性。一个记录应包含哪些数据项，与其所描述的实体有关。例如，把学生作为班上的一名学生时，记录中应该包括学号、姓名、年龄及所在系等数据项。若把学生作为一个医疗对象时，则记录中应包含病历号、姓名、性别、以往病史等项。【比如：在上图中，“记录 3” 下接着三个 n 个数据项。那么，“记录 3” 如果是 “医疗对象”，那么 “数据项1、数据项2、数据项3、… 、数据项 n” 可以依次是 “姓名、性别、年龄、…、以往病史”】

◆ 注意：为了能惟一标识一个记录，必须在一个记录的各个数据项中确定出一个或多个数据项，称之为关键字。关键字能惟一标识一个记录的数据项。【比如说，在 名为“学生”的记录 和 名为“医疗对象”的记录 中，“性别” 这个数据项都存在，但它俩分别具有唯一的关键字 “学号”、“病历号” 作为区别标识】

● 文件：具有文件名的一组相关信息的集合。文件在文件系统中是一个最大的数据单位，它描述了一个实体集。例如可以将一个班的学生记录组成一个文件。一个文件必须要有一个文件名。文件名通常由字母和数字组成，它的格式和长度因系统而异。

◆ 除了文件名外，文件还具有以下一些其他的属性：【后面将对其进行讲解】

① 文件类型。如源文件、目标文件和可执行文件等。

② 文件长度。指文件长度的单位可以是字节、字或块。

③ 文件的物理位置。指示文件在哪个设备上，以及在该设备的哪个位置。

④ 文件的保护属性。如可读、可写、可执行、可删除等。

⑤ 文件的管理属性。如文件创建时间、最后存取时间等。

2.2 文件类型

① 按文件用途分类：系统文件、库文件和用户文件。

② 按存取属性分类：只读文件、读写文件和只执行文件。

③ 按信息流向分类：输入文件、输出文件和输入输出文件。

④ 按存放时限分类：临时文件、永久文件、档案文件。

2.3 文件系统模型

● 文件系统模型可以划分为3个层次：其最低层次是对象及其属性，中间层是对对象操纵和管理的软件的集合，最高层是文件系统提供给用户的接口。如下图所示：

● 文件管理的对象及其属性：

① 文件管理的对象：文件、目录和磁盘空间

② 文件是文件管理的直接对象。

③ 为方便用户对文件的存取和检索，文件系统中必须配置目录，对目录的组织和管理是方便用户和提高文件速度的关键。

④ 文件和目录必定占用存储空间（磁盘），对这部分空间的管理，不仅能提高外存的利用率，而且能加速对文件的存取速度。【就相当于，如果我们想找 D 盘里面某个文件，如果没有目录的话，全部文件都在 D 盘一点开的那个界面，都没有分类，就很难找。而有了目录的话，分好类的，就很方便我们找东西】

● 对对象操纵和管理的软件集合：【这是文件系统的核心，文件系统的功能大多是在这一层实现的。后面将对其学习】

① 文件存储空间管理。

② 文件目录管理。

③ 地址转换。

④ 文件读、写管理。

⑤ 文件的共享与保护。

● 文件系统的接口：

① 命令接口。是用户与文件系统交互的接口，用户可通过键盘终端键入命令，取得文件系统的服务。

② 程序接口。程序接口作为用户程序与文件系统的接口，用户程序可通过系统调用来取得文件系统的服务。

③ 图形接口。用户可以通过屏幕上的窗口和图标来操作计算机系统和运行自己的程序，从而大大方便了用户。

三、文件的逻辑结构与存取方法

● 对于一个文件，存在两种形式的结构：文件的逻辑结构和物理结构。

● 文件的逻辑结构是从用户的角度所观察到的文件组织形式，即我们肉眼可见的文件夹情况。（本小节讲）

● 文件的物理结构，又称文件的存储结构，是指文件在外存上的存储组织形式。（下一小节讲）

3.1 文件的逻辑结构

● 逻辑文件从结构上分可分为两类：无结构的流式文件和有结构的记录式文件。

① 流式文件 —— 文件内的数据是依次存放的一串信息集合。流式文件可以看成是无结构的文件，也可以看成只有一个记录的记录式文件。源程序、可执行文件、库函数等文件，通常采用的是无结构的流式文件。【为啥叫流式？是因为这种文件是一条流水线串通的，要用它，就用一条龙式地用它】

② 记录式文件 —— 由若干个记录组成。文件中的记录可以是顺序的，也可能是不存在相互关系。记录式文件中的记录长度可以是相等的，也可以是不等的。【为啥叫记录式？也就是用来记东西的】

3.2 文件的存取方法

● 从用户的角度来看，用户关心的是数据的逻辑结构，逻辑结构独立于物理环境。

● 从系统的角度来看，数据被文件系统按照某种规则排列和存放到物理存储介质上。

数据如何存储？数据如何检索？数据的逻辑结构和物理结构之间的怎样对接？这些都是文件的存取方法的主要任务。

● 存取方法是操作系统为用户程序提供的使用文件的技术和手段，常见的存取方法有：

① 顺序存取 —— 顺序存取是指在存取文件时严格按照记录的排列顺序依次存取。（顺序存取主要用于磁带文件，但也适用于磁盘上的顺序文件）

② 直接存取 —— 用户可以按照任意次序直接存取某个记录。可以根据记录的编号存取文件中的任一记录，或者在存取命令中指定文件的读写位置来存取文件。（直接存取方法通常用于磁盘文件）

③ 索引存取 —— 文件的记录是按它的记录键来编址，所以，用户提供给操作系统记录键后就可查找到所需记录。通常记录按记录键的某种顺序存放。（实际的系统中，大都采用多级索引，以加速记录查找过程）【这个将在后面重点学习】

四、文件的物理结构与存储设备 ⭐️⭐️

● 文件系统采用哪种逻辑结构和存取方法，和物理存储介质密切相关。

● 在文件系统中，文件的存储设备通常被划分为若干大小相等的物理块（簇）。与此相对应，为了有效地利用存储设备和便于管理，一般把文件信息也划分为与物理存储设备的物理块大小相等的逻辑块，从而，以块作为分配和传送信息的基本单位。

4.1 常见的物理结构

4.1.1 连续文件

● 连续文件：一种最简单的物理文件结构。它把逻辑文件中的信息顺序地存储到连续的物理盘块中，这样形成的文件称为顺序文件。 示意图如下：

◆ 对上图的说明：在 “文件说明信息” 中说明了 “文件起始块号” 和 “文件长度”，所以右图中文件 A 占用了 10、11、12、13 四个物理块。

● 在物理存储介质中的情况示意图如下：

● 连续文件的主要优点：

① 顺序存取容易。访问一个连续文件，只要在目录中找到该文件的第一个物理块号，然后顺序读取下去即可。

② 顺序存取速度快。连续文件所占用的物理块是同一磁道，或者是相邻磁道。因此，当要获得一批相邻的记录时，其存取速度在所有的文件结构中是最快的。

● 连续文件的主要缺点：

① 要求定量的连续存储空间。连续文件的增加和删除时，为了 保证连续性，必须移动大量信息。连续文件结构不宜用来存放用户文件、数据库文件等经常被修改的文件。存放连续文件必须要有连续的空间，容易产生不能使用的小碎片。

② 必须事先估计文件的长度。要将一个文件装入一个连续的存储区域中，必须事先估计文件的长度，然后根据其大小找到一个足够大的存储区中。

4.1.2 串联文件

● 串联文件：在将逻辑文件存储到外存上时，不要求为整个文件分配连续的空间，而是可以装入到离散的多个盘块中，然后再用链接指针将这些离散的盘块链接成一个队列，这样形成的物理文件称为链接文件。 示意图如下：【和《数据结构》中的链表有相似的思想】

◆ 对上图的说明：在 “文件说明信息” 中说明了 “文件起始块号” 即可，然后指针直接指向 10 的那个队列，队列尾部的 30 又指向下一个队列，依次往复，直到扫描到结束符 “^” 。

● 在物理存储介质中的情况示意图如下：

◆ 对上图的说明：这里的结束方式是指定了 “末地址”。一开始的 “始址” 为 9，故指向 “地址为 9 的物理块”，读取了里面的数据后，接着去读 “地址为 16 的物理块”…，直到最后读到 “末址”。

● 串联文件的优点是：

① 串联文件不需要连续的存储空间，消除了外零头问题，从而提高了存储空间利用率。

② 增加和删除记录时只需要修改指针即可，而不必移动大量的信息。

③ 文件动态增长时，可以动态的分配空间，而不必事先估计文件的最大长度。

● 串联文件的缺点是：

① 存取速度慢，不适于随机存取。

② 可靠性问题，如指针出错。

③ 更多的寻道次数和寻道时间。

④ 链接指针占用一定的空间。

4.1.3 索引文件 —— 样例(在下面) ⭐️⭐️⭐️

● 索引文件的结构要求系统为每个文件建立一张索引表，表中每一栏目指出文件信息所在的逻辑块号和与之对应的物理块号。索引表的物理地址则由文件说明信息项给出。 其结构如下图所示：【这里的 “索引表思想” 和前面的 “页表思想” 有异曲同工之妙。只不过后者是对内存下手，前者是对外存下手。】

◆ 对上图的说明：在 “文件说明信息” 中说明了 “索引表地址” 即可，然后指针直接指向索引表，指针会自动依次扫描完索引表上对应的所有逻辑块号，而每个逻辑块号和一个物理块号相对应，每个物理块号指向外存的一个物理存储空间 。

● 在物理存储介质中的情况示意图如下：

◆ 对上图的说明：在地址为 19 的这个物理块里面，专门存储了一张索引表，保存了即将依次访问的物理块号。

● 当一个文件含有很多个记录时，索引表会很长，既占有大量存储空间，又影响到检索速度。在此情况下便引入了多级索引。这是一种缩短索引表长度的方法。

● 该方法是再为索引表本身建立索引表，从而形成两级索引。如果二级索引表仍然很长，还可再建立三级索引、四级索引表等。但随着索引级数的增多，访问盘的次数会增加。

● Linux 操作系统采用的是便是混合索引方式：

① 每个文件的索引表规定为13个索引项，每项4个字节，登记一个存放文件信息的物理块号。

② 假设前面10项存放文件信息的物理块号，叫直接寻址。假设物理块的大小是4KB，直接寻址可以表示 40KB（4KB×10）的文件。

③ 如果文件大于10块，则利用第11项指向一个物理块，该块中最多可放1K个存放文件信息的物理块的块号。这种方式是一次间接寻址，可以表示4MB（4KB×1K）的文件。

④ 每个大型文件还可以利用第12和13项作二次和三次间接寻址，二次间接寻址可以表示4GB（4MB×1K）的文件，三次间接寻址可以表示4TB（4GB×1K）的文件。

● 混合索引方式的示意图如下：

◆ 对上图的说明：

① 地址为0~9的索引(总共10个)都是直接索引，一对一的形式(一个索引指向一个常规的物理块)。

② 而地址为10的索引就指向了一个特殊的物理块(它里面存储的不是常规数据，而是大小为1K的一层索引表)。如果用到这个东西就形成两级索引。

③ 同理，地址为11的索引地址就指向了一个更特殊的物理块(它里面存储的不是常规的的索引表，而是一个大小为1K的二层索引表，里面的每一个指针地址都指向 另一个大小为1K的一层索引表)

④ 同理，地址为12的索引地址就更更特殊了。刚刚看到的4TB的由来就和它有关。

● 索引文件优点：【保持了链接结构的优点，又解决了其缺点】

① 即能顺序存取，又能随机存取。

② 满足了文件动态增长、插入删除的要求。

③ 能充分利用外存空间。

● 索引文件的缺点：

① 较多的寻道次数和寻道时间。

② 索引表本身带来了系统开销。(如：内外存空间，存取时间)

● 举一个例子：某个文件系统，采用混合索引分配方式为文件分配磁盘空间，FCB 中共有 13 个地址项，每个盘块的大小为 512 字节，请回答下列问题:

① 如果每个盘块号只需要用 2 个字节来描述，则该文件系统需要设置几级间接索引？为什么？

② 如果每个盘块号需要用 3 个字节来描述，共允许每个盘块中存放 170 个盘块地址，而且 FCB 中采用 10 个直接地址项、1 个一级间接索引、1 个二级间接索引项和 1 个三级间接索引项，则对某个长度为 18000000 字节的文件，它共需占用多少个盘块（包括索引块)?

【请写出详细解题过程】

解：（注：FCB 是文件控制块，File control block 的缩写，在本文的 “6.2 文件控制块和索引结点” 有写其具体含义。）

问题①： [1] 1字节为8bit，2个字节 = 16bit。每个盘块号需要用2个字节来描述，而2字节能表示 2^16 = 65536 个地址。

[2] 因为每个盘块的大小为512字节，且每个盘块号需要用2个字节表示，所以每个盘块能存放512 ÷ 2 = 256个盘块地址。

[4] 所以，10 ( 直 接 寻 址 + 一 次 间 址 索 引 ) + 256 < 65536 < 10 + 256 +256^2 ( 直 接 寻 址 + 一 次 间 接 寻 址 + 二 次 间 址 索 引 )

[5] 答：该文件系统需要设置二级间接索引。

问题②： [1] 1字节为8bit，3个字节 = 24bit。每个盘块号需要用3个字节来描述，而3字节能表示 2^24 = 16,777,216 个地址。

[2] 每个盘块只能存放170个盘块地址。（额外分析：且每个盘块号需要用3个字节表示，所以每个盘块只存170 × 3 = 510个字节物理地址，其余 512 - 510 = 2 个字节置于空闲）

[3] 则对某个长度为18000000字节的文件，18000000 ÷ 512 ≈ 35156.25，向上取整为35157，故需要35157个盘块地址才行。

[4] 因为，10 + 170 + 170^2) ( 直 接 + 一 / 二 次 间 址 ) < 35156 < 10 + 170 + 170^2 + 170^3 ( 直 接 + 一 / 二 / 三 次 间 址 )

[5] 该文件系统需要设置三级间接索引。

[6] 故该文件不仅需要10个直接直接地址项，还需要使用一次、二次、三次间址项。

[7] 35157 - (10 + 170 + 170^2) = 35157 - 29080 = 6077，【这一步是为了把直接间址、一次间址、二次间址的物理块数减掉，好看在三次间址中的物理块使用情况】

[8] 因为 6077 / 170^2 的商为0，余数为6077，所以该文件在使用三次间址时只需要1(0+1=1)个二次间址块，而余数 6077 / 170得到的商为 35，余数为 127。故该文件在使用三次间址时还需要使用 36(35+1=36) 个一次间址块。

[9] 因此该文件需要：

总共的物理盘块数：35 × 170 + 127 + 170^2 + 170 + 10 = 35157 个【下图中，黑色的部分】

三次间址块(即三级索引块)：1(下图红色那个) 个

二次间址块(即二级索引块)：1(三次间址中的那个) + 1(原本的二次间址) = 2个

一次间址块(即一级索引块)：36(三次间址中的) + 170(三次间址中的) + 1(一次间址中的) = 207 个

共需占用多少个盘块（包括索引块)：35157 + 1 + 2 + 207 = 35367 个

问题 ② 的索引分配图如下：

4.2 文件的存储设备

● 常见的存储设备有磁盘、光盘、磁带等。其中磁盘又分为硬盘和软盘。

● 这里重点介绍以磁带为代表的顺序存储设备和以磁盘为代表直接存储设备的特性以及相关存取方法。

4.2.1 顺序存储设备

● 磁带：磁带是一种用于记录声音、图像、数字或其他信号的载有磁层的带状材料。（一种最典型的顺序存取设备）

● 顺序存取设备的特性：只有在前面的物理块存取访问后，才能存取后续的物理块。

● 顺序存取设备的物理结构特点：通常在两个相邻物理块间设计有一个间隙，磁带的访问速度与信息密度、块间间隙和磁带速度有关。若信息密度高，间隙小，带速高，则存取的速度高。另外，顺序存取速度与存取物理块的位置有关。距离磁头越近，存取的速度越高。其结构图如下：

4.2.2 直接存储设备

● 磁盘：计算机主要的存储介质，可以存储大量的二进制数据，并且断电后也能保持数据不丢失。（最典型的直接存取设备）

● 磁盘设备的特性：允许文件系统直接存取磁盘上的任意物理块。为了存取一个特定的物理块，磁头直接移动到所要求的位置上，而不需要顺序存取那样先存取其他物理块。

4.2.3 存储设备、文件的结构与存取方法之间的关系

● 经过前人的经验，总结出来的一张表：

◆ 对上图的说明：

① 最上层的 “存储设备” 有两种：磁盘和磁带。

② 每种磁盘有自己的下属的几个或一个 “物理结构”，每种 “物理结构” 都取了一些方便我们记忆的名字，就像上面的“连续文件”、“串联文件”。

③ 每一种物理结构都有自己所适应的，能装载的文件，固定长度的或者非固定长度的，以及相应的存取方法。

五、文件存储空间的管理

文件管理要解决的重要问题之一，就是如何为新创建的文件分配存储空间？

● 其解决方法与内存的分配情况有许多相似之处，即同样可采取连续分配方式或离散分配方式。前者具有较高的文件分配速度，但可能产生较多的外存碎片；后者能有效地利用外存空间，但分配速度慢。

● 无论是哪种分配方式，分配的基本单位都是磁盘块(物理块)而非字节。

● 为了实现存储空间的分配，首先系统必须知道存储空间的使用情况，为此，系统应为分配存储空间而设置相应的数据结构；其次，系统应提供对存储空间进行分配和回收的功能。

● 几种常用的文件存储空间的管理方法：空闲区表法、空闲链表法、位示图法。

5.1 空闲区表法

● 空闲区表法属于连续分配方式。它会为每个文件分配一个连续的存储空间。（它与 “上一节 4.1.1” 的连续文件类似）

● 空闲区表的构成：每一个空闲区对应于一个 “空闲区表项”。每个表项中包括：空闲区序号、空闲区起始盘块号和空闲区盘块数。所有的空闲区表项形成空闲区表。如下图所示：

● 空闲区表法的细则：系统为外存上的所有空闲区建立一张 “空闲区表”。空闲区表法分配时，系统依次扫描空闲区表，寻找合适的空闲块并修改登记项。删除文件释放空闲区时，把空闲块位置及连续的空闲块数填入空闲区表，如果出现邻接的空闲块，还需执行合并操作并修改登记项。空闲区表的搜索算法有优先适应、最佳适应和最坏适应算法等。

5.2 空闲链表法

● 空闲链表法：即将所有空头盘区连成一条空闲链。

● 根据构成链的基本元素不同，有两种链表形式：空闲盘块链和空闲盘区链。

① 空闲盘块链：把所有的空闲盘块链在一起组成一个链表。当用户创建文件需要一个或几个物理块时，就从链头上依次取下一块或几块。反之，当系统回收空闲块时，把释放的空闲块逐个插入链尾上。【它与 “上一节 4.1.2” 的串联文件类似】

② 空闲盘区法：把将磁盘上的所有空闲盘区（每个盘区可包含若干个盘块）连成一条链。在每个盘区上除含有用于指示下一个空闲盘区的指针外，还应标明本盘区的大小（即第二个数 → 盘块数）的信息。盘区的分配方法与内存的动态分区分配类似（即和连续文件的那种方法类似）。在回收盘区时，同样也要将与回收区邻接的空闲盘区与之合并。

5.3 位示图法

● 位示图(又称为字位映像表)：利用二进制的一位来表示磁盘中一个块的使用情况的一张表。当其值为 “0” 时，表示对应的盘块空闲；为“1”时，表示已分配。

● 磁盘上的所有盘块都有一个二进制位与之对应，这样，由所有块所对应的位形成了一个集合，称为位示图。

● 通常可用 m × n 个位数来构成位示图，并使 m × n 等于磁盘的总块数。 如下图所示：

● 盘块的分配：（利用位示图进行盘块的分配时，可分以下三步进行）

① 顺序扫描位示图，从中找出一个或一组其值为 “0” 的二进制位。

② 将它们转换成相应的盘块号。假定，找到其值为 “0” 的二进制位，处于位示图的第 i 行、第 j 列，则其相应的盘块号按下式计算：b = i × n + j。将盘块 b 分配出去。

③ 修改位示图，令 m a p [ i , j ] = 1。

● 盘块的回收：（利用位示图进行盘块的回收，可分为以下两步）

① 将已知的要回收的盘块号转换成位示图中的行号和列号，转换公式为：i = b / n 和 j = b % n 。

② 修改位示图，令 m a p [ i , j ] = 0。

六、文件目录 —— 只作了解

● 在现代的操作系统中，存储了大量的文件。为了对这些文件进行有效的管理，必须对它们加以妥善组织与归类，这主要就是通过文件目录来实现的。

6.1 文件目录管理的基本要求

● 文件目录也是一种数据结构，用于标识系统中文件及其物理地址，供检索时使用。

● 文件目录管理的要求如下：

① 实现 “按名存取” 。用户只需提供文件名，即可对文件进行存取，这是最基本的功能。

② 提高对目录的检索速度。通过合理组织目录结构的方法来加快对目录的检索速度，从而加快了对文件的存取速度。

③ 文件共享。在多用户系统中应允许多个用户共享一个文件，以节省大量的存储空间。【我们的电脑一般只有我们自己一个用户，但在学校的 Linux服务器 上，就有多个用户，函数调用库文件等就是共享的】

④ 允许文件重名。系统应允许不同用户对不同文件取用相同的名字，以便于用户按照自己的习惯命名和使用文件。

6.2 文件控制块和索引结点

● 从文件管理的角度看，一个文件包含两部分：

① 文件体：指文件本身的信息，即流式文件或者记录式文件。

② 文件控制块(即文件说明)：为了能对一个文件进行正确的存取，必须为文件设置用于描述和控制文件的数据结构，称之为文件控制块（FCB）。文件控制块至少包括文件名、文件在存储器上的物理地址、文件的逻辑结构、文件的物理结构、存取控制信息以及使用信息等。

◆ 补充说明：文件与文件控制块一一对应，而文件控制块的有序集合被称为文件目录。通常，一个文件目录也被看作是一个文件，称为目录文件。

● 另外，在检索目录文件的过程中，仅当找到一个其文件名与指定文件名相匹配的目录项时，才需读出该文件的物理地址；而在检索目录时，一概用不着该文件的描述信息。显然，这些信息在检索目录时不需调入内存。因此，在有些系统（如UNIX）中，便采用了把文件名与文件描述信息分开的办法。即把文件描述信息单独形成一个称为索引结点的数据结构，简称 i-结点；而在文件目录中的每个目录项，则仅由文件名及指向该文件所对应的i-结点的指针所构成。这样在查找目录的时候，大大节省了系统的开销。

6.3 文件的目录结构

● 文件目录结构的组织，关系到文件系统的存取速度、关系到文件共享性和安全性，因此，组织好文件的目录，是设计文件系统的重要环节。

● 目前常用的目录结构形式有：单级目录、二级目录和树型目录。

① 单级目录：在整个文件系统中只建立一张目录表，每个描述文件的属性占一个表项，表项中包含文件名、文件物理地址以及文件说明等。每当要建立一个文件时，先从目录表中找到一空白表项，再填入新建文件的文件名及其他说明信息；删除该文件时，清除该目录项。

◆ 单级目录结构的优点：简单，能实现目录管理的基本功能——按名存取。

◆ 单级目录结构的缺点：

[1] 查找速度慢。对于稍具规模的文件系统，会拥有可观的目录项，致使为查找一个目录项要花费较长的时间。

[2] 不允许重名。在一个目录表中的所有文件，都不被允许具有与另一文件相同的名字，然而重名问题在多道程序环境下却又是难以避免的。

[3] 难于实现文件共享。如果允许不同用户使用不同文件名来共享同一个文件，这在单级目录中是很难实现的。

② 二级目录：在二级目录中，第一级为主文件目录（MFD），它用于管理所有用户文件目录，它的目录项登记了系统接受的用户的名字以及该用户文件目录的地址。第二级为用户的文件目录（UFD），它为该用户的每个文件保存一登记栏，其内容与一级目录的目录项相同。每一用户只允许查看自己的文件目录。

③ 树形目录：二级目录的推广形成了树形目录，又称为多级目录。每一级目录可以是下一级目录的说明，也可以是文件的说明。树形目录是一棵倒向的有根树，树根是根目录；从根向下，每一个树枝是一个子目录；而树叶是文件。结构如下图所示：

● 文件的存取往往局限于某个范围中。因此，在树形结构中，可用当前目录，按相对路径名进行检索的方法，从而减少检索的层次，加快检索速度。所谓当前目录，表示检索时从该目录开始；相对路径名是从当前目录开始到文件的路径名。绝对路径名是从根目录开始到文件的路径名。

● 举个例子：

◆ 树形多级目录有许多优点：

① 较好地反映现实世界中具有层次关系的数据集合和较确切地反映系统内部文件的分支结构。

② 不同文件可以重名，只要它们不位于同一末端的子目录中。

③ 易于规定不同层次或子树中文件的不同存取权限，便于文件的保护、保密和共享等。

④ 查找搜索的速度快。

6.4 文件的共享

● 实现文件的共享也是文件管理系统的重要功能。文件的共享是指不同的用户共同使用同一个文件，以减少系统的开销。

● 文件的共享主要有两种方法：采用链接方法、采用基本文件目录方法。

① 采用链接方法：对经常使用的共享文件采用链接方法，即在自己的符号文件目录中，对需共享的文件建立相应的表目，这种链接可以在各层目录文件之间进行，也可以在目录文件和数据文件之间进行。比如下图中的 “9”，被 “3” 的 “4” 共用。

② 采用基本文件目录：这是一种事先进行文件共享的有效方法。如下图所示：【有点记事本、备忘录的思想】

◆ 对上图的说明：【BFD：基本文件目录。SFD：符号文件目录】

[1] 在主目录中有两个用户目录，ID = 3 是用户 Wang 的文件目录。

[2] 用户 Wang 用符号名 b.c(即一个用 C 语言编写的文件) 来访问 ID = 6 的共享文件。

[3] 而 Zhang 也可以用符号名 f.c 来访问 ID = 6 的共享文件。

[4] 可见，如果一个用户想共享另一个用户的文件，只需在自己的目录文件中新增一个表目，填上他为该文件起的符号名及该共享文件的唯一 ID 标识符即可。