B + -Tree in Java

Question

我想在Java中创建一个B + -Tree的简单实现,我需要一些帮助.我希望我的程序实现这些功能:搜索,插入,删除.

我的问题:

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

此外,如果您有任何建议,或者您想要一个简单的实现,我可以作为参考,请告诉我.

谢谢

Answer 1

B树的整个点(或任何存在的小变化)是将数据存储在磁盘上,以便可以使用少量磁盘访问来读取它.如果你要将所有内容保存在内存中,你应该使用平衡的二叉搜索树(可能是红黑树或splay树),甚至是一个香草BST,但你的问题似乎都没有考虑到这个事实.

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

TreeMap是一种内存中的数据结构,因此不清楚这将如何有助于表示磁盘上的树.此外,这为您实现了二叉搜索树,因此如果您使用,您自己并没有真正实现B树TreeMap.

2. 在B + -Tree中,数据被存储在叶节点(K,V)和内部节点中而不是每个记录中的数据中存在指向子节点(K,P)的指针.我想建议如何指向另一个节点因为我不能在java中使用指针.

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

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