Notesstorage🌱 seedling

B-Tree

Also: B+Tree · B+ Tree · Btree · B-Tree Index

A balanced tree of fixed-size pages that keeps keys sorted and updates them in place: a lookup follows one page per level from root to leaf. High fanout keeps it shallow, and page splits keep every leaf at the same depth.

Why it exists

Sorted data on disk needs a structure that supports point lookups, range scans and in-place updates, with a bounded number of page reads per operation, at any size.

How it works

  • Interior pages hold separator keys and child pointers; leaves hold entries. In the common B+tree variant only leaves hold data, linked left to right for range scans.
  • Fanout is hundreds of keys per page (8 KB pages in Postgres, 16 KB in InnoDB), so three or four levels cover hundreds of millions to billions of rows; the top levels stay cached.
  • Insert into a full leaf splits it into two half-full pages and adds a separator to the parent, which may split in turn. A root split adds a level at the top.
  • Changes are logged to the Write-Ahead Log first, because a split touches several pages at once.
  • Concurrent writers coordinate with short page latches.

Trade-offs

Gains Costs
predictable reads: one path, one place per key random writes; a whole page rewritten per small change
excellent range scans pages left partly empty by splits (fragmentation)
each key in one place, convenient for locking WAL plus full-page images add Write Amplification

In practice

  • PostgreSQL, MySQL (InnoDB), SQLite, SQL Server and Oracle all default to B-trees. InnoDB stores the whole table in one, a Clustered Index.
  • LMDB uses a copy-on-write B-tree: it copies changed pages up to a new root instead of overwriting.

Pitfalls

  • Random keys (UUIDv4) scatter inserts across every leaf: more splits, more cache misses, half-empty pages. Time-ordered keys (UUIDv7) append at the right edge.

Recall

These cards are also in your review deck, scheduled with spaced repetition.