Storage engines: pages, B-trees and the WAL

Your database is a file of fixed-size pages, usually 4 KB to 16 KB. Every read and write moves whole pages between disk and memory, and every index is a tree of pages. Once you know that, many query and performance questions get easier to answer. Why is a random primary key slow to insert? Why does one extra column in an index make it bigger? Why does a crash not lose committed data?

The most common answer to "how do databases find data?" is the B+tree, used by PostgreSQL, MySQL InnoDB, SQLite and SQL Server. The B+tree is wide, shallow, and balanced, so a lookup reads only a few pages.

The big idea

Three parts work together:

1. Pages hold rows and index entries in a fixed size, so the storage layer moves data in equal blocks.
2. The B+tree finds the page that holds a key. Each level narrows the search by a factor of hundreds.
3. The buffer pool keeps hot pages in RAM. The write-ahead log (WAL) makes changes durable before the pages are written.

Concepts in this topic

A B+tree is one of two main families. The other, LSM trees, writes to a log and merges sorted files in the background. It favors writes at the cost of reads. See LSM storage engines for that trade-off.

Why this matters at work

Most performance problems in a relational database come down to pages: how many are read, whether they are in memory, and how well they are packed. A query that reads 3 pages from cache is fast. The same query reading 3 pages from disk, plus 300 random leaf pages because the index doesn't cover it, is slow. Query execution covers the planner's side. This topic covers what it's planning around.

Common mistakes

• Assuming an index is always a win. Each index adds write work, pages to keep in cache, and space.
• Ignoring page fill. Random inserts into a tree leave pages half full, so the table grows.
• Expecting the buffer pool to hold the whole database. When the hot set doesn't fit, reads hit the disk.

Key takeaways

• A database is a set of fixed-size pages, and every index is a tree of them.
• A B+tree with a fanout of hundreds reaches millions of rows in three or four reads.
• The buffer pool caches pages, and the WAL makes commits durable.
• Index design is about which pages a query touches, not only which columns it filters on.

Further learning

Andy Pavlo's CMU Database Systems lectures cover B+trees, buffer pools and logging. They are free on YouTube and among the most thorough treatments available.

Search for Andy Pavlo's CMU Database Systems lectures on YouTube.

Next, start with pages and row layout.