Splitting Root Nodes
What you'll learn: How B-trees increase their height by splitting the root node and promoting a key upward to form a new root.
The Unique Growth Pattern
In most trees, height increases by adding leaves at the bottom. B-trees are different—they grow upward by splitting the root when it overflows.
When you insert a key into a full root node (one that's already at maximum capacity), you can't just split it like an internal node and promote a key to the parent—there is no parent. This is the special case.
How Root Splitting Works
When the root node is full and needs to accommodate another key:
- Split the full root into two nodes, just like any node split
- Promote the middle key upward
- Create a brand new root containing only the promoted key
- Make the two split pieces children of this new root
This is the only way a B-tree grows taller. The entire tree gains one level of height, but remains perfectly balanced because the root split affects all paths equally.
Simple Example
Imagine a B-tree of order 3 (max 2 keys per node) with root containing [10, 20]. When you insert 15:
- Root is full, so you'd have
[10, 15, 20]to split - Middle key
15gets promoted - New root contains just
[15] - Left child:
[10], right child:[20] - Tree height increased from 1 to 2
Key Takeaway: B-trees grow in height exclusively through root splitting, where the middle key is promoted to a newly created root, making the tree grow upward while maintaining perfect balance across all paths.