★ 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.
★ Source Code
Source code can be found at here.
