Node Splitting During Insertion
You'll learn how B-trees handle full nodes by splitting them in half and promoting the median key upward to keep the tree balanced.
Why Split Nodes?
In a B-tree, each node has a maximum capacity for keys (determined by the tree's order). When you try to insert a key into an already-full node, you can't just keep adding—the node would violate the B-tree invariants. Instead, you split the node into two smaller nodes and push the middle key up to the parent.
The Splitting Process
Think of it like overfilling a bookshelf. When one shelf has too many books, you:
- Take the middle book
- Split the remaining books between two shelves
- Use the middle book's title as a divider label on the shelf above
In B-tree terms:
- Identify the median key in the full node
- Create two new nodes: left gets keys smaller than median, right gets keys greater
- Promote the median up to the parent node
- Update pointers so the parent links to both new child nodes
Example
Imagine a node that can hold maximum 3 keys is full: [10, 20, 30]
When you need to insert 25:
- The node becomes temporarily
[10, 20, 25, 30] - Median is
20(or25, depending on convention) - Split into: Left
[10], promote20, Right[25, 30] - The parent node receives
20as a new key pointing to both children
If the parent is also full, the split cascades upward—possibly creating a new root, which is how B-trees grow taller.
Key Takeaway: Node splitting divides a full node at its median, promoting the middle key upward to maintain B-tree balance and invariants during insertion.