c - 如何为文件系统实现 B+ 树？

Question

我有一个文本文件，其中包含有关文件系统中所有文件的范围的一些信息，如下所示 C:\Program Files\abcd.txt 12345 100 23456 200 C:\Program Files\bcde.txt 56789 50 26746 300 .. .

现在我有另一个二进制文件，它试图找出所有文件的范围。现在我正在使用线性搜索来查找上述文本文件中文件的范围信息。这是一个耗时的过程。有没有更好的编码方式？就像实现任何好的数据结构，比如 BTree。如果使用 B+ 树，我需要使用什么关键分支因子？

Answer 1

使用数据库。

在文件中实现树的关键点是具有固定的记录长度并使用文件偏移量而不是指针。

使用数据库。嗯，SQL Lite。

文件要考虑的另一点是读取数据块比读取单个项目更快（无论硬盘是否具有缓存或操作系统是否具有缓存）。我实现了一个 B+Tree，它使用页面作为它的节点。

使用数据库。数据库已经被编写和测试过了。

更有效的设计是将初始节点保留在内存中。这减少了从文件中提取的次数。如果您的程序有空间，将前几级保留在内存中也可以加快执行速度。

使用数据库。

我放弃了为我的应用程序编写 B-Tree 实现，因为我想专注于程序的其他功能。后来我了解到，在现实世界（程序需要按计划完成的世界）中，时间应该花在应用程序的“核心”上，而不是已经编写和测试过的附件（也就是架子）。

Answer 2

这取决于您要如何搜索文件。我假设您想在给定文件名的情况下查找您的信息。那么哈希表或Trie将是一个很好的数据结构。

B-tree 是可能的，但不是最方便的选择，因为您的键是字符串。