用于构建文件系统的数据结构？

Question

什么数据结构最适合用于文件组织？B-Tree是最好的还是有另一种数据结构可以更快地访问文件和良好的组织？谢谢

Answer 1

所有文件系统都不同,因此实际上在文件系统中使用了大量的数据结构.

许多文件系统使用某种位向量(通常称为位图)来跟踪某些空闲块的位置,因为它们具有良好的性能,可用于查询特定的磁盘块是否正在使用中(对于非压倒性的磁盘) full)支持合理快速查找空闲块.

许多较旧的文件系统(ext和ext2)使用简单的链接列表存储目录结构.显然,这对于大多数应用程序来说实际上足够快,尽管使用大量大型目录的某些类型的应用程序遭受了明显的性能命中.

XFS文件系统因使用B + -trees而闻名,包括目录结构和日志系统.从我记得的本科操作系统课程开始,我们的理念是,由于编写,调试和性能需要很长时间才能调整B +树的实现,因此尽可能多地使用它是有意义的.

其他文件系统(ext3和ext4)使用我不太熟悉的称为HTree的B树变体.显然,它使用某种散列方案来保持分支因子高,以便使用极少的磁盘访问.

我听说有些操作系统尝试使用splay树来存储它们的目录结构但是遇到了麻烦.具体来说,它阻止了多个读取器对同一目录的多线程访问(因为在一个splay树中,每个访问重新整形树)并遇到一个边缘情况,如果树的所有元素都是顺序访问,树将退化为链表.也就是说,我不知道这是否只是一个都市传奇,因为在任何人试图编码之前这些问题都会显而易见.

微软的FAT32系统使用了一个巨大的阵列(文件分配表),它存储了哪些文件存储在哪里以及哪些磁盘扇区在文件中逻辑上相互跟随.主要缺点是必须提前设置表,因此最终存在可以存储在磁盘上的文件大小的上限.但是,基于阵列的系统非常容易实现.

这不是一个详尽的列表 - 我确信其他文件系统使用其他数据结构.但是,我希望它能帮助你推动正确的方向发展.

希望这可以帮助!