B-tree Indexes, in depth: page layout, fan-out arithmetic, search and split paths, concurrency and keeping indexes healthy

Why a tree of pages

A binary search tree over a hundred million keys is about 27 levels deep. If each level is a separate random read from storage, a lookup costs 27 I/Os, which is unusable. A B-tree fixes this by making each node a whole page, typically 8 KiB in PostgreSQL and 16 KiB by default in InnoDB, and packing hundreds of keys into it. One page read then chooses among hundreds of children rather than two, and the tree's height becomes the logarithm of the row count to the base of the fan-out.

Databases use the B+tree variant: internal pages hold only separator keys and child pointers, and every entry lives in a leaf. Internal pages stay dense, and all entries sit in one sorted, linked layer that range scans can walk.

Here is an estimate for an index on an 8-byte bigint in PostgreSQL. A leaf entry is the key plus an 8-byte tuple header holding the row pointer, plus a 4-byte line pointer: roughly 20 bytes. An 8 KiB page therefore holds about 400 entries when full, and about 360 at the default B-tree fillfactor of 90 percent. Internal entries are similar in size, so fan-out is a few hundred.

Four levels for a hundred million rows, and the top three total under 800 pages, about 6 MB. They stay in the buffer pool permanently, so a point lookup costs one leaf read plus one table read in the worst case. Wider keys lower the fan-out: a UUID stored as 36-character text cuts it by more than half, which adds a level sooner and doubles the leaf footprint. Key width is the main thing you control that changes the shape of the tree.

What is on a page

A leaf page has a header (including the log sequence number of the last change, used by the write-ahead log), an array of line pointers, and the index tuples themselves. Line pointers are kept in key order, so binary search finds a key in about nine comparisons for 400 entries. Leaves also carry links to their left and right siblings, and in PostgreSQL each page except the rightmost on its level stores a high key: an upper bound on every key that page can hold.

Internal pages hold separator keys and downlinks. A separator only has to divide the key space, so it can be truncated to the shortest distinguishing prefix; PostgreSQL has done this suffix truncation since version 12, keeping internal pages dense for wide multi-column keys.

Search and range scans

A lookup starts at the root, binary searches the separators to choose a child, and repeats until it reaches a leaf. A range scan does the same descent for the lower bound, then walks right along the leaf chain until it passes the upper bound. That walk is why ORDER BY on an indexed column can avoid a sort and why LIMIT queries over an index can stop after a handful of entries.

def search(tree, key):
    page = tree.read(tree.root)
    while not page.is_leaf:
        i = bisect_right(page.separators, key)   # separators[i-1] <= key < separators[i]
        page = tree.read(page.children[i])
    i = bisect_left(page.keys, key)
    return page.pointers[i] if i < len(page.keys) and page.keys[i] == key else None


def range_scan(tree, lo, hi):
    page = descend_to_leaf(tree, lo)
    i = bisect_left(page.keys, lo)
    while page is not None:
        while i < len(page.keys):
            if page.keys[i] > hi:
                return
            yield page.pointers[i]
            i += 1
        page = tree.read(page.right) if page.right else None
        i = 0

In a heap table each yielded pointer is a table fetch. If matching rows are scattered, 50,000 entries can mean tens of thousands of random page reads, which is why planners switch to bitmap or sequential scans for unselective predicates.

Insert and split

An insert descends to the correct leaf and places the entry in order. If the page has room, that is the whole operation, plus a log record. If it does not, the page splits: a new page is allocated, roughly half the entries move to it, and a separator for the new page is inserted into the parent. A full parent splits too; if the root splits, a new root is created above it. That is the only way the tree grows taller, which keeps every leaf at the same depth.

def insert(tree, key, ptr):
    path = []                                    # internal pages visited, root first
    page = tree.read(tree.root)
    while not page.is_leaf:
        path.append(page)
        page = tree.read(page.children[bisect_right(page.separators, key)])
    page.insert_sorted(key, ptr)
    while page.overflows():
        right = tree.allocate()
        sep = page.move_upper_half_to(right)     # right-links and high keys updated here
        if not path:                             # splitting the root: tree grows one level
            tree.root = tree.new_internal([sep], [page.id, right.id]).id
            return
        parent = path.pop()
        parent.insert_separator(sep, right.id)
        page = parent

Where the split point goes matters. With random keys such as UUID version 4, inserts land on arbitrary leaves and each split leaves two half-full pages; the classic analysis puts the steady-state average fill at about 69 percent (ln 2). With monotonically increasing keys, such as a sequence or a timestamp, every insert hits the rightmost leaf. PostgreSQL detects that pattern and splits the rightmost page so that the left page keeps fillfactor worth of entries rather than half, so append-mostly indexes stay dense. The price is contention on that one page. Time-ordered identifiers such as UUID version 7 give sequence-like density without a central counter.

Deletes, dead entries and bloat

Deleting a key does not rebalance the tree the way textbook B-trees do. In PostgreSQL, an index entry is not even removed when its row is deleted, because other transactions may still see the old row under MVCC. Entries are cleared later by VACUUM, by scans that mark entries for dead rows as killed, and, since version 14, by bottom-up deletion before a page would split. A leaf is unlinked only once completely empty, and free space is reused only by keys that sort into that page.

The result is bloat: an index much larger than its live content, typically after a mass delete or heavy updates to indexed columns. PostgreSQL 13 added deduplication, which stores repeated keys once with a list of row pointers and shrinks low-cardinality indexes considerably. InnoDB does merge pages whose fill falls below a threshold (MERGE_THRESHOLD, 50 percent by default), which limits bloat but adds work to the delete path.

Concurrency: many sessions, one tree

Page splits are the hard part of concurrency. A reader descending the tree could read a parent, then arrive at a child that has just been split, with its key now on the new right sibling. The classic answer is latch coupling, or crabbing: hold the latch on a parent until the child is latched, and release ancestors once the child is known to be safe from splitting.

PostgreSQL's nbtree follows the Lehman and Yao B-link design instead. Every page has a right-link and a high key, so a reader that lands on a page whose high key is below its search key simply moves right until it finds the correct page. Readers therefore hold only one page latch at a time, and a split can finish in two steps (split the child, then update the parent) with the tree valid in between. Latches are short-term locks on in-memory pages, separate from transactional row locks.

Clustered versus heap tables

The row pointer in a leaf depends on how the table is stored. PostgreSQL keeps rows in an unordered heap, and every index, including the primary key, points at a physical tuple id. An update creates a new row version, so every index gets a new entry unless the update is heap-only (no indexed column changed and the version fits on the same page).

InnoDB stores the table itself as a B+tree on the primary key, with full rows in its leaves: a clustered index. Secondary indexes store the primary key as their row pointer, so a secondary lookup is two tree descents. Two consequences follow. A wide primary key is copied into every secondary index, and a random primary key scatters inserts across the whole table, not just the index. That is why InnoDB schemas favour compact, increasing primary keys.

In both designs, if the index contains every column a query needs, the table visit can be skipped. PostgreSQL still checks its visibility map to confirm the page holds only rows visible to everyone, so index-only scans work best on tables that are vacuumed regularly.

What a B-tree can serve

• Equality and range predicates on the leading column: =, <, >, BETWEEN, IN.
• Sorted output and ORDER BY ... LIMIT in either direction, plus MIN and MAX.
• Prefix pattern matches such as LIKE 'abc%', in PostgreSQL only under the C collation or with a text_pattern_ops operator class.
• Multi-column indexes whose leading columns are constrained. PostgreSQL 18 added skip scan, so an index on (region, created_at) can now serve a query on created_at alone by jumping between region values, which pays off when the leading column has few distinct values.
• Not served: suffix or infix matches, predicates wrapped in a function (unless you build an expression index on that function), array containment and full-text search (use GIN), and very low-selectivity predicates, where a sequential scan wins.

For comparisons with other index types see PostgreSQL Indexes, and for the storage-engine alternative, LSM trees versus B-trees.

Operating B-tree indexes

Three things are worth monitoring. First, usage: unused indexes still cost write amplification and memory. Second, bloat and density. Third, whether the hot part of each index fits in memory. In PostgreSQL:

-- Indexes never scanned since statistics were last reset (check replicas too).
SELECT schemaname, relname, indexrelname, idx_scan,
       pg_size_pretty(pg_relation_size(indexrelid)) AS size
FROM pg_stat_user_indexes
WHERE idx_scan = 0
ORDER BY pg_relation_size(indexrelid) DESC;

-- Leaf density and fragmentation for one index (pgstattuple extension).
CREATE EXTENSION IF NOT EXISTS pgstattuple;
SELECT tree_level, leaf_pages, avg_leaf_density, leaf_fragmentation
FROM pgstatindex('orders_customer_id_idx');

-- Rebuild without blocking writes (PostgreSQL 12 and later).
REINDEX INDEX CONCURRENTLY orders_customer_id_idx;

A B-tree index whose avg_leaf_density sits well below its fillfactor after a large delete is a rebuild candidate. REINDEX CONCURRENTLY builds a copy alongside the old index, needs about that much free disk, and leaves an invalid index to drop if it fails. Before dropping an unused index, check replicas, whose reads do not show in the primary's statistics, and whether it enforces uniqueness.

Failure modes

• Index sprawl. Every index is written on every insert and on most updates. Ten indexes on a hot table can cost more than the table itself.
• Random wide keys. UUID version 4 keys, especially stored as text, lower fan-out, spread writes across every leaf, and push the working set out of memory.
• Right-edge hotspot. Sequential keys concentrate every insert on one leaf; at very high insert rates the latch on that page becomes the bottleneck.
• Bloat after bulk deletes. The index keeps its size until rebuilt, and scans still read the sparse pages.
• Unusable predicates. WHERE lower(email) = $1 cannot use an index on email; implicit type casts in joins can defeat indexes in the same way.
• Collation changes. An operating-system upgrade that changes the C library's collation rules can silently corrupt text indexes in PostgreSQL. Rebuild text indexes after such upgrades, or use ICU collations with version tracking.

Trade-offs

A B-tree trades write cost for read cost. Each index makes lookups on its columns logarithmic and turns every write into several page modifications and log records. Compared with an LSM tree, a B-tree updates in place, which gives predictable read latency and no compaction debt, at the price of random writes and space lost to partly filled pages. A lower fillfactor leaves room for in-place growth and fewer splits, at the price of a bigger index. Clustering on the primary key makes key range scans fast and secondary lookups slower. There is no universally right answer, but there is a right question: which queries does this index serve, how often, and what do they save compared with what every write pays for it?

What to do next

1. List the indexes on your three busiest tables with their sizes and scan counts, and drop any with zero scans on every node that are not enforcing constraints.
2. Run pgstatindex (or check InnoDB's index statistics) on the largest indexes and rebuild those with low leaf density.
3. Check the key type of every primary key; replace random identifiers with compact, time-ordered ones in new tables.
4. Run EXPLAIN (ANALYZE, BUFFERS) on your slowest queries and confirm each one uses the index you expect, with the predicate in index-friendly form.
5. Estimate each hot index's inner pages plus hot leaves and confirm they fit in the buffer pool.
6. Schedule text-index rebuilds as part of any operating-system or collation upgrade.