Past exam question: 2077 Chaitra (Regular), Q10(a)
Open in the Padhaiko appQuestion
Explain balancing of B-tree with example.
Solution
How a B-Tree Maintains Perfect Balance: Unlike BSTs or AVL trees that balance via local rotations, a B-Tree of order stays perfectly height-balanced (all leaves at the exact same level) by allowing nodes to hold between and keys and growing upward from the root via node splitting:
- Every new key is inserted into a sorted leaf node.
- If the leaf remains within keys, no structural change occurs.
- If the leaf overflows ( keys), it splits at its median key into two half-full nodes and promotes the median key into its parent.
- If the parent overflows, splitting propagates upward; when the root splits, a new root with 1 key is created, increasing tree height uniformly across all paths.
Example (Order , Max 2 Keys per Node): Insert 10, 20, 30:
- Insert
10, 20: leaf[10, 20](valid, max 2 keys). - Insert
30:[10, 20, 30]overflows (3 keys)! Split around median20:
[20]
/ \
[10] [30]
Both leaves [10] and [30] remain at depth 1.
Answer:
A B-Tree stays balanced (all leaves at identical depth) through node splitting and upward median promotion: whenever an insertion causes a node to reach keys, its median key moves up to the parent and the remaining keys split evenly into two valid sibling nodes.