1

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

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

提前致谢。

4

3 回答 3

3

如果 B-Tree 结构必须从 RAM 写入 HD，您可能应该使用序列化

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

于 2013-04-03T01:45:38.570 回答
2

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

于 2013-04-02T14:46:52.347 回答
1

为了获得 rdbms 的灵感，检查嵌入式 Java 数据库的源代码可能是一个好主意：Derby、HyperSql、H2、...

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

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

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

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

如果树太大而无法放入内存，则必须使用带有某种内存缓存的RandomAccessFile 。尽管如此，经常访问的项目还是会从内存中消失。但是，您需要考虑对索引的更新。您必须在某个时候将它们刷新到磁盘。

所以，就个人而言，我宁愿不要从头开始这样做。而是使用那里的代码。:-)

于 2013-04-02T15:07:22.013 回答