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

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

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

许多文件系统使用某种类型的 bit vector (通常称为位图)来跟踪某些空闲块的位置,因为它们具有优异的性能,用于查询特定的磁盘块是否正在使用(对于不是压倒多数的磁盘) )支持快速查找空闲块.

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

XFS文件系统是着名的使用 B+-trees 的一切,包括目录结构和其日志系统.从我本人的本科生操作课程,我的想法是,由于编写,调试和性能调整B树的实现需要很长时间,因此尽可能多地使用它.

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

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

Microsoft的FAT32系统使用了一个庞大的阵列(文件分配表),用于存储哪些文件存储在哪里,哪些磁盘扇区在逻辑上相互依存在一个文件中.主要的缺点是表必须提前设置,所以最终可以存储在磁盘上的文件的大小上限.然而,基于阵列的系统很容易实现.

这不是详尽的列表 – 我确信其他文件系统使用其他数据结构.但是,我希望它有助于推动正确的方向.

希望这可以帮助！

代码日志版权声明：

翻译自：http://stackoverflow.com/questions/14126575/data-structures-used-to-build-file-systems