B-Trees and Write-Ahead Logs

How a B-tree finds any key in a few page reads, how it splits pages as it grows, and how the write-ahead log keeps in-place updates safe after a crash.

Overview

A B-tree is a sorted, balanced tree built out of fixed-size disk pages. It is the default index in most relational databases: PostgreSQL's default index type is a B-tree, and every InnoDB table in MySQL is itself a B-tree ordered by its primary key. It answers point lookups and range scans in a small, predictable number of page reads.

Where an LSM-tree never changes a file, a B-tree changes pages in place. That is what makes reads simple, and it is also why a B-tree needs a write-ahead log: a crash in the middle of changing pages must not leave the tree broken.

Pages and the tree

The disk is split into pages of one fixed size. PostgreSQL uses 8 kB pages by default, InnoDB 16 KB, and SQLite 4096 bytes. Each page holds sorted keys. In an inner page, the keys sit between pointers to child pages, and each pointer covers the range of keys between its two neighbors. Leaf pages hold the entries themselves, or pointers to the rows.

A lookup starts at the root and reads one page per level until it reaches a leaf. The number of children per page is the branching factor, and it is large: a page of several kilobytes holds hundreds of keys and pointers. So the tree is short, and the top levels are small enough to stay in memory.

300 — 3 — 90,000 — 9 million
300 — 4 — 27 million — 2.7 billion
500 — 4 — 125 million — 12.5 billion

The table is arithmetic, not a measurement: leaf pages = branching factor to the power (levels minus 1). Four levels with a few hundred children per page already reach billions of keys, which is why lookups take about three or four page reads.

Range scans

Leaf pages are linked to their neighbors. In PostgreSQL, each level of a B-tree can be walked as a doubly linked list of pages. A range query descends once to the first key, then walks leaf to leaf until the range ends.

Inserts and page splits

An insert descends to the leaf that should hold the key. If the page has room, the key is added in sorted order and the page is rewritten. If the page is full, it splits: about half the entries move to a new page, and the parent gets a new key and pointer for it. If the parent is also full, it splits too. When the root splits, a new root is made above it and the tree grows one level. This is how a B-tree stays balanced: every leaf is always the same distance from the root.

To leave room and split less often, PostgreSQL fills B-tree leaf pages to 90% when it builds an index or appends new largest keys (the fillfactor setting, 10 to 100). InnoDB tries to leave about one sixteenth of each index page free for later inserts, so pages filled in key order end up about 15/16 full.

The write-ahead log

Changing pages in place is risky. One insert may touch three pages in a split, and a crash between them would leave a pointer to a page that was never written. The fix is the write-ahead log (WAL): a file that only grows at the end, where every change is described before any data page is changed.

PostgreSQL's rule is that a change to a data file may be written only after the log records that describe it are on stable storage. This has two benefits. After a crash, the database replays the log from the last checkpoint and redoes whatever did not reach the data files. And a commit only needs one sequential flush of the log, not a flush of every page it touched. PostgreSQL makes a checkpoint at least every 5 minutes by default (checkpoint_timeout).

Replaying a record twice is harmless because each page remembers how far it is in the log. In PostgreSQL, a page header stores the log position (LSN) just after its last change, so recovery can tell which records a page already has.

Torn pages

A page write can itself be cut in half: the disk writes part of an 8 kB page, then power fails. The log records a small change, which cannot repair a page that is half old and half new. Each engine has a fix.

PostgreSQL — full_page_writes (on by default) — The first change to a page after each checkpoint logs the whole page, so recovery can rebuild it
MySQL InnoDB — Doublewrite buffer (on by default) — Pages are first written to a separate area in one sequential write; a torn page is restored from that copy
LMDB — Copy-on-write — A changed page is written to a new location, and the tree's root is switched only at commit, so old pages are never overwritten mid-transaction

LMDB shows the other way to be crash safe. It never overwrites a live page. Each write copies the pages from the leaf up to the root, and the commit switches one of two meta pages to the new root. Readers keep seeing the old root until they finish.

B-tree or LSM-tree

A write — Rewrites the page in place, plus a log record — Log append plus memory; files merged later
A point read — One page per level, often mostly cached — Memtable, then files, filtered by Bloom filters
A range scan — Descend once, follow leaf links — Merge results from several files
Extra writes — Whole pages for small changes, full-page images, splits — Compaction rewrites data several times
Latency — Steady — Can spike when compaction is busy

What you will be able to do

Explain how a B-tree finds a key in about three or four page reads, and estimate its height.
Walk through an insert that splits a page.
Explain the write-ahead log rule and how recovery uses it.
Name the torn-page problem and how PostgreSQL, InnoDB and LMDB solve it.
Compare B-trees and LSM-trees for a given workload.

Key concepts

Page: The fixed-size block a B-tree is built from: 8 kB by default in PostgreSQL, 16 KB in InnoDB, 4096 bytes in SQLite.
Branching factor: The number of child pointers in an inner page. Hundreds per page keep the tree three or four levels deep.
Page split: When a full page gets a new entry, half its entries move to a new page and the parent gets a pointer to it. Splits can climb to the root.
Sibling links: Pointers between neighboring pages on the same level, so a range scan can walk leaf to leaf.
Write-ahead log (WAL): An append-only log where each change is recorded, and flushed, before the data page it describes is written.
Checkpoint: A point where all changed pages are written to the data files, so recovery can start replaying the log from there.
Torn page: A page only partly written when the power failed. Fixed by full-page images in the log, a doublewrite area, or copy-on-write.
Fill factor: How full a page is packed when an index is built. PostgreSQL B-tree indexes default to 90, leaving room for later inserts.

When to use it

Explaining why an indexed lookup in PostgreSQL or MySQL takes only a few page reads
Comparing B-tree and LSM-tree engines for a read-heavy or write-heavy workload
Explaining crash recovery and the role of the write-ahead log
Reasoning about why random-key inserts cause more page splits than sequential ones

Interview questions

How does a B-tree survive a crash in the middle of a write?
Why is a B-tree only three or four levels deep, even for a huge table?
Walk me through an insert that causes a page split.
When would you pick a B-tree engine over an LSM-tree engine?
How can a B-tree be crash safe without a write-ahead log?