413_文件目录
# 4.1_3_文件目录
在小节中我们会介绍文件目录特别重要的知识点，那么在我们平时生活当中对文件目录的使用其实很频繁的，比如说像 windows 操作系统里，我们随便打开一个逻辑磁盘，比如说 d 盘，里边就有很多各种各样的文件夹或者说文件目录，并且在这个 D 盘下面它也会有一系列的普通的文件
打开其中的某一个文件夹文件目录之后，里边也还会有更深一级的文件目录，还有一些普通的文件，像这种一层一层的目录结构对于我们用户来说有什么好处？很显然我们通过这样的目录结构可以很方便的找到我们的这些想要找的文件，可以使整个文件的存放的组织结构非常清晰，易于我们查找。
另外如果有编程经验的同学应该也写过操作文件相关的一些函数，比如说像打开文件这个操作，它其实就是用我们提供的文件路径名作为参数，然后根据路径一层一层往下去找到我们想要让这个程序控制的文件的，所以采用这样的目录结构的话，可以让用户很轻松的实现按名存取这件事情。
从操作系统的角度来看，这些文件目录应该是怎么实现的，这是我们在小节中需要重点探讨的问题。
所谓的文件目录其实就是我们很熟悉的 windows 操作系统的文件夹，要实现文件目录的功能，需要有一个很关键的数据结构，文件控制块的支持，所以我们首先会介绍什么是文件控制块，操作系统又是怎么用这种数据结构来实现文件目录的。
另外随着计算机的发展，文件目录的结构也出现了不同的变化，最早的系统只支持单极目录结构，之后出现了两极目录，在之后出现了树形目录，无环图目录结构，最后我们会接受索引节点相关的知识点，其实索引节点这种机制它是对文件控制快的一个优化，我们会按从上至下的顺序依次讲解。
# 文件控制块
我们首先来看一下什么是文件控制块，打开电脑中的 D 盘这个根目录，会发现这个根目录下面有一系列的文件夹，或者说一系列的文件目录，还有一些普通的文件，对于 D 盘这个根目录来说，它对应的目录文件就应该是这个样子。其实就是用一个所谓的目录表来表示这个目录下面它存放了哪些东西，在 D 盘当中的每一个文件，每一个文件夹都会对应目录表当中的一个表项，所以其实这些一条一条的目录项本身就是一条一条的记录，所以目录文件其实本身就是一种有结构的文件，它是由一条一条的记录组成的，而每一条记录会对应在这个目录下面的一个文件。
因此我们在这个地方看到的目录，其实它也是一种特殊的文件，可以看到在这个表当中标识了文件的文件名是什么，还标识了文件类型，比如说像照片这个文件它其实是一个目录文件，所以它的类型标识是目录，像对账单这个文件，它的类型就是 txt 文件
另外，在这个地方我们还需要注意一个很重要的信息就是，在表项当中记录了文件在外存当中存放的物理地址，放在外存中的什么位置，所以其实我们双击打开目录的时候，操作系统在背后做的事情是他会来查询这个根目录，D 盘这个根目录的目录文件，然后找到照片这个文件对应的目录项，之后根据目录项当中记录的文件的存放位置，从外存当中读入照片目录文件的数据，这样的话就可以知道照片这个目录下面还有哪些内容，这些内容就可以展示在我们用户面前了
打开照片这个目录之后，会发现里边有一系列的文件，那么同样的照片这个目录对应的目录文件，它也是由一条一条的目录项组成的，每个目录项会对应其中的一个文件，其实目录文件当中的这样的一条记录，它就是一个文件控制块，英文缩写是 FCB，所以其实这些 FCB 的有序结合就是所谓的文件目录，而一个 FCB 就是一个文件目录项，那很显然每一个文件都会对应一个 FCB。
另外从这个例子中，我们可以看到 FCB 中包含了有文件的一些基本信息，包括文件名、物理地址，还有文件的逻辑结构、物理结构等等一系列的基本信息。另外还会有文件存取权限、存取控制相关的一些信息，包括文件是否可读，是否可写等等。除了这些之外，还会有文件的一些使用信息，包括文件是在什么时候建立的，上一次修改的时间是多少等等。不过所有的这些信息当中最重要的还是文件名，还有文件的存放的物理地址这两个信息，
因为 FCB 存在的最重要的一个作用其实是为了实现让用户按名存取，就是按照文件的名字来操作一个文件这样的事情。所以 FCB 它必须建立起文件名到文件实际存放的物理地址这样的一个映射关系。因此最重要最基本的应该是文件名，还有物理地址这样的两个数据。
除了这个地方提到的这些信息以外，其实咱们之前提到过的文件的各种各样的那些属性，也可以存放在文件对应的 FCB 文件控制块当中。
接下来我们再来看一下，我们需要对文件目录进行哪些操作？
首先为了让用户能够实现按名存取，为了实现这件事，肯定是需要有一个对目录搜索的过程。当用户需要使用一个文件的时候，系统需要根据这个文件名来搜索目录，然后找到这个文件名对应的目录项。
第二，当我们创建一个文件的时候，这个文件肯定是放在某一个目录当中的，所以在这个文件所属的目录当中，就需要增加一个目录项，
与创建文件相反，当我们删除一个文件的时候，除了删除文件数据本身之外，也需要删除这个文件在目录当中对应的目录项。
另外系统还需要提供显示目录的功能，因为用户在查看各级目录的时候，肯定是需要知道这个目录下一级到底还有哪一些文件，哪一些目录，所以这个功能也是必须实现的。在显示目录的时候可以显示与这些文件相关的一些属性，这一点大家可以在自己的 windows 电脑上具体看一下。
最后我们需要知道的是文件的各种属性是保存在目录当中的，所以如果说文件的某些属性发生变化的时候，相应的肯定需要修改与它对应的目录项的内容，比如说我们对一个文件重命名，那么我们就需要把这个文件对应目录项的文件名信息给修改掉，这就是一般来说需要对目录进行的一些操作。
# 单级目录结构
通过之前的讲解，我们知道由文件控制快的有序集合，就组成了文件的目录，在操作系统发展的过程当中出现了各种各样的目录结构，在刚开始出现的叫做单级目录结构，
早期的操作系统，它只会在整个系统当中建立一张目录表，每个文件会占用一个目录表的目录项，这种单极目录结构是支持按名存取的，因为这个 FCB 当中其实也是包含文件名这个关键字。但是单级目录最大的一个缺点就是不允许文件重名，可以想象一下各个目录项的关键字是文件名，那么如果说出现了重名文件的话，比如说有一个文件叫 a，另一个文件也叫 a，那么当我们告诉操作系统，我们要按照文件名 a 来存取一个文件的时候，操作系统到底应该选择哪一个文件？
因此在单级目录结构当中是不允许文件重名的。所以我们在创建一个文件的时候，首先需要检查目录表当中到底有没有重名的文件，确定不重名之后才允许建立新文件，并且把新文件对应的目录项，也就是 FCB 插入到目录表当中。如果说计算机有很多用户在使用的话，那显然不同的用户的文件名是很容易重复的，因此单极目录结构不适用于多用户操作系统。为了解决这个问题，后来人们提出了两级目录结构
# 两级目录结构
在这种目录结构当中会把目录分为两级，第一集叫做主文件目录，英文缩写是 MFD 和用户的文件目录，英文缩写是 UFD
主文件目录就是记录了用户名，还有用户名对应的用户文件目录存放的位置。而一个用户文件目录又由这个用户的那些文件对应的 FCB 组成。由于不同的用户文件是存放在不同的用户文件目录下的，所以在这种情况下，不同用户的文件是允许重名的，比如说像 user1 用户，它有一个文件名叫 demo 的文件，user2 用户它也有一个文件名叫做 demo 的用文件，不过虽然它们的文件名是相同的，但是它们实际对应的文件数据是不同的两个数据。
除了允许不同用户的文件重名之外，在采用了两级目录结构之后，也可以通过目录来实现访问限制，比如说 user1 想要访问 user2 的用户文件目录的话，操作系统可以验证一下 user1 和 user2 这两个名字是否匹配，发现它不是 user2 就可以拒绝让他访问 user2 对应的用户文件目录，因此采用了这种两级目录结构之后，还是很方便实现这种对于访问的限制的。
但是采用这种目录结构的缺点就是用户不可以把自己的文件进行分类，因此人们又提出了多级目录结构
又叫树形目录结构，这也是现代操作系统当中很常用的一种目录结构，每一个目录下面可以有更低一级的目录，同时在各个目录下面也可以有一些普通的文件，并且不同目录下的文件是可以重名的，和刚才一样不同目录下的文件虽然说名字是相同的，但是他们实际对应的文件并不是同一个，如果说采用的是多级目录结构的话，用户或者用户进程想要访问某一个文件的时候，就需要用文件的路径名标识符来让操作系统根据这个文件路径名找到这个文件存放的位置。各级目录之间一般来说是用小斜线来隔开的，从根目录出发的路径称为绝对路径。比如说像 自拍.JPG，这个文件的绝对路径，也就是从根目录出发的路径，应该是根目录下面的照片这个目录，然后照片这个目录下面的 201508 目录，在 201508 这个目录下面才可以找到自拍这个文件对应的目录项，用户或者说用户进程想要访问这个文件的时候，就需要把路径名告诉系统，让操作系统会根据绝对路径一层一层的往下找下一集的目录。
刚开始它会从外存当中调入根目录对应的目录表，也就是这个目录文件，然后找到照片目录存放的位置，然后又从外存当中调入照片目录文件，然后再从这个目录当中找到 201508 目录在外存当中存放的位置，于是还需要再从外存调入 201508 目录对应的目录表文件，最后再查询目录表，才能找到 自拍.JPG 文件存放的实际位置。
所以如果从根目录这个地方开始一层一层往下寻找的话，整个过程需要三次读磁盘的 lO 操作，第一次是读入一级的目录，第二次是读入这级的目录，第三次是读入这级的目录。
不过在实际生活当中，用户经常会访问同一个目录内的多个文件，比如说一个用户他在连续的查看 201508 目录下面的各种各样的照片，那就意味着这个目录当中的那些内容是经常会被访问的，但是如果每一次访问 201508 当中的文件，都需要从根目录开始一层一层的往下寻找的话，显然每一次都需要三次读磁盘操作，这是很低效的，
所以我们可以设置一个当前目录，比如说此时我们已经打开了照片目录文件，也就是说照片这个目录文件已经是从外存掉入内存当中的了，我们可以把照片这个目录设置为当前目录，当用户想要访问某个文件的时候，就可以从当前目录出发，然后找到自己想要的文件，从当前目录出发的这种文件路径就叫做相对路径，比如说像 Linux 系统当中，如果说当前目录是照片这个目录，然后我们想要用相对路径来表示 自拍.JPG 这个文件的话，那么它的相对路径就是当前目录下面的 201508 这个目录下面的 自拍.JPG 这个文件，所以如果从当前目录出发的话，那么想要找到 自拍.JPG 存放的位置，我们只需要先查询内存当中当前目录表，找到 201508 目录文件在外存当中的存放位置，然后把目录调入内存，于是再从这个目录当中找到 自拍.JPG 存放的位置，这样的话整个过程只需要经过一次读磁盘操作，就可以知道 自拍.JPG 存放的位置了。所以可以看到在引入了当前目录和相对路径这种机制之后，磁盘 lO 的次数减少了，这就提升了访问文件的效率。
不过树形目录结构也并不是万能的，它可以很方便的对文件进行分类，层次结构清晰，也可以很方便的对文件进行管理和保护，但是树形结构不便于实现文件的共享，这个知识点也是经常在选择题当中进行考察的。为了解决这个问题，人们又提出了无环图目录结构
# 无环图目录结构
其实无环图目录结构和树形目录结构也比较相似，只不过是在树形目录结构的基础上，增加了这样的一些指向同一个节点的有向边，使整个目录的结构看起来是成为了一个有向无环图，有向无环图相关的知识点，是在数据结构当中进行学习的，这样的话就很方便的可以实现多个用户间的文件共享。
这个地方大家可能也会发现，可以用不同的文件名指向同一个文件，也就是说 user1 用户可以用 demo 这个文件名找到这个文件，而 user2 这个用户可以用 mydemo 这个文件名找到这个文件，他们指向的都是同一个，这个文件是被他俩所共享的，除了共享一个文件之外，甚至可以共享同一个目录，因为目录其实本身也是一个特殊的文件
在引用了共享功能之后，对于文件的删除就不能像以前那么简单，只要一个用户让删除一个文件，就把这个文件的实际数据给删除，因为这个文件有可能是被多个用户使用的
所以为了解决这个问题，可以为每一个这种共享节点设置一个共享计数器，比如说此时这个文件是正在被两个用户共享的，那么共享计数器就应该是二。此时如果用户一提出要删除文件这个请求的话，其实操作系统只是会把 user1 对应的目录项给删除，并且让共享计数器减一，而这个文件实际的内容并不会被直接删除，只有共享计数器的值减为 0 的时候，就意味着这个文件不再被任何用户所使用，在这个时候才可以把共享文件真正的删除。
大家需要注意的是共享文件和复制文件其实并不一样的，如果说 user1 只是复制了一个 use2 的文件的话，其实他们俩所拥有的文件并不是同一个文件，当 user1 对自己的文件副本进行修改的时候，原来的文件的数据并不会改变。
而如果说这个文件是被两个用户所共享的话，那么由于他们指向其实都是同一份文件的数据，因此只要其中的一个用户对这个文件数据进行更改，另一个用户那边也是可以看到这个文件数据在变化的。
以上就是我们需要掌握的 4 种目录结构，单极目录结构、2 级目录结构、树形目录结构和无环图目录结构。
# 索引节点（FCB 的改进）
最后我们来介绍一下什么是索引节点，这其实是对 FCB 这种数据结构的一种改进，通过之前的学习，我们知道由一系列的 FCB，也就是文件控制块，组成了一个一个的文件目录，但是其实操作系统在查找各级目录的过程当中，只需要使用文件名这个信息就可以了，而其他的这些而冗余的信息暂时不需要，只有文件名匹配的时候，才需要去关心这个文件存放的物理位置，
所以我们可以考虑让目录表进行一个简化，来提升搜索的效率。由于按照文件名来搜索目录的时候，并不需要关心除了文件名之外其他的所有的信息，因此可以把其他的这些信息放到另外一个地方，也就是索引节点当中。除了文件名之外，将文件的类型文件存放的物理位置等等这些信息都会放在文件对应的索引节点当中，每一个文件都会有一个唯一的索引节点，而采用了索引节点这种机制之后，目录当中只包含文件名，还有指向索引节点的指针这样的两个信息，这样的话目录表所需要占用的空间就会小很多。
我们来看一下，采用这种方式到底是怎么加快我们查找一个文件的效率的。我们假设一个文件控制块是 64 个字节，一个磁盘块的大小是 1KB，每个磁盘块只能存放 16 个 FCB，也就是说每个磁盘块只能有 16 个目录项
因此如果一个文件目录当中总共有 640 个目录项的话，那么这么多的目录项总共需要 40 个磁盘块才能存储。在这种情况下，我们按照文件名来检索目录，平均需要查找 320 个目录项，由于 320 个目录项需要 20 个磁盘块才可以存放得下，所以平均就需要启动磁盘 20 次，因为每次启动磁盘的读操作都只能读入一个磁盘块的内容，
但是如果我们采用的是索引节点机制的话，假设文件名只占 14 个字节，然后索引节点的指针是占 2 个字节，那么每个磁盘块就可以存放 64 个目录项，于是我们根据文件名按顺序来检索目录的时候，平均需要查询 320 个目录项，而 320 个目录项只需要 5 个磁盘块就可以存放了。所以如果采用的是这种方式的话，那么只需要 5 次启动磁盘的操作。由于 lO 操作都是比较耗时的，所以启动磁盘的次数减少了很多，那么在检索文件的时候速度也会提升很多，所以这是把其他的这些冗余信息全部放到索引节点当中所带来的一个好处，就是让文件的检索速度更加的快捷。
那系统根据文件名找到它所对应的索引节点之后，需要把这个索引节点调入内存之后，再根据这个索引节点当中保存的文件存放位置就可以找到这个文件了。
在外存当中的索引节点称为磁盘索引节点，当索引节点放入内存之后，就称为内存索引节点。相比于磁盘索引节点来说，内存索引节点需要再增加一些信息，比如说记录这个文件是否被修改，或者记录此时到底有几个进程正在访问这个文件等等这一系列的信息。
# 小结
那么在这个小节当中，我们学习了文件目录相关的内容，大家需要理解文件、FCB、目录项还有目录之间的一个组成的关系。另外大家也需要理解并记住，在单、两级还有多级目录结构当中，最主要的问题缺点到底是什么？其实每一种目录结构都是解决了上一种目录结构留下的最主要的问题。在多级目录结构当中，大家需要注意绝对路径、相对路径，还有当前目录这样的几个概念，
并且需要能够理解为什么根据相对路径来检索文件，可以减少磁盘 lO 的次数。那其实背后的原因在于每查询下一级的目录的时候，都需要启动磁盘 IO 把下一级目录对应的目录文件从外存调入内存，
多级目录结构当中不方便实现文件的共享，但是无环图目录结构很方便的可以实现文件共享。但是需要注意的是每一个共享节点会有一个共享计数器，只有共享计数器的数值为 0 的时候，才可以真正的删除这个共享节点。
最后我们介绍了文件目录的一个优化方式，除了文件名之外的所有信息都放到索引节点当中，这样的话就可以让目录表的表项就大幅度的减小，从而每个磁盘块可以存放更多的目录项。因此我们根据文件名来检索文件的时候，就可以有更少的磁盘 lO 的次数，为什么磁盘的次数会更少。这一点大家也需要理解。那么这个小节的内容十分重要，很容易在选择题当中进行考察，大家还需要通过课后习题进行进一步的巩固。
