B+ Tree - Structure and Operations
Structure of B+ Tree
A B+ Tree is a balanced tree data structure used for databases and file systems. It stores
data only at the leaf nodes while internal nodes are used for navigation.
Properties:
- Each node can have a maximum of 'm' children.
- Internal nodes store keys; leaf nodes store actual data.
- Leaf nodes are linked together for faster range queries.
Diagram of a Simple B+ Tree (Order 4)
Internal Node:
+------+-----+------+
| 10 | 20 | 30 |
+---+--+---+-+---+--+
/ | | \
Leaf Nodes:
[1,5,8] [12,15,18] [22,25,28] [32,35]
Operations on B+ Tree
(a) Insertion:
- Find correct leaf, insert key in sorted order.
- If overflow, split the node and promote middle key.
(b) Deletion:
- Locate key, remove it.
- If underflow, borrow from sibling or merge nodes.
(c) Search:
- Traverse from root to appropriate leaf.
- Search linearly in the leaf node.
Example - Insertions
Order = 3 (max 2 keys per node)
Insert 10: [10]
Insert 20: [10, 20]
Insert 5: [5, 10, 20] -> Split into [5] and [10, 20], root [10]
Insert 6: [5,6] and [10,20]
Insert 12: [10,12,20] -> Split [10] and [12,20], root becomes [10,12]
Resulting Tree:
Root: [10,12]
/ \
[5,6] [10] [12,20]
Example - Deletion
Delete 6:
- Find 6 in [5,6]
- Remove 6 -> [5]
- No need to merge as [5] has minimum keys.
Advantages of B+ Tree
- Balanced and shallow structure.
- Fast search, insertion, deletion.
- Efficient range queries.
- Used in database indexing (e.g., MySQL, PostgreSQL).
Summary
B+ Tree is an efficient, balanced, multi-level index tree.
It supports fast search, insertion, deletion, and is highly useful in database systems.