algorithm - 将 Btrees 保存到磁盘文件并读取它

Question

我想在磁盘文件中保存一个 Btree（不确定是二进制的）。然后将其读入内存。一些级别顺序遍历可能是二叉 Btree 的好方法。但如果它不是二进制的。我在内存中建立了从叶子节点到根节点的 Btree。我相信我必须在磁盘文件中定义一些结构并输出树节点。使用一些额外的标签来识别文件中的节点？如何遍历可能是这里的关键问题。我想不出保存节点和指针的好方法。然后阅读它。在内存中重新构造树。有什么好主意吗？多谢。

Answer 1

B-Trees的常用技术是确保一个节点的大小等于磁盘的块大小，然后mmap磁盘文件。您没有指定您正在使用哪种编程语言，因此它可能像 C 中的强制转换一样简单，或者更复杂一些，例如创建享元对象来包装 java.nio.IntBuffer。无论哪种方式，B-tree 的大部分优点是您不必一次全部加载，而是可以相当有效地跳过它。

Answer 2

如果您真的想做类似的事情，您可以在每个节点上分配一个 id 并以该格式保存节点：

[node-id 值 left-node-id right-node-id]

然后用广度优先搜索访问树。

当您要重建树时，创建一个映射 id->node 然后向后读取文件：因此，当您读取记录时，创建节点，将其注册到映射并分配左右节点，从中获取节点地图。

Answer 3

对于每个节点，定义一些数据结构，它将为您保留节点所具有的相同信息，并向该结构添加附加字段，该字段将为您标记下一个儿子在文件中的偏移量。并将该结构的顶部字段设置为实际大小，因为您不知道您现在正在寻找哪种树。现在通过跳过文件，您将能够重建您的树。我确信我的解决方案不是最终的，但我希望它可以成为你的好榜样。

Answer 4

您可能想查看Protocol Buffers。它们是紧凑的、二进制的、可扩展的、易于读写的，并且可用于 C++、Java 和 Python（以及其他语言的第三方实现）。

您可以为 BTree 节点定义一个协议缓冲区消息，为子节点定义文件偏移量，然后以显而易见的方式将其序列化到磁盘。