Existing implementation of Btree or B+tree in Java

Question

I am doing a project in which I require btree or b+tree data structure. Does anyone know of an existing implementation of btree or b+tree (with insert, delete, search algorithms)? It should accept string as input and form btree or b+tree of these string.

Answer 1

So let me get this straight. You don't want to do it because it would take up your 'precious' time, but you are quite happy to let other people spend their time doing it or finding it for you?

Answer 2

In the lack of details about the problem that you need to solve, I am going to allow myself to suggest an alternative solution that might solve your problem: use a red/black tree instead.

The red/black tree can be thought of as a b-tree, as explained on Wikipedia:

A red-black tree is similar in structure to a B-tree of order 4, where each node can contain between 1 to 3 values and (accordingly) between 2 to 4 child pointers. In such B-tree, each node will contain only one value matching the value in a black node of the red-black tree, with an optional value before and/or after it in the same node, both matching an equivalent red node of the red-black tree [...]

Java has two built-in classes, TreeMap and TreeSet, providing red/black trees. None of these will take a string as input and grow a tree from it, but you might be able to implement something similar "around" one of those classes.

Answer 3

jdbm has a very solid implementation of b+tree. Also h+tree which is an interesting related data structure.