文件系统的实现：FAT&UNIX文件系统

文件系统的工作本质上是把外部存储设备抽象成目录层次结构中的一棵树

文件系统需要通过设计一系列的数据结构来完成从存储设备驱动程序接口到用户可见的文件系统树与相应的文件系统API的抽象，这些数据结构都是要在存储设备当中实现的unix目录，也就是说，这些数据结构存放在这些持久化的存储设备里 ，而非RAM中，这也就使得对文件系统中的数据结构的设计与考量和传统数据结构并不相同

FAT(File Table)

FAT文件系统的最原始的构想是：用链表串联起来属于某个文件的所有块（因为当时存储设备容量有限，不能使用太复杂的数据结构），位于块末尾的每个指针所占的空间很小，不会造成什么开销，但如果想读文件的最后几个字节（lseek函数就会干这种事情），就要顺着链表逐个节点向后遍历，这就导致了会读很多不需要读的块，效率降低

为了解决这个问题，FAT中引入了文件分配表（File Table，这也是它命名的由来），文件分配表中记录了所有的块的next指针（next[3]就是3号块的指针，大概就是这样）文档系统，也就是把指针集中存储，如果指针的值是-1（也就是0xff...f），那就表示"end of file"，并且可以通过让指针的值等于某个特定的数字（FAT文件系统中使用的是0）来表示这个块空闲，这顺便解决了block /free的问题，但这也有个缺点，如果文件分配表损坏了，那磁盘的文件也将损坏

使用FAT文件系统的硬盘的布局如下：

最前面是一些，然后就是文件分配表文档系统，然后是真正存储文件数据的块

FAT文件系统为了解决文件分配表被损坏导致文件损坏的问题，给文件分配表做了多个备份

并且FAT文件系统中有簇（）的概念，每个块的大小不是固定的，它的粒度是可调节的

现在讲完了FAT文件系统中单个的文件的数据组织方法，那么目录层次结构/目录树是怎么实现的呢？

我们只需知道单个文件的第一个块的地址，就能把整个文件的内容从硬盘中读出来，对于目录来说，我们也把它当作一个普通文件，只不过它的内容是一组"key-value "，即从目录里的文件/子目录的名字到具体的文件数据块的映射，甚至可以说目录就是一个容器

其实目录里面不止记录了文件名到数据块的映射，还记录了文件的meat data（jyy对文件的/元数据的解释很精辟：文件除了数据以外，它自身作为一个对象的属性）

对FAT的性能分析如下：

FAT文件系统适合存储小容量的文件，但不适合对大文件进行随机访问，因为这会导致在文件分配表中上千次的跳跃（虽然说可以通过缓存这样的方式来解决这个问题，但性能总体来说还是很糟糕）

ext2/UNIX文件系统

如果希望文件系统更好地支持对大文件的随机访问，那就不能用链表，树更适合这一点；而且在实际的场景中一般对文件头部的读写会比文件其他部分多一些（比如说想加载或链接ELF文件必须先读ELF ），而且文件系统中绝大多数文件都是小文件，以及还有如下所示的各种实际

UNIX文件系统为了更好的支持这些，有如下特性 ：

ext2为了性能与可靠性，将磁盘分成了很多个group，每个group都是一个独立的文件系统

ext2中的inode就是前面所说的文件对象，其中包含了size,date,mode（文件读写权限）,etc.这些。如果想对文件对象进行/free，也就是说要创建文件对象的话，会借助，中的1/0会代表inode是否已经被分配

ext2文件系统为了实现树这样的索引结构，也应该实现block的/free，因此还要额外维护block的（它不像FAT只需要维护一堆next指针）

接下来分析索引结构的具体实现，如果我们完全参照二级页表那样的1024叉树来实现，那么小文件的索引结构会浪费很多空间，甚至有可能浪费的空间比它本身所占的空间大的多。因此ext2中的索引结构采取了"fast path+slow path"的设计思想，毕竟我们的需求就是“让对小文件的访问变快，让对文件的头部的访问变快”，以应对用户访问文件头和小文件频率高的，这样的访问模式和进程对虚拟地址空间的随机访问不一样，那么就可以采取如下的直接索引+间接索引的inode数据结构，相当于把数组和树结合起来了

基于inode的设计，ext2的目录比FAT简单的多，毕竟目录里不用存全部了

对ext2的性能分析如下：

Ref/参考自：

/video/?p=25

以上为用户投稿51细雨网整理发布，希望对大家有所帮助！

（编辑：南京站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!