本节开始介绍文件系统相关的基础知识，主要包括：文件的逻辑结构、物理结构、存储空间管理 以及 磁盘结构 这四部分，会分四篇文章讲解。

文件的逻辑结构讲的是一个文件内的数据如何存储到逻辑块上，块与块之间如何组织才能达到高效率查找和写入的事情。

文件的物理结构讲的是已分配给文件的磁盘块在物理硬件（磁盘）中如何组织的事情。

存储空间管理讲的是文件系统如何为一个文件分配空闲磁盘块的。

最后磁盘结构会介绍磁盘这一硬件结构、以及读写数据时磁盘的行为和磁盘调度算法。

 

一、文件属性和文件存储单位

在开始学习文件系统之前，我们需要先掌握下面几个问题：

 

1. 一个文件有哪些属性？

文件名；

标识符：一个系统内的各文件标识 符唯一，对用户来说毫无可读性，。标识符只是操作系统用于区分 各个文件的一种内部名称;

类型;

位置：文件存放的路径（让用户使 用）、在外存中的地址（操作系统 使用，对用户不可见）;

大小：指明文件大小;

创建时间、上次修改时间;

文件所有者信息;

保护信息：对文件进行保护的访问 控制信息;

 

2.文件内部的数据应该怎样组织起来？

文件分为有结构和无结构文件。

无结构文件：由一系列二进制或字符流组成，称为“流式文件”，如文本文件。

有结构文件：由 一组相似的记录组成，又称“记录式文件”。

 

3.文件数据的存储单位和组织方式

类似于内存分为一个个“内存块”，外存会分为一个个“块/磁盘块/物理块”。每个磁盘块的大小是相等的，每块一般包含2的整数幂个地址（一块包含 2^10 个字节，即 1KB。一个字节就是一个地址）。文件的逻辑地址也可以分为“（逻辑块号，块内地址）”，操作系统同样需要将逻辑地址转换为外存的物理地址“（物理块号，块内地址）”的形式。

如下所示：

 

操作系统以“块”为单位为文件分配存储空间，因此即使一个文件大小只有10B，但它依然需要占用 1KB 的磁盘块。外存中的数据读入内存时同样以块为单位。

 

 

二、文件的逻辑结构

按文件是否有结构分类，可以分为无结构文件、有结构文件两种。

无结构文件：文件内部的数据就是一系列二进制流或字符流组成。又称“流式文件”。不用探讨无结构文 件的“逻辑结构”问题。

有结构文件：由一组相似的记录组成，又称“记录式文件”。每条记录又若干个数据项（列）组成。如： 数据库表文件。一般来说，每条记录有一个数据项可作为关键字（例如记录的ID）。

 

根据各条记录的长度（占用的 存储空间）是否相等，又可分为定长记录和可变长记录两种。

 

有结构文件的逻辑结构分为顺序文件、索引文件和索引顺序文件 3 种。

 

1、顺序文件

指文件中的记录在逻辑上是顺序排列的。顺序文件又可以从3个方面分成多种情况：

a. 记录可以是定长的或可变长的;

b. 各个记录在物理上可以顺序存储（即连续存储，记录与记录间紧密排列）或链式存储（记录与记录间分散存储）。

 

c. 顺序文件按照 串结构 或 顺序结构 来组织顺序。

串结构是指记录的顺序与关键字（文件id）无关，通常是按记录的插入时间排序。

顺序结构是指记录的顺序按关键字排序。

 

接下来我们关注两个问题：已经知道了文件的起始地址（也就是第一个记录存放的位置）。能否快速找到第 i 个记录对应的地址？（即能否实现随机存取）？能否快速找到某个关键字对应的记录存放的位置？

 

对于连续存储且不定长记录的文件，由于每个记录长度不一，如果想要找到第i个记录的地址，在存储这个记录的时候需要计算每个记录的长度L，并和记录内容一起存起来。

从文件起始地址开始，读取第一个记录的长度 L0，得知第二个记录的位置；再读取第二个地址的长度L1，L0+L1得出第三个记录的位置；以此类推得到第 i 个记录的开始地址。

所以需要遍历前 i-1 个记录才能知道第 i 个记录的地址。

 

对于连续存储且定长记录的文件，可以根据 i * L直接得到第i个记录的地址。

所以连续存储且定长记录的文件才能快速找到第 i 个记录的位置。而且这些记录必须按照 关键字（记录ID） 排序才能用 二分查找 快速查找指定ID的记录。

 

顺序文件的缺点在于无法使用变长记录，只有记录是定长的情况下才能够快速找到第 i 个记录的地址。

然而每条记录的实际长度不会一样，如果每个字段分配长度少了就会截断数据，分配多了又会造成浪费，因此实际很多应用场景中又必须使用可变长记录。

此时可以使用索引文件。

 

2、索引文件

索引文件的每条记录是按链式存储的方式存在物理磁盘上的，此外还需要一张索引表记录 索引号、记录长度 和 记录的指针。索引号可以是 记录ID 或者其他的字段值。

索引表的每一行是连续存储、每个字段定长且按照索引号排序的表，每一行紧密的存放在一起的。

 

假设索引表每行的大小是 L 个字节，所以如果想查找文件中第 i 行记录的位置，通过 i*L 得到第 i 行记录的位置，查到第i行记录的指针字段ptr，再根据 ptr 得到记录内容。

由于索引表是按照记录ID排序，所以可以在索引表中用二分查找快速找到 指定ID的行和该文件记录的ptr。

综上，一个索引文件内部包括 连续存储的索引表 和 离散存储的记录内容。

 

索引文件这种逻辑结构优点是快速查找。

缺点在于两点：

1、如果在中间插入一个记录或者删除一个记录，会造成索引表中多个行的位置移动；

2、每个记录对应一个索引表项，因此索引表可能会很大。

比如：文件的每个记录平均只占 8B，而每个索引表项占32个字节，那么索引 表都要比文件内容本身大4倍，这样对存储空间的利用率就太低了。

第一个问题可以使用 二叉平衡树 代替 数据结构 来存储索引表。

第二个问题可以使用索引顺序文件解决。

 

 

3、索引顺序文件

索引顺序文件的关键是对记录按照某个字段进行分组，每个分组之间离散存储，分组内的每个记录连续存储。索引表的每行存储每个分组的开始地址，而不是存储每个记录内容的地址。

在索引表中对索引字段按照二分查找（如果是无序的就直接遍历找到指定的行）找到某个分组的地址，再在分组内遍历（如果分组内的记录是定长的，则无需遍历）。这样就可以让索引表的行大大减少。

 

Q1: 如果记录是不定长记录，而且单个分组的记录很多，那么在分组内检 索速度慢的问题如何解决呢？

答案是可以使用多级索引，假设索引表和分组是有层次的，分组位于最底层，上层都是索引表。除了顶层索引表之外，其他层的索引表都要进行分组（即分为多个索引表），第 i 层的索引表记录的是第i+1层的某个索引表的索引。只有倒数第二层的索引表记录的才是分组的索引。

 

4、检索效率分析

顺序文件：

若一个顺序文件有10000个记录，则根据关键字检索文件，只能从头开始顺序遍历查找（这里指的并不是定长记录、顺序结构 的顺序文件），平均须查找 5000 个记录。

 

一级索引顺序文件：

若采用索引顺序文件结构，可把 10000 个记录分为 100 组，每组 100 个记录。则需要先顺序查找 索引表找到分组（共100个分组，因此索引表长度为 100，平均需要查 50 次），找到分组后，再在分组中 顺序查找记录（每个分组100 个记录，因此平均需要查 50 次）。可见，采用索引顺序文件结构后，平均查 找次数减少为 50+50 = 100 次。

同理，若文件共有 10^6个记录，则可分为 1000 个分组，每个分组 1000 个记录。根据关键字检索一个记录

平均需要查找 500+500 = 1000 次。这个查找次数依然很多，所以使用多级索引顺序文件。

 

多级索引顺序文件：

Tips: 要为 N 个记录的文件 建立 K 级索引，则最优的 分组是每组 N1/(K+1)个记录。

对于一个含 10^6个记录的文件使用三级索引顺序文件来存储，可先 为该文件建立一张二级索引表，把所有记录按每 100 个记录为一组，故二级索引表中共有 10^6 / 100 = 10000 个表项（即10000个定长 记录），再把有10^4行二级索引表分组，每组100个，为其建立顶级索引表，故二级索引表有100个分组，顶级索引表只有一个，其中共有 100 个表项。

此时平均查找次数是 (100/2) * 3 = 150 次

 

 

三、目录文件和目录的逻辑结构

目录本身是一种有结构的文件， 里面每条记录对应一个在 放在该目录下的文件。后面所有内容中的“目录文件”都是指目录自己本身这个文件，而不是指目录内的文件。

当我们双击“照片”后，操作系统会在这个目录表中找到关键字 “照片”对应的目录项（也就是记录），然后根据记录的物理地址字段从外存中将“照片”目录文件的信息读入内存，于是，“照片”目录中的内容就可以显示出来了。

 

1、文件控制块

目录文件中的一条记录就是一个“文件控制块（FCB）”，一个文件控制块记录了一个文件或者目录的相关信息，可以用一个状态字段标识该FCB是普通文件还是目录文件。

一个目录文件采用链式存储，即一个目录文件的所有FCB记录被分为多个块，一个块中包含多条FCB记录，块内的多个FCB是顺序存储，块和块之间离散存储。目录文件持存储着指向第一个块的指针。

目录文件内部就是FCB的有序集合（即上图中的目录表），FCB 中包含了文件的基本信息（文件名、物理地址、逻辑结构、物 理结构等），存取控制信息（是否可读/可写、禁止访问的用户名 单等），使用信息（如文件的建立时间、修改时间等）。

 

最重要、最基本的还是 文件名、文件存放的物理地址。有了这两个字段，FCB 就实现了文件名和 文件地址之间的映射（这也是FCB的最基本功能）。使用户（用户程序）可以实现“按名存取”。

注意，FCB中的“物理地址”是盘块号。

一个文件的描述信息放在FCB中，而FCB又是放在目录文件中的。这么一来，如果修改一个文件的内容，就要修改该文件所在目录内的对应FCB信息（如修改时间和大小）；如果删除一个文件，就要删除改目录文件中的对应FCB项；如果创建一个文件，就要遍历整个目录文件的每一项，以防重名，并且添加创建文件的FCB。

 

2、查询文件地址

根据文件名查找它的外存地址的过程是怎么样的？

首先要把文件所在目录的目录文件的第一个块从磁盘调入内存，将目标文件名和块内的所有FCB的文件名比对，如果未找到指定文件，再将下一个块调入内存，再比对。找到目标FCB后，查询FCB中的物理地址。

假设目录文件有N个块，目标FCB在所有FCB中间，则找到目标FCB所需的平均IO次数是 N/2次。

 

 

3、目录的逻辑结构

 

单级目录

早期操作系统不支持多级目录，整个系统只有一张目录表，每个文件占一个目录项。这样的目录文件就是单级目录。

因为整个系统只有一个目录表，所以不允许文件重名。单级目录结构不适用于多用户操作系统。

 

两级目录

早期的多用户操作系统，整个系统就包含两级目录。顶级目录是主目录，主目录下有多个用户目录，一个用户对应一个目录，每个用户的所有文件都在它自己的用户目录下。

这样的系统采用两级目录结构。分为主文件目录（MFD）和用户 文件目录（UFD）。

主文件目录记 录用户名及相 应用户目 录文件的存放位置，而用户目录文件里的文件内容就是某个用户的所有文件的FCB。

 

两级目录结构允许不同用户的文件重名，也可 以在目录上实现实现访问限制（检查此时登录 的用户名是否匹配）。

但是有两个缺点：

1、用户不能对自己的文件进行分类；

2、同一用户下的所有文件不能有重名的文件。

多级目录结构（树形目录结构）

为了克服两级目录的缺点，现代操作系统允许一个主机有多层目录，即一个目录A下可以有目录B，目录B下还可以有目录C甚至更多层级的目录。

为了管理主机中多层级的目录，现代操作系统使用树形目录结构来管理这些目录。

 

用户进程要访问某个文件时要用文件路径名标识文件，文件路径名是个字符串。按文件路径访问分为 按绝对路径访问 和 按相对路径访问。

相对路径和绝对路径大家都听过，但是他们具体是如何根据路径访问到指定的文件，这两种访问方式在IO请求的角度有什么区别？

答案是IO操作次数不同。如果访问一个绝对路径：/a/b/c/d.jpg，那么需要从根目录的目录文件内容从磁盘写入到内存，根据目录名查询到 a 目录的外存地址，并将a目录文件从磁盘读到内存，这样就发生了2次IO，同理b、c的目录文件从磁盘加载到内存也是2次IO。因此查询 d.jpg 的外存地址需要花4次磁盘IO（假设根目录的目录文件是永驻内存的，那么也要花3次IO）。

当用户已经在 c目录下，系统会把c目录设置为当前目录，即 c 目录文件已经加载到内存中了。如果用户此时还是用 /a/b/c/d.jpg 访问 d.jpg ，那么依旧要花4次IO。但如果直接访问相对地址 ./d.jpg，则系统直达从当前目录的目录文件中查询，当前目录的目录文件已经在内存中了，所以花费 0 次IO就能查出d.jpg的地址。

上面是假设每个目录文件的大小只占1个块，由于每次磁盘IO是读出一个块（因为一个IO指令只能指明一个块的开始地址，而一个指令就是一个IO请求），所以读出一个目录文件的所有内容只需1次磁盘IO。如果一个目录下的文件数量很多，那么一个目录文件的大小不止一个块，所以一个目录文件从磁盘读到内存可能需要多次IO。

树形目录结构还未解决的缺点是不利于多个目录对同一文件的共享，因为假如目录A和B下要共享文件C，而且A和B下C的文件名不同，取名为C1和C2，那么A和B的目录文件都要增加一个FCB项，两个FCB除了文件名不同，其他的文件信息都相同，这样就造成了数据冗余；假如引入了下面要介绍的索引节点解决了数据冗余问题，但树结构的特性是一个子节点只能有一个父节点，所以使用树结构无法实现文件C的索引节点被 A 和 B同时指向，此时使用有向无环图代替树来实现目录结构可以解决这个问题。

所以，有向无环图目录 + 索引节点 可以实现 多目录对同一文件共享。

 

 

无环图目录结构

 

 

使用无环图这一数据结构，可以在不同的目录用不同的文件名指向同一个文件（普通文件或目录文件）。

需要为每个共享iNode结点设置一个共享计数器，用于记录此时有多少个地方在共享该结点。用户提出删除结 点的请求时，只是删除该用户的FCB、并使共享计数器减1，并不会直接删除共享结点。

只有共享计数器减为0时，才删除结点。

 

 

四、索引节点（iNode节点 或 i节点）

假设一个FCB包含一个文件的所有信息，但是在目录文件中查找文件地址只需要“文件名”和“文件地址”这两个信息。然而每次加载一个目录文件的块到内存都会把文件的其他无用信息字段加载进来，会导致文件寻址所需磁盘IO的次数较多。

索引节点包含除文件名外的文件描述信息，一个FCB目录项只需包含文件名和索引节点指针即可。这样可以使一个FCB的大小减小很多。

索引节点也代表着一个唯一的文件。

未使用的iNode节点的目录文件：

 

使用的iNode节点的目录文件：

 

未使用索引结点机制，假设一个FCB是64B，磁盘块的大 小为1KB，则每个盘块中只能存放 16个FCB。

若一个文件目录中共有 640个目录项，则共需要占用 640/16 = 40 个盘块。因此按照某 文件名检索该目录，平均需要发生20次磁盘IO（每次磁盘I/O读入一块）。

若使用索引结点机制，文件名占14B，索引结点指针站2B，则每 个盘块可存放64个目录项，那么按文件名检索目录平均只需要 读入 320/64 = 5 个磁盘块（5次磁盘IO），再加上把目标FCB下的索引节点加载到内存，一共是6次IO。

当找到文件名对应的目录项时，才需要将索引结点从磁盘调入内存，索引结点中记录了文件的各种信息，包括 文件在外存中的存放位置，根据“存放位置”即可找到文件。

存放在外存中的索引结点称为“磁盘索引结点”，当索引结点放入内存后称为“内存索引结点”。 内存索引结点相比外存索引节点需要增加一些信息，比如：文件是否被修改、此时有几个进程正在访问该文件 、索引节点在内存中的编号等。

 

使用索引节点的优点总结：

1、优化了查询文件地址时的IO次数。

2、方便实现同一文件在不同目录的共享。