B-Tree on Disk

The board behind the index you’ve been using without knowing its shape, part of Database Internals - the deep-dive set. By the end of this lesson you’ll know why one page-sized decision turns a billion-row search into four stops, and one added arrow kept that search safe while somebody else was rearranging the pages underneath it.

Before you start. WAL & Recovery showed you that every change is written to a log and flushed to disk before its commit is confirmed, so a crash can always be replayed back to where it left off. This lesson is about the structure that log is protecting - the actual arrangement of pages your rows sit inside, and why finding one of a billion of them takes a blink.

The idea in 30 seconds

A table’s index is a much smaller, sorted copy of just the keys, kept next to the table.
A B-tree index is a search tree where each step down reads one whole disk page holding about 400 keys, not one key, so a billion rows take four disk trips instead of thirty.
The top few pages of that index are read so often they stay permanently in memory, so a real lookup on a huge table usually costs about one disk read.
When a bottom page of the index fills, it splits into two half-full pages and passes one dividing key up a level; the index only grows taller at the top, so every search stays the same number of steps and nothing needs fixing afterward.
Each index page also stores its highest allowed key and a pointer to the next page over, so a search that arrives just after a split moved its key can step right and recover, letting reads and writes share the index at once.

Read the story · Skip to the numbers