B-Trees: Definition & Invariants

A B-tree is an m-way search tree with extra rules that force it to stay balanced — every leaf sits at exactly the same depth, no matter what order keys arrive in. It was designed by Bayer and McCreight (1972) for data stored on disk, where reading a node is expensive and we want the tree as short as possible.

Definition. A B-tree of minimum degree t (t ≥ 2) is a search tree in which:

1. Every node has at most 2t − 1 keys and at most 2t children.
2. Every node except the root has at least t − 1 keys and at least t children.
3. The root has at least 1 key (unless the tree is empty).
4. A node with k keys has exactly k + 1 children.
5. All leaves appear at the same level.

The parameter t is the minimum degree. Some textbooks instead use the order m = 2t (max children). Both describe the same structure — this course uses minimum degree t, following CLRS.

Two invariants do the real work:

1. The "half-full" rule (min keys ≥ t − 1). No node (except the root) is allowed to get too empty. This is what caps the tree's height — since every node carries a healthy load of keys, you can't have long chains of nearly-empty nodes.

2. Uniform leaf depth. Every path from root to leaf has the same length. This is the balance guarantee that a plain m-way tree lacks.

Together they mean a B-tree with n keys has height at most log_t((n + 1) / 2) — logarithmic and, critically, guaranteed regardless of insertion order. B-trees never degrade into a chain.

How is this maintained? B-trees grow at the root, not at the leaves. When a node overflows during insertion it splits, pushing one key up; when a node underflows during deletion it borrows or merges. These local repairs (next two topics) keep all invariants true after every operation.

Take minimum degree t = 3. Plug into the invariants:

So in a t = 3 B-tree, an ordinary node must hold between 2 and 5 keys and (if internal) point to between 3 and 6 children.

Why do these limits matter for balance?

• The lower bound (2 keys / 3 children) stops nodes from becoming sparse. If a node were allowed to shrink to a single key, the tree could grow tall and thin — defeating the point. Forcing every node at least half-full means each level multiplies the key count by at least ~t, so height stays ≈ log_t n.
• The upper bound (5 keys / 6 children) keeps nodes a fixed, bounded size — one node fits neatly in one fixed-size disk page, so a single read loads a whole node.

The gap between the bounds gives "slack": a node can absorb several inserts before splitting and several deletes before merging, so restructuring is rare (this is the amortized win we analyze later).

Here is a valid B-tree of minimum degree t = 2 (max 3 keys, min 1 key per non-root node). Notice every leaf is on the same bottom level.

Reading it top-down: the root key 17 separates everything ≤ 17 (left) from everything ≥ 17 (right). Inside node 5 | 9, the three children hold keys < 5, between 5 and 9, and > 9 respectively. Every leaf is exactly 2 levels below the root — the defining balance property.

Because every non-root node holds at least t − 1 keys, a B-tree of height h contains at least

Every core operation — search, insert, delete — walks a single root-to-leaf path, touching O(h) = O(log_t n) nodes and doing O(t) work inside each. So all three are O(t · log_t n) in comparisons.

The decisive metric for B-trees, though, is disk reads: one per node on the path, i.e. O(log_t n) page accesses — and we'll see that choosing a large t makes this a tiny number even for billions of keys.