Part 4 of 8 · 3 min read
How a B-tree writes
Updating in place, splitting a full page, and the log that guards against a crash.
Think of editing a printed binder page. If a page is full and a new entry must be added, the editor splits it into two pages and updates the index at the front of the binder. If the editor is interrupted halfway, the binder may have the new page but no entry for it.
The book describes the writes of a B-tree.
- Update an existing key. Find the leaf page, change the value and write the page back to its same place. References to the page stay valid.
- Add a new key. Find the page whose range covers the key and add it there. If the page has no room, split it into two half-full pages, and update the parent page with a new reference. If the parent is also full, it splits too, and so on up to the root.
A worked example of a split. A leaf page holds at most 4 keys: 10, 20, 30, 40. The key 25 arrives.
- The page is full. Split it into two: [10, 20] and [30, 40].
- Insert 25 into the page where it belongs, [10, 20, 25].
- The parent gains a reference for the new page, with the border between 25 and 30.
- Pages written: the two leaf pages and the parent page, 3 page writes for one new key.
The book points out the danger. A split overwrites several pages. If the database crashes after writing only some of them, the index is corrupted. For example, a page might exist that no parent points to.
Write-ahead log
A write-ahead log (WAL, also called a redo log) is an append-only file on disk. Every change to the tree is written there first, before the pages are changed. After a crash, the log is replayed to bring the tree back to a consistent state.
Example: the change "insert key 25" is appended to the log. Only then are the pages updated. A crash between the two is repaired by replaying the log.
Two more points from the book:
- Concurrency. When many threads read and write the tree, it must be protected, usually with light locks called latches, or readers could see the tree half-changed.
- Alternatives to overwriting. Some databases, such as LMDB, use copy-on-write: a changed page is written to a new location, and new versions of its parents are written pointing to it. The old tree stays valid until the switch. This also helps concurrency control.
Other optimisations in the book: shortening the keys in interior pages so more fit in a page (a higher branching factor and fewer levels), laying leaf pages out in order on disk to speed up scans, and sibling pointers.
Every B-tree write is at least two writes. The book says a B-tree writes every piece of data at least twice: once to the log and once to the page. A page must be written whole even when only a few bytes change.
A worked example. A row of 100 bytes is updated in a 4 KB page.
- The log gets about 100 bytes.
- The page gets the full 4,096 bytes.
- Total written: about 4,200 bytes for 100 bytes of change, a ratio of about 42.
Common mistake
Believing that a B-tree write is one small write. The page is rewritten whole, the log is written too, and a split touches several pages. Heavy random writes make B-tree engines busy.
Check yourself:
- What happens to a full leaf page when a key must be added?
- Why does a B-tree engine keep a write-ahead log?