B+tree invariants, search, insertion, and splits

Where this sits on the journey

Our running query is SELECT name FROM emp WHERE salary > 75000 ORDER BY name. By the time control reaches this layer the optimizer (week 11) has already decided whether to scan the whole heap or to use an index on salary, and the executor (week 9) is pulling tuples through an access method. If the chosen path is an index scan, this layer is what the access method runs. It takes a key or a key range and hands back row ids (TIDs), which it gets by descending a B+tree.

What the layer above hands in: a SARG, the searchable predicate salary > 75000, plus a request for matching rows in key order. What this layer hands down: requests for specific index pages by page id, served by the buffer pool (week 5), which in turn reads them off disk through the storage layer (week 2). The B+tree's whole low-I/O argument leans on that buffer pool keeping the top levels resident, so this lesson sits directly on top of the one before it. Next week (week 7) closes the structure: deletion, bulk loading, composite keys, and the hash alternative.

Why a wide tree and not a binary tree

An index earns its keep by turning an O(N) heap scan into something sublinear. So the obvious move is a balanced binary search tree: an AVL or red-black tree gives O(log₂ N) comparisons, which is about 30 steps for a billion keys. That sounds fine until you remember where the data lives.

The four invariants

A B+tree of order m keeps four properties true at all times. They are not decoration; each one is the reason a guarantee holds. [Comer 1979, CMU 15-445 L08]

1. All data lives in the leaves. Internal nodes hold only separator keys and child pointers. They route a search; they never store a record or a row pointer. This is the one line that separates a B+tree from a plain B-tree, and it is why a separator can be copied rather than moved on a leaf split.
2. Leaves are linked in key order. Once a search lands on the lower bound of a range, it walks leaf to leaf sideways without climbing back up. PostgreSQL keeps the leaf chain doubly linked so scans run in either direction.
3. The tree is height-balanced. Every root-to-leaf path has the same length. Balance is a structural invariant maintained by splits and merges, not a periodic rebuild, so the worst-case lookup equals the average-case lookup.
4. Every non-root node is at least half full. For order m a non-root node holds between ceil(m/2) - 1 and m - 1 keys. This minimum occupancy is what bounds the height: it forces N keys into at most about log_m/2 N levels, so the logarithmic I/O bound holds in the worst case, not only on average. The root is exempt and may hold a single key.

Search: follow Ki < v <= Ki+1

Searching is a descent. At each internal node you binary-search the separators to find the one child whose key range contains your target, then follow that pointer down. The exact rule between adjacent separators K_i and K_i+1 is that a search value v takes the child between them when K_i < v <= K_i+1. PostgreSQL states this inequality verbatim in its nbtree README. [nbtree README] You repeat until you hit a leaf, binary-search the leaf, and you are done. One page read per level, so O(log_m N) I/Os. A range scan does this descent once to land on the lower bound, then rides the leaf links rightward until it passes the upper bound. That is exactly how salary > 75000 gets served: descend to the first leaf at or above 75000, then walk leaves.

Insertion: fit, or split

Insertion starts as a search: descend to the leaf where the key belongs. Then one of two things happens.

1. If the leaf has room, write the entry in sorted position and stop. No structural change. Most inserts end here, which is why inserts are cheap on average.
2. If the leaf is full, split it. Allocate a new leaf, move the upper half of the entries into it, link it into the leaf chain, and copy up the first key of the new right leaf as a separator into the parent. The word is copy: the key still exists down in the leaf, because all data must stay in leaves.
3. That copied-up separator may overflow the parent internal node. Split the parent too, but here you push up the middle key (move it, do not copy it) into the grandparent, because an internal node only routes and need not keep a copy.
4. Splits propagate up only as far as overflow continues. The moment a node has room for the incoming separator, propagation stops. If the root itself splits, a new root is allocated with the two halves as children. That is the only way the tree grows taller, and it grows from the top, which is precisely why every leaf stays at the same depth.

Build a B+tree by hand

Set a small order, then insert keys and watch the structure react. Use the worked sequence button to replay a deterministic run that forces a leaf split, then an internal split, then a new root. The half-full boundary is drawn on every node, the height and I/O counters tick per operation, and a split is announced as copy-up or push-up so you can see the difference rather than take it on faith.

Experiment: with m = 4, insert 10, 20, 30, then 40. The fourth key overflows the single leaf and splits it. Keep inserting and find the key that splits the root, the only moment the height counter goes up.

Insertion in pseudocode

# Insert key k. Descend, then fit or split. Splits bubble up only on overflow.
def insert(tree, k):
    leaf, path = descend_to_leaf(tree.root, k)   # Ki < v <= Ki+1 at each level
    leaf.put_sorted(k)
    if len(leaf.keys) <= MAX_KEYS:
        return                                   # common case: no structural change
    right = leaf.split_upper_half()              # link right into leaf chain
    sep   = right.keys[0]                       # COPY UP: key stays in the leaf too
    promote(path, leaf, sep, right)

def promote(path, left, sep, right):
    if path.is_empty():                          # left was the root
        tree.root = Internal(keys=[sep], kids=[left, right])   # only place height grows
        return
    parent = path.pop()
    parent.insert(sep, right)
    if len(parent.keys) <= MAX_KEYS:
        return
    up, rnode = parent.split_middle()            # PUSH UP: middle key removed from children
    promote(path, parent, up, rnode)

Check yourself