B-Tree Invariants
What you'll learn: The three fundamental rules that every B-tree must maintain to guarantee balanced, efficient operations.
Now that you understand B-tree structure, let's explore the invariants—the non-negotiable rules that make B-trees work. These properties must hold true at all times, after every insertion and deletion.
The Three Core Invariants
1. Minimum Degree (t)
Every B-tree has a minimum degree t ≥ 2:
- Root exception: The root may have as few as 1 key (unless it's the only node)
- All other nodes: Must contain at least
t-1keys - Maximum keys: No node may exceed
2t-1keys
Think of t as the "occupancy rule" for a parking garage—most levels must be at least half-full, but never overflow.
2. Key Ordering
Within each node:
- Keys are stored in sorted order (left to right)
- For any key at position
i, all keys in thei-th child subtree are smaller - All keys in the
(i+1)-th child subtree are larger
This extends the BST property across multiple keys per node, enabling binary search within nodes.
3. Balanced Height
All leaf nodes must be at the same depth. Unlike BSTs where balance is approximate, B-trees maintain perfect height balance—every path from root to leaf has identical length.
This is why B-trees guarantee logarithmic performance: no path can be longer than any other.
Why These Matter
These invariants work together: the minimum degree prevents sparse nodes, ordering enables efficient search, and balanced height guarantees predictable performance regardless of insertion order.
Key Takeaway: B-tree invariants—minimum degree constraints, sorted key ordering, and uniform leaf depth—ensure the tree remains balanced and efficient through all operations.