B-Tree Node Occupancy, Splits, and the Minimum Degree

Every structure discussed so far bounds height by keeping the branching factor at two and constraining the shape. A B-tree inverts the strategy: the branching factor is large and fixed by the node’s byte size, so the height is small because the tree is wide. A node holds an array of keys and an array of child pointers, and a search within a node is a binary search over the key array. The balance invariant is that all leaves are at the same depth and that every non-root node stays at least half full.

The consequence is that the number of levels is tiny. A 4 KiB page holding a few hundred keys gives a tree of a billion entries on the order of five levels, and a lookup touches five pages instead of the thirty binary nodes that a balanced binary tree of the same size would visit. On storage where a page read costs orders of magnitude more than a comparison, that difference is the entire design.

Where the depth bound comes from

A B-tree of minimum degree t requires every node other than the root to hold between t − 1 and 2t − 1 keys, and every internal node to have between t and 2t children. The root holds at least one key. The upper bound 2t − 1 is the point at which a node is full and must be split.

The lower bound is what makes the height logarithmic. Every internal node below the root has at least t children, so a tree with h levels has at least 2t^(h−2) leaves, each holding at least t − 1 keys. Hence n ≥ 2(t − 1)t^(h−2), and inverting for large t gives h ≤ log_t((n + 1)/2) + 1. The base of the logarithm is t, not 2, and that is the whole point.

The upper bound on keys per node is what bounds the search cost within a node. A node with 2t − 1 keys takes ⌈log₂(2t − 1)⌉ comparisons to search by binary search, so the total lookup cost is O(log_t n · log t), which is O(log n) with a constant that depends on the node size. Choosing t too large makes the in-node search expensive; too small makes the tree deep. The optimum is where the node size matches the transfer unit of the underlying device, which is why on-disk B-trees use the page size and in-memory B-trees use the cache line multiple.

#define T 64                       /* minimum degree; node holds up to 2*T-1 keys */

typedef struct {
    int n;                         /* keys currently stored */
    int leaf;
    int key[2 * T - 1];
    struct bnode *child[2 * T];
} bnode;

/* Binary search within a node; returns the index of the first key >= target. */
int find_index(bnode *x, int target) {
    int lo = 0, hi = x->n;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (x->key[mid] < target) lo = mid + 1; else hi = mid;
    }
    return lo;
}

Note that the child array has one more slot than the key array, because n keys separate n + 1 children. That off-by-one is the most common source of buffer overruns in B-tree implementations, and the reason node sizes are usually stated as “2t − 1 keys and 2t children” rather than as a single count.

Splitting a full node

Insertion descends to a leaf and inserts the key there. If the leaf is full, it must be split first. The split takes the median key, promotes it to the parent, and divides the remaining 2t − 2 keys into two nodes of t − 1 each. Both halves satisfy the lower bound exactly, and the parent gains one key and one child.

The parent may now be full, so the split can propagate upward. In the worst case it reaches the root, which is the one node allowed to hold fewer than t − 1 keys. Splitting the root creates a new root with one key and two children, which is the only operation that increases the height of a B-tree. Since the height is bounded by log_t n, a split cascade is O(log_t n) in the worst case, and in practice it is rare: a node splits only when it is full, and after a split each half is half full, so the next split in that region requires at least t − 1 more insertions.

The standard implementation splits proactively on the way down rather than retroactively on the way up. Before descending into a child, if that child is full, split it. The consequence is that the descent never needs to return upward, so insertion is a single pass with no parent pointers and no recursion unwinding. It also guarantees that the node being split has a non-full parent, because the parent was checked on the previous step. The invariant maintained is “the node about to be entered is not full”, which is stronger than the B-tree invariant and makes the code simpler.

Deletion is the mirror and is genuinely harder. A node that drops below t − 1 keys must borrow from a sibling with spare keys or merge with a sibling. Borrowing rotates one key through the parent; merging pulls a key down from the parent and concatenates two nodes, which may leave the parent underfull and propagate the merge upward. The proactive strategy applies again: on the way down, ensure every child about to be entered has at least t keys, by borrowing or merging in advance, so the removal at the leaf never causes underflow.

Minimum degree as a tuning knob

The parameter t trades three quantities against each other, and the trade is not symmetric.

Larger t reduces height, which reduces the number of node accesses per lookup. It increases the cost of searching within a node, which grows as log t. It also increases the amount of data moved on a split: a split of a node with 2t − 1 keys copies t − 1 keys and t pointers to a new node. And it increases the minimum number of keys a node must hold, which raises the worst-case space overhead of a sparse tree — a tree with n keys has at most n/(t − 1) nodes, but the constant is not what matters; what matters is that a half-full node wastes half a page.

t	Max keys per node	Height for 10⁹ keys	Keys moved per split
2	3	~30	1
32	63	~7	31
64	127	~6	63
256	511	~5	255

t = 2 gives a 2-3-4 tree, the multiway structure that a red-black tree encodes, which is why the red-black height bound is about twice the B-tree height bound for the same key count. The comparison is developed in the 2-3-4 correspondence behind red-black colouring.

The split cost is why very large t is not free. A split moves half a node, and on a device with a fixed transfer unit that is one or two page writes. Amortized over the t − 1 insertions needed to fill the node again, the per-insertion cost of splits is O(1) regardless of t — the constant is roughly one key move per insertion, since each insertion contributes one key to the eventual split. What grows with t is the variance: a single split writes a whole page, which is a latency spike even if the average is low.

Why the leaves are linked

Most B-tree variants thread the leaves into a doubly linked list in key order. The list costs two pointers per leaf, which is negligible, and it turns a range scan from a tree traversal into a linear walk. Without it, enumerating k consecutive keys requires an in-order traversal that revisits internal nodes repeatedly, and the cost is O(k log n) rather than O(k + log n).

The linked leaves are also what makes a B-tree usable as a database index for ordered scans. The internal nodes hold separators, not data, so a scan that covers a key range descends once to the first leaf and then follows sibling pointers. The separators can be a prefix of the key rather than the whole key, which is why on-disk implementations store shortened separator keys and gain a larger branching factor for the same page size — a technique that matters enough to be its own design decision.

Failure modes specific to B-trees

Three problems recur in B-tree implementations and have no analogue in binary trees.

The first is key size. A node holds a fixed number of bytes, so variable-length keys mean a variable number of keys per node. Implementations either cap the key length, which breaks on long keys, or store keys indirectly through a slot array, which adds a level of indirection and complicates the in-node binary search. The slot-array layout is what most on-disk engines use, and it is why their node format documentation is longer than the algorithm description.

The second is concurrency. A split modifies a node, its parent, and a sibling, so a reader traversing concurrently can observe a torn state unless the modifications are ordered and published carefully. The common solution is to split bottom-up with latches held on the path, or to use a copy-on-write design where a modified node is written to a new location and the parent pointer is switched atomically. The latter avoids latches entirely on the read path but requires a free-space manager and garbage collection of old pages.

The third is that the height bound is a bound on node accesses, not on time. A four-level B-tree lookup is four page reads, and if those pages are not cached the cost is four device latencies. That is why buffer pool management dominates B-tree performance on disk, and why the algorithmic elegance of the structure says little about how fast it will answer a query in a system that has to fetch pages.