I was searching on google for a b+ tree and the main operations INSERT, DELETE AND SEARCH

and found a couple algorithms. But i figured out that i'm too noob in java to properly implement the classes

and make the code work.

Would you help me to implement this b+ tree?

there is an example:

https://code.google.com/p/java-algorithms-implementation/source/browse/trunk/src/com/jwetherell/algorithms/data_structures/BTree.java?r=373

In this case, do i have to create the "node" and "btree" classes separately and a main class to instantiate them?

Or maybe i should just get a procedural code? lol

Any help would be apreciated. Thanks.

EDIT:

Strange. d2jsp wont't let me directly click on the link.

It'll display a broken link...

Just ctrl c ctrl v the link on your web navigator if you're having any problems to see the example i found. Thanks.

This post was edited by Kvera on Mar 3 2013 09:56am

if you're not comfortable with java, start writing pseudocode and we'll help you convert to java.

This post was edited by carteblanche on Mar 3 2013 11:32am

The pseudocode itself is too big and i'm afraid my english isn't good enough to translate it.

Can't someone just make this example i found to get working and show me how to do?

I can get another examples if needed, i just dont know how to make them run on my Java

IDE lol.

I found some procedural binary tree examples that i sucessfully run on Java, sadly, i can't find

a procedural B+ tree. :|

I'm using ECLIPSE by the way.

Thanks.

There is a simple pseudocode of my b+ tree.

Steps of operation INCLUDE:

To insert a record with search key K

Look for the leaf node where K should appear.

If the search key K is found add the record
in the file and create a block "Indirect" if it does not exist.

Add a record pointer (data) for the block indirect.

If the search key K is not found:

Add the record in the file.

Enter <K, P r> in the leaf node.

Note 1: This way all search keys in the leaf node
will be sorted.

Note 2: cases of overflow and underflow were not considered (way hard to my programing skills)

Steps of operation DELETE:

To delete a record with search key K

Look for the leaf node where K should appear.

Look for the pointer data, delete the register in the file.

Remove <K, P r> leaf node if there is no block
"Indirect" associated with this entry.

Note 1: again, cases of overflow and underflow were not considered.

Can you help me with the operation SELECT and overflow/underflow cases as well?

Thanks.

This post was edited by Kvera on Mar 6 2013 10:43pm

Doh, found this on wikipedia, much better than my silly pseudocode.

Search

The root of a B+ Tree represents the whole range of values in the tree, where every internal node a subinterval.
We are looking for a value k in the B+ Tree. Starting from the root, we are looking for the leaf which may contain the value k. At each node, we figure out which internal pointer we should follow. An internal B+ Tree node has at most d ≤ b children, where every one of them represents a different sub-interval. We select the corresponding node by searching on the key values of the node.
Function: search (k)
return tree_search (k, root);

Function: tree_search (k, node)
if node is a leaf then
return node;
switch k do
case k < k_0
return tree_search(k, p_0);
case k_i ≤ k < k_{i+1}
return tree_search(k, p_i);
case k_d ≤ k
return tree_search(k, p_d);
This pseudocode assumes that no duplicates are allowed.

Insertion
Perform a search to determine what bucket the new record should go into.
If the bucket is not full (at most b - 1 entries after the insertion), add the record.
Otherwise, split the bucket.
Allocate new leaf and move half the bucket's elements to the new bucket.
Insert the new leaf's smallest key and address into the parent.
If the parent is full, split it too.
Add the middle key to the parent node.
Repeat until a parent is found that need not split.
If the root splits, create a new root which has one key and two pointers.
B-trees grow at the root and not at the leaves.

Deletion
Start at root, find leaf L where entry belongs.
Remove the entry.
If L is at least half-full, done!
If L has fewer entries than it should,
Try to re-distribute, borrowing from sibling (adjacent node with same parent as L).
If re-distribution fails, merge L and sibling.
If merge occurred, must delete entry (pointing to L or sibling) from parent of L.
Merge could propagate to root, decreasing height.