B+ Tree Internals: Pages, Splits, Merges

Forget the picture of a tree of nodes. A B+ tree is a file of fixed-size pages; the "tree" is the pattern of page ids they store. Internal pages hold k separator keys and k+1 child page ids. Leaf pages hold entries (key → row locator) in key order plus the page id of the right sibling. The root is whichever page the metapage says it is.

Below is a complete tree with capacity 3 keys per page (real pages hold ~200; small capacities make splits visible). Read it the way the engine does: page ids, not arrows.

A lookup for 70 reads the root (page 9): 40 ≤ 70 < 80, so child 1 → page 7. Page 7: 60 ≤ 70, so child 1 → page 5. Page 5 is a leaf; binary search finds 70 at slot 1 → heap(7,4). Three index pages plus one heap page. Each page decision is a binary search over its keys — roughly 8 comparisons on a 200-key page — but comparisons are not what you wait for.

Height is what you wait for, and height is logarithmic with base = fanout. With 200 keys per page: 1 level for ≤ 200 entries, 2 for ≤ 40,000, 3 for ≤ 8 million, 4 for ≤ 1.6 billion. The root and the second level are a few hundred pages at most and stay in the buffer pool, so the typical lookup is one real read for the leaf and one for the heap row.

Insert 33: descend to page 2, which holds [20, 30, 35] — full. The page cannot take a fourth key, so it splits: the lower half stays, the upper half moves to a freshly allocated page, the sibling chain is relinked around the new page, and the first key of the new page is copied up into the parent as a separator. The parent (page 3) had one key and takes a second. Three pages written: the two leaves and the parent.

If the parent is also full, it splits too — but internal splits move the middle key up rather than copying it, because an internal key is only a guide and does not need to exist anywhere else. A split of the root allocates a new root with a single separator, and the tree grows one level. That is the only way height increases, and it is why all leaves are always at the same depth: growth happens at the top, never at the bottom.

Delete 15 from page 1 ([10, 15]): the page drops to 1 key, below the minimum of 2. The engine first tries to borrow: if a sibling under the same parent has more than the minimum, one entry moves across and the separator in the parent is updated to the new first key. Here page 2 holds exactly 2, so it cannot spare one. The alternative is merge: page 1 absorbs page 2, the separator 20 is dropped from page 3, page 2 is freed, and the sibling chain skips it.

The parent may now be under-full too, and the same rule applies one level up: borrow from a sibling through the parent (rotating a separator down and another up) or merge and pull the separator down. If the root loses its last separator, its only child becomes the root and the tree shrinks by one level. Many production engines never merge eagerly — PostgreSQL only deletes a leaf page once it is completely empty, during VACUUM — because half-empty pages are cheap and merges are not.

Separators do not have to be real keys. Deleting 40 from the leaf leaves the separator 40 in page 9 untouched: it still divides the key space correctly. This is why a B+ tree can carry keys in its internal pages that no longer exist in any leaf.

WHERE k BETWEEN 25 AND 70 does one descent — to the leaf that would contain 25 — and then never touches an internal page again. It emits entries from that leaf, follows next to the right sibling, and continues until it meets a key above 70. The cost is height plus the number of leaves the range spans, and those leaves are neighbours, so a large range reads pages in nearly sequential order.

This is the property that makes ORDER BY k, MIN(k), MAX(k), k > ? and LIKE 'abc%' index-friendly, and it is what a B-tree (values in internal nodes, no leaf chain) and a hash index both lack. ORDER BY k DESC needs a backward walk, which is why real leaves also carry a prev pointer.

A B-tree stores each key exactly once, with its value, wherever it happens to land — including in internal nodes. A B+ tree stores every key in a leaf and copies some of them into internal pages as separators. The duplication buys three things: internal pages hold only keys and page ids, so their fanout is maximal; every lookup ends at the same depth; and all entries are in one sorted, chained sequence, so ranges are a walk rather than an in-order traversal through internal nodes.

The cost is a few percent of extra key storage in the internal levels — which for a 200-key page is under 1% of the tree. No storage engine that targets disk or SSD uses the B-tree variant.

PostgreSQL's btree access method is a Lehman-Yao B+ tree. Every page — internal and leaf — carries a right-link to its right sibling and a high key, the upper bound of what the page may contain. A reader that descends into a page and finds its key above the high key knows a split happened underneath it and simply follows the right-link; no lock on the parent is needed while reading. Writers hold a short lock on the page being split and fix the parent afterwards.

Leaf entries are (key, TID) where TID = (heap block, offset): the index never contains the row. Since PostgreSQL 12, duplicate keys are ordered by TID and since 13 they are deduplicated into posting lists, which shrinks indexes on low-cardinality columns. Deleted entries are removed lazily: a leaf page is unlinked only when VACUUM finds it empty, so a churned index needs REINDEX or pg_repack to recover space. Page 0 is the metapage naming the root and the tree height; pageinspect shows all of it.

InnoDB tables are B+ trees keyed by the primary key — the clustered index — and the leaf pages contain the full rows, not locators. A primary-key lookup therefore ends at the leaf with the row in hand: height reads, no heap fetch. Pages are 16 KB by default, roughly doubling the fanout compared with 8 KB.

Secondary indexes are separate B+ trees whose leaf entries hold the secondary key plus the primary key rather than a physical locator. A secondary lookup is two descents — secondary tree, then clustered tree — and a wide primary key is paid for in every secondary index. Rows move when the clustered page splits, which is why the leaf cannot store a physical position. See InnoDB Internals: Clustered Index, Buffer Pool, Redo, Undo, Locks and Physical Layouts Compared: Heap + Secondary Index vs Clustered Index for the consequences.