图解fat32文件系统设计

有趣

有用

有态

设计文件系统思路

这一篇文章是带大家思考，fatfs文件系统是怎样逐步发展而来的，如果你是文件系统的设计者，你会怎么设计?希望从这个思考的过程，帮助大家掌握fatfs里面的一些基本概念。

要设计一种文件系统，说白了就是要实现一种文件名与文件数据的映射，也就是给定一个文件名后，就能找到它所对应的映射。这看似简单，事实上却不简单。要考虑的问题很多，比如数据的不连续存储、存储空间的有效利用等等。

这里我们从简单的实现算法开始思考，一步步逼近fatfs的设计思想。

原始文件系统

存储设备(flsh、软盘、硬盘)上面是由很多顺序分布的扇区所构成的，文件里面的内容就存储在这些扇区上面，最简单的算法，就是在先在扇区里面存储文件名，然后在文件名的后面存储对应数据。其他文件用同样的方法依次存储，最终文件系统里面的的布局如下图所示:

这种储存文件的方法，有一定的优点，比如说算法简单，没有任何的空间浪费，数据的储存十分紧凑等等。但是致命的缺点就是文件的搜索效率太低，每次查找文件的时候，遍历全部的扇区显然是非常愚蠢的办法。

改进方案一

把文件名全部保存在扇区的起始位置，这样就能避免对整个扇区的搜索了，如下图

可以看到，这里已经出现了一些内存空间的浪费，但这个是必然会存在的，空间换时间。另外的一个缺点是，现在文件的保存只能在连续的扇区保存，一旦小文件被删除之后，它腾出来的内存空间将不足以用来储存其他一些大文件。我们可以把它理解为"磁盘碎片"

改进方案二

要让数据可以跨扇区储存，又要知道各部分数据的具体存储位置，该如何实现呢?这时候我们应该想起链表这种数据结构，因为链表就是专门针对非连续空间存储的。我们可以在每个扇区的头部都设置一个专门的字段来记录扇区所属文件以及下一个扇区的地址，这样读取某一个扇区之后，就能知道下一个扇区在什么位置了。

这样，就能把"磁盘碎片"空间也拼凑起来使用了。只是现在我们定位一个文件的时候，还是得逐个扇区地读一下文件名，效率依然很低。

改进方案三

我们要解决遍历扇区的"恶梦"，就必须把文件名剥离出来，不能让随意地保存在扇区里面。否则永远摆脱不了遍历扇区的结局。我们现在回想一下，之所要把文件名保存在扇区上，无非是因为需要靠文件名帮助我们定位到文件的位置。

这其实跟我们看书非常相类似，我们拿到一本书，如果想找到某一个章节的内容，一个笨方法就是逐页地翻书，直到我们找到这个章节的名字。只不过这个笨方法我们都不喜欢用，我们直接通过书本前几页的目录就能得到目标章节的位置了。

我们模仿书的目录一样，拿出一些扇区专门用来记录文件名和它对应的数据其实位置。这样一来，当我们想到查找某些文件内容时，就查一下这个"目录"就可以了。这个"目录"我们把它叫做文件索引表。如下图:

改进方案四

现在每个扇区的头部还有一个专门的字段来记录扇区所属文件以及下一个扇区的地址，这个字段我们也把它剥离出来集中管理，像文件索引表一样，也用一些扇区来保存，这样子会显得整个文件系统，架构更加的清晰，管理更加方便。这些用来保扇区关系的扇区，在fatfs里面就叫做FAT(File Allocation Table)表，如下图:

改进方案五

当磁盘里面的扇区数量非常多的时候，它们之间的链式关系会非常复杂，FAT表需要白白消耗很多内存来储存它们，为了减小扇区间链式关系的复杂度，我们可以把多个扇区合并成一个新的储存单位。这样一来，新的储存单位间的链式关系就会简化很多。在fat32文件系统里面，这种新的储存单位称为簇。

总结

到这里，通过一个对文件系统不断迭代优化的过程，就把fatfs的基本概念，通俗易懂地介绍给大家了。希望大家能够深刻理解下面这几个概念的含义:

• 文件索引表
• FAT表
• 簇