B+ Tree implementation in Java

The most commonly implemented form of the B-Tree is the B+ Tree. The difference between them is that the internal nodes of B+ tree do not store records; they are used for navigation only.

★ Definition of B+ Tree
    A B+ Tree of order m has these properties:
    - The root is either a leaf or has at least two children;
    - Each internal node, except for the root, has between ⎡m/2⎤ and m children;
    - Internal nodes do not store record, only store key values to guild the search;
    - Each leaf node, has between ⎡m/2⎤ and m keys and values;
    - Leaf node store keys and records or pointers to records;
    - All leaves are at the same level in the tree, so the tree is always height balanced.

★ Algorithms

Search

• Do binary search on keys in current node. 
• When current node is a leaf node:
• If search key is found, then return record.
• If search key is not found, then report an unsuccessful search.
• When current node is an internal node:
• If search key < key_0, then repeat the search process on the first branch of current node.
• If search key >= key_last, then repeat the search process on the last branch of current node.
• Otherwise, find the first key_i >= key, and repeat the search process on the (i+1) branch of current node.

Insertion

• Perform a search to determine which leaf node the new key should go into.
• If the node is not full, insert the new key, done!
• Otherwise, split the leaf node.
• Allocate a new leaf node and move half keys to the new node.
• Insert the new leaf's smallest key into the parent node.
• If the parent is full, split it too, repeat the split process above until a parent is found that need not split.
• If the root splits, create a new root which has one key and two children.

Deletion

• Perform a search to determine which leaf node contains the key.
• Remove the key from the leaf node.
• If the leaf node is at least half-full, done!
• If the leaf node as L is less than half-full:
• Try to borrow a key from sibling node as S (adjacent node with same parent)
• If S is L's left sibling, then borrow S's last key, and replace their parent navigate key with this borrowed key value.
• If S is L's right sibling, then borrow S's first key, and replace their parent navigate key with S's second key value.
• If can not borrow a key from sibling node, then merge L and sibling S
• After merged L and S, delete their parent navigate key and proper child pointer.
• Repeat the borrow or merge operation on parent node, perhaps propagate to root node and decrease the height of the tree.

★ Implementation

★ Source Code
Source code can be found at here.