操作系统入门（十） 文件系统篇之文件与目录的逻辑结构、文件索引节点

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

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

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

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

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

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

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

文件名：文件名称；

标识符：标识符是操作系统用于区分各个文件的一种内部名称;

类型;

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

大小：指明文件大小;

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

文件所有者信息;

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

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

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

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

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

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

类似于内存分为一个个“内存块”，外存会分为一个个“物理块（如果外存是磁盘，又称物理块为磁盘块）”。每个物理块的大小是相等的，一个物理块一般包含2的整数幂个物理地址，一个字节就是一个地址。一般而言，一个物理块包含
2^10 个字节，即 1KB。

每一个文件也有从0开始的逻辑地址，外存的一个外存地址会对应文件的一个逻辑地址。

文件的逻辑地址由“（逻辑块号，块内地址）”两部分组成，操作系统同样需要将逻辑地址转换为外存的物理地址“（物理块号，块内地址）”的形式。

如下所示：

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

01 文件的逻辑结构

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

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

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

根据各条记录的长度是否相等，又可分为定长记录和可变长记录两种。有结构文件的逻辑结构分为顺序文件、索引文件和索引顺序文件 3 种。

顺序文件

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

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

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

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

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

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

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

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

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

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

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

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

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

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

索引文件

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

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

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

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

小结一下就是，一个索引文件内部包括 连续存储的索引表和离散存储的记录内容 。索引文件这种逻辑结构优点是快速查找。

缺点在于两点：

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

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

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

第一个问题可以使用 二叉平衡树 代替 链表 来存储索引表。第二个问题可以使用索引顺序文件解决。

索引顺序文件

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

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

Q1: 如果单个分组的记录很多，那么在分组内检索速度慢的问题如何解决呢（毕竟要遍历分组内的所有记录）？

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

检索效率分析

顺序文件：

若一个顺序文件有10000个不定长记录，根据关键字检索文件，只能从头开始顺序遍历查找，平均须查找 5000 个记录。

一级索引顺序文件：

若采用索引顺序文件结构，可把 10000 个记录分为 100 组，每组 100 个记录。

那么需要先顺序查找 索引表找到记录所在分组的起始地址。由于有100个记录分组，因此索引表长度为 100行，平均需要查 50
次才能找到记录所在分组的起始地址。

找到分组后，再在分组中 顺序查找记录（每个分组100 个记录，因此平均需要查 50 次）。

可见，采用索引顺序文件结构后，平均查找次数减少为 50+50 = 100 次。

如果我们的文件不是存储10000条记录，而是存 10^6 个记录，则可分为 1000 个分组，每个分组 1000 个记录。根据关键字检索一个记录平均需要查找
500+500 = 1000 次。这个查找次数依然很多，所以使用多级索引顺序文件。

多级索引顺序文件：

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

对于一个含
10^6个记录的文件使用三级索引顺序文件来存储，前两级是索引表，最后一级才是记录本身。那么顶级索引表只有一个，有100行；二级索引表有100个，每个二级索引表有100行；底层的分组有100个，每个分组有100条记录。

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

02 目录的逻辑结构

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

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

文件控制块 FCB

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

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

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

最重要、最基本的还是 文件名 和 文件存放的物理地址 。 有了这两个字段，FCB 就实现了文件名 和
文件地址之间的映射，这也是FCB的最基本功能。注意，FCB中的“物理地址”具体是物理块号。

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

查询文件地址

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

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

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

目录的逻辑结构

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

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

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

但是有两个缺点：

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。

树形目录结构还未解决的问题是多个目录对同一文件的共享问题，假如目录A和B下要共享文件C，而且A和B下C的文件名不同，取名为C1和C2，那么A和B的目录文件都要增加一个FCB项来记录C文件的信息，造成数据冗余，此时就引入了索引节点的概念来解决这个问题；

此外树结构的特性是一个子节点只能有一个父节点，所以使用树结构无法实现文件C同时被 目录A 和
目录B同时指向，此时使用有向无环图代替树来实现目录结构可以解决这个问题。

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

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

什么是索引节点，为什么需要引入它呢？

我们知道一个FCB代表目录下的一个文件，FCB包含了一个文件的所有信息，包括文件名、文件地、文件大小、创建/修改时间等等。

但是在目录文件中查找文件地址只需要“文件名”和“文件地址”这两个信息。

如果每次加载一个目录文件的块到内存都要把文件的其他无用信息字段加载进来，会导致文件寻址所需磁盘IO的次数大大增多。

为此就引入了索引节点的概念，一个索引节点是包含除文件名外的所有文件描述信息的数据结构，包括文件在外存中的存放位置。一个FCB目录项只需包含文件名和索引节点指针即可。这样可以使一个FCB的大小减小很多。一个索引节点也代表着一个唯一的文件。

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

使用的索引节点的目录文件：

未使用索引结点的情况下，假设一个FCB是64B，物理块的大 小为1KB，则每个物理块中只能存放 16个FCB。

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

若使用索引结点机制，文件名占14B，索引结点指针站2B，一个FCB就只占 14+2=16B，则每个物理块可存放64个FCB，那么按文件名检索目录平均只需要
读入 320/64/2 = 2.5 个磁盘块（2.5次磁盘IO）。

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

而且索引节点还能解决前面所说的多个目录下共享同一个文件时，FCB数据冗余的问题。例如下面User1目录有一个“照片”文件，User2目录有一个“Mydemo”文件，但实际上他们都指向同一个文件地址，只是文件名不同。此时两个FCB指向同一个索引节点的地址。

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

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

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

1、优化了文件寻址时的IO次数。

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