B-Tree在序列化方面是如何工作的？

Question

在Java中，我知道如果你要在硬盘上建立一个B-Tree索引，你可能应该使用序列化，因为B-Tree结构必须从RAM写到HD。我的问题是，如果以后我想从索引中查询一个键的值，是否可以将B-Tree的一部分反序列化为RAM？理想情况下，仅检索特定键的值。将整个索引提取到RAM是一个糟糕的设计，至少在B-Tree大于RAM大小的情况下是这样。

如果这是可能的，如果有人提供一些代码，那就太好了。DBMS是如何做到这一点的，是用Java还是C？

提前谢谢。

Answer 1

要了解关系型数据库是如何做到这一点的，最好检查一下嵌入式Java数据库的源代码: Derby、HyperSql、H2等。

如果这些数据库解决了您的问题，我宁愿忘记实现索引，立即使用它们的产品。因为它们是嵌入式的，所以不需要设置服务器。- rdbms代码是应用程序类路径的一部分-并且内存占用不大。

当然，如果这对你来说是可能的话...

如果这棵树可以很容易地装入内存，我强烈建议将它保留在那里。性能上的差异将是巨大的。更不用说在磁盘上保持更改同步、重新组织等的困难了。

当你需要存储它的时候，检查Externalizable而不是常规的序列化。序列化是出了名的缓慢和广泛。而Externalizable允许您控制写入磁盘的每个字节。更不用说将索引读回内存时的性能差异了。

如果树太大而无法放入内存，则必须使用带有某种内存缓存的RandomAccessFile。使得经常被访问的项目仍然会从存储器中取出。但是，您需要考虑对索引的更新。在某个时刻，您必须将它们刷新到磁盘。

所以，就我个人而言，我不想从头开始。而是使用现有的代码。:-)

Answer 2

你可能应该使用序列化，因为B树结构必须从内存写入硬盘

绝对不是。序列化是实现基于磁盘的B树时要使用的最后一种技术。您必须能够将单个节点读入内存，添加/删除键，更改指针等，并将它们放回原处。您还希望该文件能够被其他语言读取。您应该定义B树节点的独立于语言的表示形式。这并不难。除了RandomAccessFile提供的功能之外，您不需要任何其他东西。

Answer 3

您通常将B-tree拆分为几个“页面”，每个页面都有一些键值对，等等。然后，您一次只需要将一个页面加载到内存中。