Question

Implement a B+ tree with explanation in java

Answer 1

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 eaves 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 a 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.