Storage Engines

The Data Systems track’s take on storage: a database has to put your bytes on a disk and find them again, and there turn out to be exactly two honest ways to do both. This lesson tells the story of each, and by the end you’ll know which one your own database is running.

Before you start. The previous lesson, Data Models and Query Languages, was about the shapes you’re allowed to store your data in - tables, documents, graphs - and the languages you ask questions in. This lesson is about what the database does after you say “save”: how it puts those bytes on a disk, and how it finds them again without reading everything you ever gave it.

The idea in 30 seconds

An index is extra structure built alongside your data, so a database doesn’t read every row to find one.
A B-tree overwrites a fixed-size page in place, splitting it in two when full, so a table stays only a few pages deep however big it grows.
Splitting in place means every write is a seek-and-overwrite: cheap occasionally, ruinous under a constant stream.
An LSM-tree never edits a page. It holds writes in memory and flushes them as one new sorted file, an SSTable - a sequential burst instead of a seek.
That shape trades cheap writes for reads that may check more than one file, until a background merge catches up.
Both are the same trade from opposite sides: an index makes reads fast and writes slower, and each design decides which side pays first.

Read the story · Skip to the numbers