B-Trees and Variants

Disk and SSD transfer data in fixed-size pages (often 4–16 KiB). A B-tree packs many keys into each page so one I/O advances you through a large key range. That is the whole design thesis: minimize random page reads per operation by maximizing fanout and keeping the tree height small and balanced after every insert and delete.

Production OLTP almost always uses a B+ tree: internal nodes are pure routers; all payloads sit in leaves; sibling pointers make ORDER BY … LIMIT and range predicates cheap. A clustered index may make those leaves the table itself. Secondary indexes are usually more B+ trees whose leaves store the primary key (or a heap TID) as the locator.

Writes are the tax. Inserting into a full leaf triggers a page split, which dirties at least two leaves and a parent, and may cascade. Each change also appends to the WAL before pages can be considered durable. A warm buffer pool hides most of this from the client; a cold cache or a rightmost-leaf hotspot makes it visible as latency spikes.

An insert finds the target leaf the same way as a lookup, then places the key in sorted order. If the leaf has free space, only that page (and the WAL) change. If not, the engine performs a page split: allocate a new page, move about half the entries, and insert a separator key into the parent. If the parent is full, the cascade continues. A root split is the only way the tree grows taller.

flowchart TD
  Ins["Insert into full leaf"] --> Alloc["Allocate sibling page"]
  Alloc --> Move["Move ~half entries to sibling"]
  Move --> Sep["Promote separator to parent"]
  Sep --> Full{"Parent full?"}
  Full -->|No| Done["Done"]
  Full -->|Yes| Cascade["Split parent similarly"]
  Cascade --> Root{"Was root?"}
  Root -->|Yes| Grow["New root → height +1"]
  Root -->|No| Full

Rightmost-leaf hotspot (SERIAL / BIGSERIAL primary keys):
  Every insert lands on the same hot leaf → frequent splits
  Contention: exclusive latches on that leaf and its ancestors
  Mitigations: UUIDv7 / time-ordered keys with jitter, reverse keys,
               hash partitioning, or a non-clustered heap + secondary PK

Deletes:
  Mark slot free or compact page; underflow may merge or borrow
  Engines differ: some defer merge aggressively to cut latch work
  Empty pages return to free space map; height rarely shrinks soon

That split cascade is a major source of B-tree write amplification under random inserts. LSM engines defer reorganization into compaction; B-trees pay some reorganization on the write path itself so the on-disk shape stays immediately searchable.

In InnoDB-style clustered layouts, the primary key leaf pages are the table. A secondary index leaf stores (secondary_key → primary_key). Looking up by email may need two tree walks: secondary leaf, then primary leaf. Covering indexes avoid the second walk when every needed column is already in the secondary leaf (or INCLUDE list).

Heap-organized tables (classic PostgreSQL heap + indexes) store rows in heap pages; every index leaf stores a TID. Updates that move a row may leave index entries pointing at redirecting tuples until cleanup. Either way, “one logical row write” can touch many B+ trees — that is index write amplification from the application’s point of view.

Example: users(id PK, email UNIQUE, status, created_at)
Indexes: PK clustered, UNIQUE(email), INDEX(status, created_at)

INSERT one user:
  + WAL records
  + clustered leaf insert (possible split)
  + email unique leaf insert (possible split)
  + status composite leaf insert (possible split)

Rule of thumb: every secondary index must earn its keep on hot read paths.

Read amplification vs write amplification. A warm B+ tree point get is a few page reads. A write may dirty multiple pages and several indexes immediately. LSM flips that: cheap sequential writes, more complex reads until compaction catches up.

Space vs split rate. Higher fill factor packs cache better but splits sooner. Lower fill factor burns space and can add a level earlier than necessary.

Page size. Larger pages raise fanout and sequential scan bandwidth; they also increase write amplification on small updates (a 16 KiB page dirtied for an 8-byte change) and raise latch granularity.

Concurrency. Fine-grained page latches scale better than tree-wide locks, but hot leaves still serialize. Design keys and partitions so traffic does not pin one leaf.