logo标签列表

Java中现有的B树或B+树实现

javadata-structuresb-tree
26

我正在进行一个项目，需要使用B树或B+树数据结构。有没有人知道现有的B树或B+树实现（带插入、删除、搜索算法）？它应该接受字符串作为输入并形成这些字符串的B树或B+树。

1
@rohit：我对你的问题进行了一些编辑，以使其不太容易被认为是“无法回答的问题”。如果您不喜欢我的更改，请随意撤销它们。 - Jørn Schou-Rode
你能详细说明一下你将使用这个数据结构做什么吗？ - Graphics Noob
4个回答
16
在缺乏解决问题的详细信息时，我将允许自己提出一种替代方案，可能解决您的问题：改用红黑树。
可以将红黑树视为B树，如Wikipedia所解释：
红黑树在结构上类似于顺序为4的B树，每个节点可以包含1到3个值和（相应地）2到4个子指针。在这样的B树中，每个节点将仅包含与红黑树中的黑色节点匹配的一个值，并且在同一节点中在其前面和/或后面具有可选值，两者均匹配红色节点[...]。
Java有两个内置类TreeMap和TreeSet，提供红黑树。 这些都不会以字符串作为输入并从中生成树，但您可能能够“围绕”其中一个类实现类似的功能。
14

jdbm拥有非常稳定的b+tree实现。此外，它还有一个有趣的相关数据结构：h+tree。

自那时起，就有了JDBM3和JDBM4，现在更名为MapDB。 - Peter Lamberg
@PeterLamberg 是的 - MapDB正在成为一个非常不错的项目。距离第一个稳定版本还有几周时间，但它看起来非常好。请注意，MapDB没有使用B+树，因为需要并发性能 - 我相信他们正在使用某种链接树。 - Kevin Day
2
这是我的基于磁盘的B+树实现。 https://github.com/myui/btree4j/ - myui
6

我不得不实现自己的代码并开源此代码。

尚未进行测试，但分割方法正是我一直在寻找的，可以用于每次插入和删除。由于只有两个元素，这几乎总是会发生。问题：您是否打乱顶层元素？假设您有从1-5000（这里以5000为例）的数据，并且您将第一个元素设置为300，那么将其设置为接近2500是不是更合理？ - Mukus
顺便说一下，你的回答加一分。 - Mukus
@TejaswiRana 我已经测试了5000个元素（1-5000），根节点最终的值为2048。默认实现是2-3树，但那只是为了测试目的。您可以在构造函数中传递树的顺序（minKeySize）。 - Justin
1
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接