Page Splits and the Write Cost of a Single B-Tree Insert

An index insert that finds free space in a leaf page costs one page modification. An insert that finds none costs several, and the several are not the same several: some are unavoidable, some are an artifact of the layout, and some exist so that readers never block. The difference between the two cases is the difference between an index that grows at a predictable rate and one that exhibits periodic stalls under a monotonically increasing key.

The descent and the latch protocol

A B-tree lookup descends from the root, reading one page per level, until it reaches a leaf. With a fanout of a few hundred — typical for 8 KiB pages and keys in the tens of bytes — three or four levels address tens of millions of entries, so a descent touches three or four pages. Each of those pages must be pinned and latched; the latch is released before descending further, because the child pointer, once read, identifies a page whose contents do not change the fact that it is the child.

An insert follows the same path but must modify the leaf. The naive protocol takes an exclusive latch on the leaf, performs the insert, and releases. If the leaf is full, the insert must split it, which means modifying the parent to add a separator and a pointer — so the parent must be latched too. Taking the parent latch after the child latch, while another thread descends parent-then-child, is a lock-order inversion and a deadlock. Every real implementation therefore either acquires latches top-down with a restart if a child is not safe, or uses a protocol in which latches are released and reacquired in a fixed order.

The top-down crabbing protocol solves this by deciding, before descending, whether the child might split. If it might, the parent latch is held across the descent; if it will not, the parent latch is released and never reacquired. The cost is that a thread holds latches across more of the descent than strictly necessary; the benefit is that no split ever needs to acquire a latch upward, so deadlock is impossible. Lehman and Yao’s alternative gives every page a right-link and a high key, allowing a reader to descend without holding the parent latch at all and to recover from a concurrent split by following the link to the right.

/* Split boundary: leave fill_pct of the entry bytes on the left page. */
static size_t split_point(const leaf_t *l, unsigned fill_pct) {
    size_t total = 0, off = 0, best = 0;
    for (size_t i = 0; i < l->nkeys; i++)
        total += entry_size(l, i);
    size_t target = total * fill_pct / 100;
    for (size_t i = 0; i < l->nkeys; i++) {
        off += entry_size(l, i);
        if (off <= target)
            best = i + 1;            /* entries [0, best) stay left */
    }
    return best;
}

What a split writes

When the leaf has no room, the split divides its entries into two pages, allocates a new page, writes the upper half there, and inserts a separator key and a pointer into the parent. The writes are:

1. The new right sibling page, initialized and filled.
2. The original leaf, rewritten with only its lower half.
3. The parent page, with one additional key-pointer pair.
4. A log record for each of the three, plus the allocation of the new page in the extent map or free-space map.

That is three page writes where the non-splitting case had one, and each page write is a full block: a 8 KiB write for a change that added perhaps 40 bytes of key and pointer to the parent. If the parent is also full, the split propagates, and each level adds another two page writes. The propagation terminates at the root, which splits by allocating a new root and increasing the tree height — the only operation that changes the number of levels, and the reason a B-tree grows from the top rather than the bottom.

The propagation is not rare in the pathological case. Inserting keys in ascending order fills every leaf from the left, so every leaf split occurs at the rightmost position and every split propagates up the rightmost spine. For a tree of height h, that means h page writes per split rather than one. The classic remedy is to split the leaf unevenly when the insert is at the right edge — leave the left page full and put only the new entry on the right — so that subsequent ascending inserts find room in the new rightmost leaf. This is what B+tree implementations with an append-only or increasing-key workload do, and it converts a repeated spine split into a sequence of leaf-only splits.

Fill factor and the space-time trade

A split leaves both resulting pages roughly half full. That is the correct choice for random inserts: it leaves room on both sides so that subsequent inserts in either direction are absorbed without further splits. It is the wrong choice for a tree that will only ever be read, where a densely packed leaf maximizes entries per page and minimizes both the tree height and the bytes read per scan.

The knob that exposes the trade is the fill factor: the fraction of each page the build process fills, leaving the remainder as reserved space for future inserts. A fill factor of 100 produces the smallest possible tree and guarantees that the next insert in the middle of any page splits it. A fill factor of 70 leaves 30 percent of every page free, which absorbs inserts at the cost of roughly 40 percent more pages and a correspondingly taller tree. The parameter is a statement about the expected future write pattern, and choosing it from the current size of the table rather than from the insert pattern is a common way to get both costs.

There is a second-order effect that makes low fill factors expensive beyond their page count. Every page in the tree is read on every descent that reaches it, and a tree with more pages has more levels. Going from three to four levels adds one page read to every lookup that reaches a leaf — a 33 percent increase in the I/O per lookup, against a saving on splits that only materializes if the inserts actually land in the reserved space.

Right-links, high keys, and the cost of concurrent splits

A split is visible to readers mid-operation. The new right sibling exists, the parent does not yet point at it, and a reader descending through the parent will not find it. Lehman and Yao’s protocol handles this by making the split a sequence of atomic steps with a defined intermediate state: the new page’s right-link points to the old page’s former right neighbour, the old page’s right-link is set to the new page, and only then is the parent updated. A reader that reaches a page and finds its high key less than the search key follows the right-link and tries again. The parent update becomes a background repair rather than a correctness requirement.

The cost is a right-link and a high key in every page header — a few dozen bytes per page, and a comparison on every descent that may need to follow a link. In exchange, readers never take a latch that a splitter holds, so a read-only workload is unaffected by concurrent inserts. Engines that use a single-page-latch-per-level scheme instead accept brief reader blocking in exchange for a simpler page format.

Deletion, merging, and why merges are rarer than splits

The symmetric operation, merging two underfull siblings, is specified in every textbook and implemented in few production engines. The reason is that merging requires holding latches on both siblings and the parent, which reintroduces the lock-order problem, and that a merge followed by a re-insert of the same key produces a split again — thrashing. PostgreSQL’s B-tree does not merge pages on delete; it marks space free and lets a later pass reclaim it, and it defers the structural work to a separate maintenance operation. The result is a tree that can carry permanently underfull pages after a large delete, which is a space cost paid to avoid a concurrency cost.

The amplification arithmetic

For a random insert into a tree of height h with pages half full, the expected number of page writes per insert is one plus the probability that the leaf splits times the cost of the split, and the parent split probability is that probability divided by the parent’s fanout, recursively. The geometric series converges quickly: with a leaf split probability of one in a few hundred inserts, the expected total is close to one page write per insert, with occasional bursts of h writes. The bursts are what matter for latency, because they arrive as a synchronous multi-page write while a writer holds latches.

The accounting is only complete when the log is included. Each of those page writes is preceded by a log record, so the bytes written per logical insert are roughly twice the page bytes plus the log bytes — and if the page write is protected by a doublewrite buffer, three times. The full chain from a one-row INSERT to the bytes the device sees is traced in write amplification across the storage stack, and the alternative that avoids in-place page modification altogether is LSM compaction strategies. The page itself, and the directory entry that makes the insert O(1) once space is known, is described in slotted page layout.