B+ Tree, in depth: copy-up versus push-up splits, the leaf chain, fanout arithmetic, bulk loading and concurrent access

Shape and invariants

Fix a maximum of M keys per node. A B+ tree keeps these invariants.

1. Every leaf is at the same depth.
2. Every key in the tree appears in exactly one leaf, in sorted order, with its value or a pointer to it.
3. Leaves are linked, each holding a pointer to its right neighbour, and often its left one too.
4. An internal node with k separator keys has k + 1 children. All keys in child i are less than separator i, and all keys in child i + 1 are greater than or equal to it.
5. Every node except the root holds at least about M / 2 keys.

Separators are copies of leaf keys, or any value that splits the ranges correctly. That detail matters for deletion: if key 30 is deleted from its leaf, the separator 30 in the root can stay, because it still routes every search to the right place.

Why fanout is everything

The reason databases use B+ trees is page arithmetic. A node is one disk page. InnoDB uses 16 KB pages by default and PostgreSQL uses 8 KB pages. Take a 16 KB internal page holding 8-byte integer keys and 6-byte child pointers: about 14 bytes per entry, so roughly 1,000 entries per page after headers. That is an estimate; real engines add per-record overhead, but the order of magnitude holds.

Leaves hold rows or row pointers, so they hold fewer entries. Say 150 rows of about 100 bytes each per 16 KB leaf. A tree of height 3 then reaches 1,000 × 1,000 leaves × 150 rows, about 150 million rows. The root and the second level together are about 1,001 pages, or 16 MB, which stays in the buffer pool. A point lookup costs two memory hits and usually one disk read.

Compare a plain B-tree storing values in internal nodes. With 100-byte values next to each key, an internal page holds about 150 entries instead of 1,000, so the tree needs an extra level for the same data, and the cached upper levels are far larger. Keeping values out of internal nodes is the whole trick. It is also why wide index keys hurt: a 200-byte key cuts internal fanout to around 75.

Search, range scans and a tested implementation

Search descends from the root, at each internal node choosing the child whose range contains the key, and finishes with a binary search inside one leaf. A range scan does the same descent for the lower bound and then walks the leaf chain until it passes the upper bound, so its cost is the tree height plus the number of leaves touched. The implementation below keeps nodes as Python lists so the logic is easy to follow; a real engine stores them in fixed-size pages.

from bisect import bisect_left, bisect_right


class Leaf:
    def __init__(self):
        self.keys, self.vals, self.next = [], [], None


class Inner:
    def __init__(self, keys, kids):
        self.keys, self.kids = keys, kids    # len(kids) == len(keys) + 1


class BPlusTree:
    def __init__(self, max_keys=4):
        self.max = max_keys
        self.root = Leaf()

    def _find_leaf(self, key):
        node, path = self.root, []
        while isinstance(node, Inner):
            i = bisect_right(node.keys, key)    # equal keys route right
            path.append((node, i))
            node = node.kids[i]
        return node, path

    def get(self, key):
        leaf, _ = self._find_leaf(key)
        i = bisect_left(leaf.keys, key)
        if i < len(leaf.keys) and leaf.keys[i] == key:
            return leaf.vals[i]
        return None

    def range(self, lo, hi):
        """Yield (key, value) for lo <= key < hi."""
        leaf, _ = self._find_leaf(lo)
        i = bisect_left(leaf.keys, lo)
        while leaf is not None:
            for j in range(i, len(leaf.keys)):
                if leaf.keys[j] >= hi:
                    return
                yield leaf.keys[j], leaf.vals[j]
            leaf, i = leaf.next, 0

    def insert(self, key, val):
        leaf, path = self._find_leaf(key)
        i = bisect_left(leaf.keys, key)
        if i < len(leaf.keys) and leaf.keys[i] == key:
            leaf.vals[i] = val                   # upsert
            return
        leaf.keys.insert(i, key)
        leaf.vals.insert(i, val)
        if len(leaf.keys) <= self.max:
            return
        mid = len(leaf.keys) // 2
        right = Leaf()
        right.keys, right.vals = leaf.keys[mid:], leaf.vals[mid:]
        leaf.keys, leaf.vals = leaf.keys[:mid], leaf.vals[:mid]
        right.next, leaf.next = leaf.next, right
        self._insert_up(path, right.keys[0], right)   # COPY up

    def _insert_up(self, path, sep, right):
        while path:
            node, i = path.pop()
            node.keys.insert(i, sep)
            node.kids.insert(i + 1, right)
            if len(node.keys) <= self.max:
                return
            mid = len(node.keys) // 2
            sep = node.keys[mid]                  # PUSH up: leaves this level
            right = Inner(node.keys[mid + 1:], node.kids[mid + 1:])
            node.keys, node.kids = node.keys[:mid], node.kids[:mid + 1]
        self.root = Inner([sep], [self.root, right])  # height grows at the top

A quick property test catches most mistakes, including the separator bug discussed next:

import random
t = BPlusTree(max_keys=4)
keys = list(range(1000))
random.shuffle(keys)
for k in keys:
    t.insert(k, str(k))
assert all(t.get(k) == str(k) for k in range(1000))
assert [k for k, _ in t.range(100, 110)] == list(range(100, 110))

Splits: copy up at leaves, push up inside

The difference between the two split functions is the most common bug in hand-written B+ trees.

When a leaf overflows, it splits into two leaves and the first key of the right leaf is copied up as the separator. The key must stay in the leaf, because leaves are where data lives and where range scans read. When an internal node overflows, its middle key is pushed up and removed from both halves. Keeping it in the right half would leave an internal node with as many keys as children, which breaks the k + 1 rule and misroutes searches.

Walk through it with M = 3, so a node splits when it reaches 4 keys. Insert 10, 20, 30: one leaf holds all three. Insert 40: the leaf holds 10, 20, 30, 40, splits into [10 20] and [30 40], and 30 is copied into a new root [30]. Insert 50 and 60: the right leaf becomes [30 40 50 60], splits into [30 40] and [50 60], and 50 is copied up, so the root becomes [30 50]. Keep inserting 70 to 100 and the root eventually holds 30, 50, 70, 90. Its overflow splits it into [30 50] and [90], and 70 is pushed into a new root, which no longer appears in either internal child. The tree grows only at the root, which is why every leaf stays at the same depth.

Note also the split point. Splitting evenly suits random inserts. For keys that always arrive in increasing order, an even split leaves every left page half empty forever. Engines detect rightmost-append patterns and split unevenly, leaving the left page nearly full.

Deletion: redistribute, merge, or leave it

Deletion removes the key from its leaf. If the leaf still meets the minimum occupancy, you are done, and the parent's separators can stay even if one of them equals the deleted key. If the leaf underflows, there are two repairs. Redistribute: borrow an entry from a sibling with spare keys and update the separator between them in the parent to the new first key of the right sibling. Merge: if neither sibling can spare a key, combine the leaf with a sibling, fix the leaf chain, and remove one separator and one child pointer from the parent. That can underflow the parent, and the same repair runs one level up, possibly shrinking the root.

Real engines are lazier than the textbook. PostgreSQL's B-tree does not merge partly filled pages; it removes a page only when it is completely empty, and leaves space reuse to later inserts. InnoDB tries to merge a page with a neighbour when its fill falls below a configurable MERGE_THRESHOLD, which defaults to 50 percent. Both accept some wasted space to avoid structural changes on every delete, which would cost latches and write amplification.

Bulk loading and fill factor

Building a large index one insert at a time causes a split every few inserts and leaves pages half full. Bulk loading does better: sort the entries, fill leaves left to right to a target fill factor, link them, then build each parent level from the first key of each child, repeating until one node remains. After the sort, it is a single linear pass and produces compact, physically sequential leaves.

The fill factor is a trade-off. PostgreSQL B-tree indexes default to 90 percent full leaves. Fully packed pages are ideal for a read-only table, but the first insert into each page causes a split, so tables with random inserts benefit from leaving some room.

Concurrent access

Concurrent access needs short-term locks, called latches, on pages. The classic protocol is latch crabbing: latch the child, then release the parent if the child is safe, meaning an insert cannot split it or a delete cannot merge it. Most descents release every ancestor almost at once. An optimistic variant takes shared latches all the way down, exclusively latches only the leaf, and restarts with exclusive latches in the rare case that the leaf must split.

The B-link tree of Lehman and Yao adds a right-link and a high key to every node, including internal ones. A reader that arrives at a node just after it split sees that its key is above the node's high key and follows the right-link, so readers never wait for a split to finish propagating. PostgreSQL's B-tree implementation is based on this design.

How real engines use the leaves

How the leaves are used differs between engines, and it changes how you design keys.

• InnoDB stores each table as a clustered B+ tree on the primary key: leaves hold the whole row. Secondary index leaves hold the primary key, so a secondary lookup is two descents, and a wide primary key makes every secondary index bigger.
• PostgreSQL stores rows in an unordered heap. B-tree index leaves hold the key and a tuple identifier pointing into the heap.
• SQLite uses B+ tree-style table b-trees that keep data only in leaves, keyed by rowid, and separate index b-trees that store keys only.

Those choices explain a classic failure: random UUIDv4 primary keys in InnoDB. Each insert lands on a random leaf, so the working set is the whole index, pages split everywhere, and leaves end up about two thirds full. Time-ordered keys, such as UUIDv7, append at the right edge instead. The opposite failure is a monotonic key under very high concurrency, where every writer contends for the same rightmost leaf latch. For write-heavy workloads where neither works well, an LSM tree trades read cost for sequential writes; see LSM trees vs B-trees and LSM tree.

Trade-offs

A B+ tree gives O(log n) point lookups with a very large logarithm base, ordered range scans, and in-place updates. It costs random writes and page splits on insert, and some unused space in every page. A hash index answers point lookups in one probe but cannot do ranges. An in-memory ordered map such as a skip list is simpler to make concurrent but has no notion of pages and does poorly on disk. If your data is on a block device and you need order, the B+ tree is still the default answer.

What to do next

1. Run the implementation above with a property test, then add delete with redistribute and merge.
2. Print the height and leaf count after inserting a million keys with different max_keys values.
3. In PostgreSQL, inspect an index with the pageinspect extension and compare its leaf fill to your fill factor.
4. Check your primary keys: replace random UUIDv4 keys on large InnoDB tables with time-ordered ones.
5. Measure index size against key width and remove wide columns from indexes that do not need them.
6. Read about B-link trees and trace what a reader does when it lands on a node mid-split.