disk - 将 B+ 树写入磁盘时保持“链接”？

Question

我已经在 java 中完成了 B+ 树的实现，但像往常一样，它完全在主内存中。如何将 B+ 树存储到磁盘上？btree 的每个节点都包含指向其子节点的指针（主内存地址或对象引用），当 Btree 驻留在磁盘上时，我如何实现类似的事情？当 b+ 树在磁盘上时，什么替换了 b+ 树节点中的主内存地址？

这里已经发布了一个类似的问题： B+Tree on-disk implementation in Java

但我不完全理解答案。

请分享你的看法？

Answer 1

看一下github中JDBM3的代码。这个项目将 B+ 树和类似的数据结构保存到磁盘，你肯定会在那里找到答案。

Answer 2

以最简单的形式：您必须跟踪当前节点读取或写入的文件偏移量（从文件开头开始的字节数）。因此，在基于文件的 DB 上，您可以保存偏移量，而不是内存地址。

然后从文件中读取它时，您可以决定将其“缓存”在内存中，并保存给定节点的内存地址，或者只对偏移量进行操作。

话虽如此，我必须补充一点，通常基于文件的数据库比这更复杂，通过将节点写入页面（通常与磁盘上的页面大小相同）来优化磁盘访问。这样，您可以通过一次磁盘寻道操作（被认为是昂贵的操作）读取多个节点。