Node Splits, Merges, and What the Fill Factor Buys

An insert into a B-tree eventually arrives at a leaf page with no room, and something must give. The mechanics of that moment determine the shape of the tree over its lifetime, the write amplification of the index, and the space it occupies relative to the data it indexes. The two decisions that matter are where the page divides and whether pages are ever joined back together.

The split, in the smallest case

A leaf page holds $m$ entries and is full. A new entry arrives. The implementation allocates a fresh page, moves roughly half the entries (including the new one, in order) to it, and writes a separator into the parent that routes to the new page. If the parent is also full, the split recurses upward, and if the root splits, a new root is created one level higher. That last case is the only way a B-tree grows in height, and it happens at most once per level of the tree over the tree’s lifetime for monotonic inserts.

The number of pages written by one insert that triggers a split at the leaf and at every level up to the root is the height plus one, and the number of pages dirtied is the same. A split at the leaf alone dirties two leaves and one parent. This is why a B-tree’s write cost is not uniform across inserts: most inserts write one page, and a small fraction write a handful, and the fraction is roughly one in the number of entries a page can absorb between splits.

The split point is the first real design choice. A half split leaves both halves at 50 percent occupancy, which is the minimum for a node with $m/2$ entries and satisfies the B-tree invariant while maximizing the number of future inserts each half can accept before splitting again. A split that leaves the left page full and the new page with one entry — a right-edge split — is what monotonic inserts produce naturally, and it keeps the tree dense but concentrates all future inserts on the new page, which is fine when the inserts are genuinely increasing and terrible when they are not.

Why random insertion leaves pages about 70 percent full

The occupancy of a B-tree built by inserting keys in random order has a known expected value of about $\ln 2 \approx 0.693$ of capacity, a result that follows from modelling each page’s fill as a random walk between the split thresholds. The intuition: a page splits when it hits full, so pages that are near full are the ones that just received inserts, and after a split each half is half full and then accumulates inserts until it splits again. Averaged over the steady state, the page sits about two-thirds full.

The practical consequence is that the storage cost of a randomly built index is roughly 1.44 times the raw entry bytes, and the effective fanout is about 0.69 of the theoretical maximum. An index built by bulk loading in sorted order is denser, because the loader can pack every page full except the last and construct the internal levels directly, reaching near 100 percent occupancy at the leaves. This is why a rebuilt index is smaller than the same index after a year of random inserts, and why a bulk load followed by an incremental maintenance phase produces a different physical structure than incremental insertion throughout.

There is a subtlety about what “random” means. Random keys are the worst case for occupancy but not the worst case for locality. Keys inserted in a shuffled order across a narrow range cause splits everywhere at once; keys inserted in a random permutation over a wide range behave like the independent-random model. Keys inserted with a slowly drifting distribution — a timestamp with jitter, an identifier from a sequence with occasional backfill — behave like monotonic inserts for most pages and random inserts for a few, which is a better outcome than either pure case.

The fill factor setting, and what it does not do

Most engines expose a per-index fill factor: a percentage of page capacity at which a page is considered full and will be split. Setting it to 70 means the page splits when it reaches 70 percent, leaving each half at 35 percent, so subsequent inserts in the neighbourhood do not split again for a while. Setting it to 100 means the page splits when physically full, leaving halves at 50 percent.

The setting affects only the moment of splitting; it does not reserve space in a page that is never split, and it does not prevent a page from reaching 100 percent through updates that enlarge entries in place. Its purpose is to leave headroom for inserts that will land in the same neighbourhood, which is useful for indexes on keys that arrive in bursts within a narrow range: a page that is already 70 percent full can absorb a burst without a split, and a split during a burst is more expensive because the parent may split too, and because the freshly split pages are immediately half-filled and the burst continues into them.

The cost is space and height. A fill factor of 70 means the page splits at 70 percent capacity, so each half emerges at about 35 percent and the steady-state average sits near halfway between that and the threshold, around 52 percent. That is less dense than the roughly 69 percent of a page that splits when physically full, so a lower fill factor makes the index larger, not smaller: the same entries occupy more pages, the fanout per level falls, and the height may rise by one. The setting is a bet that the headroom saves more in avoided splits than it costs in space, and for a burst of inserts into a narrow key range the bet is often right.

A fill factor at or below 50 is only meaningful for indexes whose keys increase monotonically. There the rightmost page splits repeatedly, and a threshold of 50 or below keeps the left half of each split near-full while the right half starts empty and receives the next inserts, which is the densest possible outcome for that workload. Applied to a non-monotonic key the same setting produces pages that are perpetually sparse, and implementations that enforce a minimum occupancy of half a page will simply split earlier than the setting requests.

Merges are usually not performed

The B-tree definition is symmetric: a node that falls below half full should be merged with a sibling, and the parent’s separator adjusted or removed. Many implementations do not do this on delete.

Merging is expensive relative to what it saves. To merge a leaf, the engine must find a sibling, which requires the parent page, take a latch on it, move the entries, remove the separator, and then possibly recurse upward if the parent drops below half full. All of this happens under concurrency, and the sibling may be the target of a concurrent scan that holds a latch on it. The work per deleted entry is far larger than the work per inserted entry, and the space saved is one page, which the allocator could reuse elsewhere anyway.

So the common behaviour is that deletes leave pages sparse and pages are reclaimed only when they become completely empty, at which point the page can be unlinked from the leaf chain and its separator removed from the parent without moving any entries. Some engines run a background process that rebuilds or rebalances an index when its occupancy drops below a threshold, which converts the per-delete cost into a periodic batch and, crucially, runs where concurrency is controlled. This is the same shape of solution as the space reclamation problem in copy-on-write filesystems: defer the expensive structural work to a pass that can be scheduled.

The consequence for an index that sees a large delete followed by no inserts is that its physical size does not shrink, and its height does not fall even though it now holds a tenth of the rows. A rebuild is required to recover the space, and a rebuild of a large index is a full scan of the table plus a full write of the index, so it is a maintenance operation rather than something the engine can do cheaply in the background.

Right-edge splits and the contention they create

Monotonic inserts — a sequence-generated primary key, a timestamp, an append-only log — always split the rightmost leaf. That is the good case for space: the left half of the split stays full and is never touched again, so occupancy approaches 100 percent and the tree is as dense as the format allows.

It is the bad case for concurrency. Every inserting transaction wants the same page, so the page latch becomes a serialization point, and the parent page that receives the separator is also hot. The usual mitigation is to make the insertion path take latches in a way that does not block readers, so that scans proceed while the rightmost page splits, which is the mechanism described in concurrent descent and page latching. A second mitigation is to batch the split: rather than splitting a full page in half, the engine splits it into a full left page and a partly filled right page, or splits several pages at once when it detects a run of right-edge inserts. Splitting off a mostly-empty right page means the next split comes sooner in terms of rows but the split itself moves fewer entries.

The mirror-image case is a descending key, which splits the leftmost leaf every time. Implementations that special-case only the right edge will perform poorly on descending sequences, and the fix is symmetry rather than a special case.

What the split policy cannot fix

No split policy prevents an index from becoming sparse after mass deletion, and none prevents the height from growing when keys widen. Both are properties of the key and the workload, not of the split rule. The remaining lever is the page size, which trades the cost of a split — a larger page moves more bytes and holds a latch longer — against the frequency of splits and the height of the tree. Larger pages mean fewer levels and fewer splits per row, and a longer time to write one page and a larger unit of write amplification. That trade, and its interaction with compression, is where index page formats diverge most, and it is taken up in prefix compression in index pages.