Database 04: The B-Tree

Follows Pages, and hands off to Write-Ahead Log.

Before you start. This series builds a small database: a program that stores rows on disk and finds them again by key. So far it can split a file into fixed-size 4 KB blocks called pages, and give every row an address made of a page number plus a slot inside that page. It can also find one row instantly by key, using a table built for single lookups - but that table cannot answer “every row between these two keys,” only one key at a time, because the trick that makes it fast also scrambles the order of the keys. What’s missing is a catalog that keeps its entries in order and is still built out of those same fixed-size pages. That catalog is what this lesson builds.