听说NTFS文件系统基本上是b-tree。真的吗？其他文件系统呢？它们是什么树？
另外，FAT32 与 FAT16 有何不同？
FAT 文件系统使用什么样的树？
问问题
1987 次
4 回答
6
FAT（FAT12、FAT16 和 FAT32）不使用任何类型的树。除了描述分区本身的数据块外，还使用了两个有趣的数据结构。Microsoft和第三方提供了在嵌入式系统中编写兼容实现所需的完整详细信息。Wikipedia有一篇不错的文章作为替代起点，其中还包括很多关于它是如何发展成现在的历史的。
由于最初的问题是关于树的使用，我将简要介绍一下 FAT 文件系统中实际的小数据结构。有关准确的详细信息和历史记录，请参阅上述参考资料。
每个目录中的文件集存储在一个简单的列表中，最初按照文件的创建顺序。删除是通过将条目标记为已删除来完成的，因此后续文件创建可能会重新使用该插槽。列表中的每个条目都是一个固定大小的结构，并且刚好足够容纳经典的 8.3 文件名以及标志位、大小、日期和起始簇号。长文件名（还包括国际字符支持）是通过使用额外的目录条目插槽来保存长名称以及包含所有其余文件属性的原始 8.3 插槽来完成的。
磁盘上的每个文件都存储在一系列簇中，其中每个簇是固定数量的相邻磁盘块。每个目录（除了磁盘的根目录）就像一个文件，可以通过分配额外的集群来按需增长。
集群由（错误命名的）文件分配表管理，文件系统从该分配表中获取其通用名称。该表是一个压缩的插槽数组，磁盘分区中的每个集群都有一个。FAT12 的名称意味着每个插槽都是 12 位宽，FAT16 插槽是 16 位，而 FAT32 插槽是 32 位。槽存储空簇、最后簇和坏簇的代码值，或文件下一个簇的簇号。通过这种方式，文件的实际内容被表示为一个称为链的簇的链表。
更大的磁盘需要更宽的 FAT 条目和/或更大的分配单元。FAT12 基本上只存在于软盘上，其 4K 簇的上限对于大小永远不会超过 1MB 的媒体有意义。FAT16 和 FAT32 都常见于拇指驱动器和闪存卡上。FAT 大小的选择部分取决于预期的应用。
访问特定文件的内容很简单。从它的目录条目中，您可以了解它的总大小（以字节为单位）和它的第一个簇号。从簇号可以立即计算出第一个逻辑磁盘块的地址。从按簇号索引的 FAT 中，您可以找到分配给该文件的链中的每个已分配簇。
发现适合存储新文件或扩展现有文件的可用空间并不容易。FAT 文件系统只是用代码值标记空闲簇。查找一个或多个空闲簇需要搜索 FAT。
定位文件的目录条目也不是很快，因为目录没有排序，需要在目录中线性时间搜索所需文件。请注意，长文件名会占用每个长名称文件的多个目录条目，从而增加搜索时间。
FAT 仍然具有实现简单的优点，它可以在小型微处理器中完成，因此即使是小型嵌入式系统和 PC 之间的数据交换也可以以具有成本效益的方式完成。我怀疑它的怪癖和怪癖会因此而伴随我们很长时间。
于 2010-05-28T03:11:04.023 回答
1
这是一个关于 FAT16 与 FAT32 的漂亮图表。
名称 FAT16 和 FAT32 中的数字是指文件分配表条目所需的位数。
FAT16 使用 16 位文件分配表条目（2 个 16 分配单元）。
Windows 2000 保留了 FAT32 文件分配表项的前 4 位，这意味着 FAT32 最多有 2 个 28 个分配单元。但是，Windows 2000 格式实用程序将这个数字限制为 32 GB。
于 2010-05-24T04:41:24.690 回答
1
FAT32 使用 32 位数字来存储簇号。它支持最大 4 GiB 的更大磁盘和文件。
据我了解该主题，FAT 使用文件分配表，用于在磁盘上存储有关状态的数据。它似乎不使用树木。不过我可能是错的。
于 2010-05-24T04:45:44.147 回答