Course contentsShow
← Computer Science
Lesson 558 of 2,87213. Balanced TreesFree lesson

B-Tree Invariants

Master the structural invariants that B-trees maintain: minimum degree, key ordering, and balanced height.

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-1 keys
  • Maximum keys: No node may exceed 2t-1 keys

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 the i-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.