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

Question

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

Answer 1

所有文件系统都是不同的，因此文件系统中实际使用的数据结构数量巨大。

许多文件系统使用某种 bit vector (通常称为位图)来跟踪某些空闲 block 的位置，因为它们在查询特定磁盘 block 是否正在使用方面具有出色的性能，并且(对于不是完全满的磁盘)支持合理快速地查找空闲 block .

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

XFS 文件系统因使用 B+-trees 而闻名几乎所有内容，包括目录结构及其日志系统。根据我在本科操作系统类(class)中的内存，其理念是，由于编写、调试和性能调整 B+-tree 的实现需要很长时间，因此尽可能多地使用它是有意义的。

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

我听说一些操作系统尝试使用 splay trees存储他们的目录结构，但遇到了麻烦。具体来说，它阻止了多个读取器对同一目录的多线程访问(因为在展开树中，每次访问都会 reshape 树)，并且遇到了一个边缘情况，如果树的所有元素都是按顺序访问的，那么树将退化为链表。也就是说，我不知道这是否只是一个都市传说，因为这些问题在任何人尝试编写它们之前就已经很明显了。

微软的 FAT32 系统使用一个巨大的数组(文件分配表)来存储哪些文件存储在哪里以及哪些磁盘扇区在一个文件中逻辑上彼此跟随。主要缺点是必须提前设置表，因此最终限制了可以存储在磁盘上的文件大小。然而，基于阵列的系统很容易实现。

这不是一个详尽的列表——我确信其他文件系统使用其他数据结构。但是，我希望它可以帮助您朝着正确的方向前进。

希望这可以帮助!