c++ - C/C++：如何将数据存储在 B 树中的文件中

Question

在我看来，将数据作为文件存储在 B 树中的一种方法可以使用 C 使用具有结构序列（数组）的二进制文件有效地完成，每个结构代表一个节点。因此，可以使用类似于使用数组创建链表的方法连接各个节点。但是接下来的问题是删除一个节点，因为在一个巨大的文件中只擦除中间的几个字节是不可能的。

删除的一种方法可能是跟踪“空”节点，直到达到阈值截止，然后制作另一个将丢弃空节点的文件。但这很乏味。

从简单/效率的角度来看，是否有更好的方法来删除，甚至在文件中表示 B 树？

TIA，-斯维亚

Answer 1

为了在文件中实现 B 树，您可以使用文件偏移量而不是指针。此外，您可以实现“文件内存管理器”，以便您可以重新使用文件中已删除的项目。

为了完全恢复 B-Tree 文件中已删除的块，您必须在新文件中重新创建 B-Tree。还要记住大多数操作系统没有截断文件的方法。截断文件的一种可移植方法是写入一个新文件并销毁旧文件。

另一个建议是将文件划分为 B-Tree 分区和数据（项目）分区。B-Tree 分区将包含页面。叶页将包含数据项的偏移量。数据分区将是文件中包含数据项的部分。您最终可能会为每个分区创建多个分区，并且这些分区可能是交错的。

我花了很多时间玩基于文件的 B-Tree，直到我放弃并决定让数据库程序（或服务器）为我处理数据。

Answer 2

我做了一个非常快速的搜索并挖掘了这个： http: //people.csail.mit.edu/jaffer/WB C 来源：http ://cvs.savannah.gnu.org/viewvc/wb/wb/c/ -它似乎提供了基于磁盘的 B-tree 样式数据库——虽然看一下“delete.c”，但它似乎暗示如果你删除一个节点，从它下面的所有东西都会被删除——如果这是正确的行为，那么它听起来像可能有帮助的东西？

另外——B-trees 经常用在文件系统中——你能不看一些文件系统代码吗？

我自己的倾向是文件系统——如果你有一个固定大小的 B-tree，每当你“删除”一个节点而不是试图删除引用时，只需将值设置为在你的代码中没有任何意义的值。然后，运行一个清理线程来检查是否有人打开了文件以供读取，以及是否所有的安静都阻塞了文件并进行了整理。

Answer 3

您也可以使用 Berkley DB。它适用于 C 程序并实现 B+ 树。