26

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.

Jørn Schou-Rode
  • 37,718
  • 15
  • 88
  • 122
rohit
  • 423
  • 1
  • 6
  • 12
  • 1
    @rohit: I have done some editing of your question to make it a less obvious candidate for "close as not a real question". If you do not like my changes, feel free to revert them. – Jørn Schou-Rode Apr 04 '10 at 15:06
  • Can you elaborate on what you're going to be using the data structure for? – Graphics Noob Apr 04 '10 at 15:55

4 Answers4

16

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.

James Boutcher
  • 2,593
  • 1
  • 25
  • 37
Jørn Schou-Rode
  • 37,718
  • 15
  • 88
  • 122
14

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

Kevin Day
  • 16,067
  • 8
  • 44
  • 68
  • Since then there has been [JDBM3](https://github.com/jankotek/JDBM3) and [JDBM4 which was renamed to MapDB](http://www.mapdb.org/). – Peter Lamberg Dec 29 '13 at 05:31
  • @PeterLamberg yes - MapDB is shaping up to be a very nice project. Still a few weeks from first stable release, but it looks very good. Note that MapDB isn't using b+tree b/c of concurrency requirements - I believe they are using a linked tree of some sort. – Kevin Day Jan 02 '14 at 00:28
  • 2
    Here is my disk-based B+-tree implementation. https://github.com/myui/btree4j/ – myui Mar 27 '19 at 15:40
6

I've had to implement my own and open sourced the code.

Justin
  • 4,196
  • 4
  • 24
  • 48
  • Haven't tested it but the split method was what I was looking for with every insert and remove. With only 2 elements this will occur almost all the time. Question: Do you shuffle the top level element? Say you have data from 1 -5000 (5000 for the sake of this comment) and you had the first element as 300, wouldn't it make sense to have that as closer to 2500? – Mukus Feb 18 '13 at 15:55
  • btw.. +1 for your answer. – Mukus Feb 18 '13 at 15:55
  • @TejaswiRana I've tested with 5000 elements (1-5000) and the root ended up with the 2048 value. The default implementation is 2-3 tree but that was just for testing purposes. You can pass in the order (minKeySize) of the tree in the constructor. – Justin Feb 18 '13 at 16:13
1

You could try Electric's BTree (author page here).

Charles Goodwin
  • 6,402
  • 3
  • 34
  • 63