B-Trees

Motivation and Definition

B-trees generalise binary search trees: each node can hold many keys and have many children. They are designed for disk-resident data where following a pointer costs ~2 million CPU cycles. By maximising the branching factor, B-trees minimise tree height and thus disk accesses.

A B-tree of minimum degree $t$ (with $t \ge 2$) satisfies:

1. Internal nodes hold at least $t-1$ keys (except the root, which may have as few as 1).
2. Internal nodes hold at most $2t-1$ keys.
3. A node with $m$ keys has exactly $m+1$ children.
4. All keyless leaves exist at the same depth (perfect height balance).
5. Keys partition the key ranges of children: for a node with keys $k_1, k_2, \ldots, k_m$, child $c_i$ contains keys between $k_{i-1}$ and $k_i$ (with appropriate adjustments at the ends).

Example: B-tree<2> (t=2). Internal nodes hold 1—3 keys and have 2—4 children. This is also known as a 2-3-4 tree (see next note).

Height Bound

The minimum number of keys at each level (starting from the root) is: 1, $2(t-1)$, $2t(t-1)$, $2t^2(t-1)$, and so on. Summing the geometric progression and rearranging:

$n \ge 1 + (t-1)\sum_{i=1}^{h} 2t^{i-1}$

From which: $h \le \log_t\left(\frac{n+1}{2}\right)$

Thus the height is $\Theta(\log_t n)$. Since $t$ can be large (e.g. 100), the tree is very shallow; search, insert, and delete all examine $\Theta(\log_t n)$ nodes.

Pointer Discipline

Only one pointer to a B-tree is permitted: the root pointer. Internal node pointers must not be stored externally, because restructuring operations (splits, merges) move keys between nodes. A stale pointer could reference a node that no longer contains the expected key.

Search

BT-Search descends from the root. At each internal node, scan the keys (or use binary search since $t$ is constant with respect to $n$) to find the first key $\ge$ the search key. If found, return the payload. If not found at a leaf level (where children are keyless leaves), return NIL. Cost: $O(t \cdot \log_t n) = O(\log n)$.

Insert

The naive approach: walk down to the bottom level of internal nodes, insert into the leaf node. If the node overflows (reaches $2t$ keys), split it around its median into two nodes of $t-1$ keys each, and promote the median to the parent. If the parent is full, splitting cascades upward. If the root splits, a new root is created: the tree grows taller at the top, preserving perfect height balance.

Improved insert: preemptively split any full node encountered on the way down. This guarantees the parent is never full when a split promotion arrives, avoiding upward cascading. It also avoids revisiting nodes already read from disk.

Delete

More complex. Key cases:

• If the key is in a leaf node and the node has $> t-1$ keys: simply remove it.
• If the key is in an internal node: swap with predecessor (or successor), which must be in a leaf; then delete from the leaf.
• If the leaf has only $t-1$ keys (minimum): either redistribute (borrow a key from a sibling via the parent), or merge with a sibling (combine $t-1 + t-1 + 1 = 2t-1$ keys into one node by “stealing” the separator from the parent). Merging may cascade upward if the parent becomes too small.
• If the root’s last key is merged away, the root is replaced by its merged child: the tree becomes shorter.

Summary

Property	Value
Min keys per node (non-root)	$t-1$
Max keys per node	$2t-1$
Children per node	$m+1$ (for $m$ keys)
Height	$\le \log_t((n+1)/2)$
Search	$O(\log n)$
Insert	$O(\log n)$, top-down splitting
Delete	$O(\log n)$, redistribute or merge
Key invariance	All leaves at same depth