B+Tree Index¶

What it is¶

A B+Tree is a balanced search tree with a very high fan-out, designed so that each node is one disk page. Internal nodes hold only routing keys and child pointers; all data (or pointers to data) lives in the leaves, and the leaves are linked in key order. It is the default index in PostgreSQL, MySQL InnoDB, SQL Server, Oracle, and SQLite.

Why a high fan-out tree, not a binary tree¶

A balanced binary tree over 1 billion keys has height ~30. If each node is a separate disk page, a lookup costs ~30 random reads — ~300 ms on an HDD. A B+Tree packs hundreds of keys into each page-sized node, so the height collapses:

Worked example: with 8 KB pages and 16-byte entries (8-byte key + 8-byte child pointer), an internal node holds ~500 entries. Height 4 covers 500⁴ ≈ 62 billion leaf entries. The root and level 2 (~500 pages, 4 MB) always stay in memory, often level 3 too (~250K pages, 2 GB), so a lookup costs one or two disk reads in practice. The same reasoning — minimize the number of cache lines or pages touched per lookup — appears in Memory Hierarchy and CPU Cache.

Structure¶

• Internal node with m children holds m - 1 routing keys. Child i contains keys between routing key i-1 and routing key i.
• Leaf node holds (key, value) pairs. In a secondary index the value is a pointer to the row: a TID (page number + slot) in PostgreSQL, or the primary key in InnoDB.
• Sibling links connect leaves in key order (often both directions), so range scans never go back up the tree.

A lookup for 25 walks root → n1 → l3: three page reads, whatever the table size. A range query BETWEEN 15 AND 35 finds 15 the same way, then follows sibling links l2 → l3 → l4, costing O(log n + k) for k results.

Inside a page: the slotted page layout¶

Keys have variable length, so a page cannot be a simple array. Databases use a slotted page:

+--------+--------------------------------------------+
| header | slot 0 | slot 1 | slot 2 | ...  →          |
+--------+--------------------------------------------+
|                 free space                          |
+-----------------------------------------------------+
|          ← ... | record 2 | record 1 | record 0     |
+-----------------------------------------------------+

The header stores the page LSN, number of slots, and free-space pointers. The slot array grows from the front and holds the offset of each record, kept in key order; the records grow from the back. Inserting a key in the middle shifts only the small slot array, not the records. Binary search runs over the slot array. The page LSN links the page to the WAL: during recovery, a log record is reapplied only if its LSN is greater than the page's.

Insert and split¶

1. Descend to the leaf that should contain the key.
2. If the leaf has room, insert it in sorted position. Done.
3. Otherwise split: allocate a new page, move the upper half of the entries into it, and insert a separator key plus a pointer to the new page into the parent.
4. If the parent is full, split it too — splits can propagate up to the root. A root split creates a new root, and that is the only way the tree grows taller, which is why it stays perfectly balanced.

Worked example (max 4 keys per leaf): leaf [10 20 30 40] receives 25. It splits into [10 20] and [25 30 40], and separator 25 is pushed into the parent.

Fill factor: after a 50/50 split, both pages are half full. Random inserts leave pages ~70% full on average. Sequential inserts (an auto-increment key) would leave every page half full, so engines detect appends at the right edge and split unevenly (90/10 or "rightmost split"). PostgreSQL's fillfactor setting leaves room on purpose so later updates fit without splitting.

Delete and merge¶

Deleting removes the entry from its leaf. In theory, a leaf that drops below half full is merged with a sibling or borrows entries from it. In practice, many engines (PostgreSQL included) do not merge eagerly — pages stay sparse until they become completely empty or the index is rebuilt. That is why indexes on tables with heavy delete churn bloat, and REINDEX (or pg_repack) can shrink them dramatically.

Clustered vs. heap-organized tables¶

The InnoDB design is why a random UUID primary key hurts MySQL: inserts land in random leaves of the clustered tree, causing splits and a cold working set, while an increasing key appends to the rightmost leaf.

The buffer pool¶

A B+Tree engine never reads or writes pages directly to disk from the tree code. Pages are accessed through a buffer pool: a fixed array of in-memory frames plus a hash table from page ID to frame.

• FetchPage(id) returns the cached frame or reads it from disk, evicting another page if needed (LRU, CLOCK, or LRU-K policies).
• A page in use is pinned and cannot be evicted.
• A modified page is dirty; it can only be written back after the WAL records describing its changes are on disk (the write-ahead rule).

A Go implementation of the buffer pool, CLOCK replacement, and page pinning is in Buffer Pool and B+Tree.

Concurrency: latch crabbing¶

Many threads traverse the tree at once. Short-term page locks are called latches (to distinguish them from transaction locks). Latch crabbing (or coupling): take the latch on a child before releasing the parent, releasing ancestors as soon as the child is known to be safe — it cannot split (inserts) or merge (deletes) as a result of this operation. Readers take shared latches; writers take exclusive latches on the path that might change. Production engines refine this further with optimistic descent and B-link trees (Lehman & Yao, used by PostgreSQL), which add a right-link and a high key to every node so readers can tolerate a concurrent split without holding the parent.

Index scan vs. sequential scan¶

An index lookup per matching row costs a random page read (if the row is not cached). A sequential scan reads every page, but in large, cheap, sequential I/O. The crossover is usually around 5–10% of the table's rows: above it, the planner prefers a sequential scan. A bitmap heap scan is the middle ground: collect all matching TIDs from the index, sort them by page, then read each needed page once in physical order. See Query Optimization.

Trade-offs¶

• Reads: O(log n) point lookups, O(log n + k) range scans — excellent, especially with the upper levels cached.
• Writes: each insert/update/delete modifies a page in every index on the table, and each dirty page is eventually written whole — see Write Amplification.
• Space: pages run ~50–70% full under random inserts; each index commonly adds 20–30% of the table size.
• Maintenance: heavy deletes leave sparse pages; periodic REINDEX or VACUUM reclaims space.

Real-world usage: Proxel's proxy_stats table had no index on (proxy_id, checked_at) — range queries for recent stats did full scans. Adding a composite index on (proxy_id, checked_at DESC) reduced query time from 400ms to 3ms.

Common pitfall¶

Adding an index and expecting it to always be used is the most common misunderstanding — the planner estimates the cost of an index scan vs a sequential scan and picks whichever is cheaper for the specific query and table statistics, not just whichever index technically applies. A query matching 15% of a table's rows may get a sequential scan even with a perfectly good index present, because random I/O for that many matching rows costs more than reading every page sequentially. See Query Optimization for reading EXPLAIN output to confirm which path the planner actually chose, rather than assuming from the schema alone.