-2

我想用 Java 创建一个简单的 B+-Tree 实现，我需要一些帮助。我希望我的程序实现这些功能：搜索、插入、删除。

我的问题：

  1. 用来表示树的最佳数据结构是什么？我在想TreeMap。
  2. 在 B+-Tree 中，数据仅存储在叶节点 (K,V) 中，并且在内部节点中，而不是每条记录中的数据，都有一个指向子节点 (K,P) 的指针。我想要一个关于如何指向另一个节点的建议，因为我不能在 java 中使用指针。

另外，如果您有任何建议或者您有一个简单的实现我可以用作参考，请告诉我。

谢谢

4

1 回答 1

7

B-tree（或任何存在的小变体）的全部意义在于将数据存储在磁盘上，以便可以通过少量磁盘访问来读取它。如果您要将所有内容都保存在内存中，则应该使用平衡二叉搜索树（可能是红黑树或展开树），甚至是香草 BST，但您的问题似乎都没有考虑到这一事实。

  1. 用来表示树的最佳数据结构是什么？我在想TreeMap。

TreeMap是一种内存数据结构，因此尚不清楚这将如何帮助表示磁盘树。此外，这为您实现了一个二叉搜索树，因此如果您使用TreeMap.

  1. 在 B+-Tree 中，数据仅存储在叶节点 (K,V) 中，并且在内部节点中，而不是每条记录中的数据，都有一个指向子节点 (K,P) 的指针。我想要一个关于如何指向另一个节点的建议，因为我不能在 java 中使用指针。

您不需要实际的指针来表示 B 树，只需要文件偏移量。您需要定义一种表示这些偏移量的方法（从文件开头开始的字节数或块数，具体取决于实现的其余部分的结构）并根据文件偏移量访问所有内容。事实上，您不应该使用标准 C 风格的指针来指向 B+-树中的节点。如果你这样做了，那么下次程序启动时这些指针将毫无意义，因此你将失去磁盘数据结构的持久性优势。

要干净地访问文件内容，我建议使用内存映射。在 Java 中创建内存映射文件对象的一种有用方法是FileChannel.map。该方法返回一个MappedByteBuffer，您可以使用它来读取特定文件偏移量处的一大块字节。

于 2013-01-07T22:33:52.410 回答