Skip to content
Course contents

Storage and Retrieval

What a database actually does with your bytes — logs, indexes, B-trees, LSM-trees — and why the answer depends on whether you are writing or reading.

5 lessons2 labs2 hr 29 min

What you will be able to do

  • Build the simplest database that works, and explain exactly where it falls over
  • Explain what an index costs on write in exchange for what it saves on read
  • Describe how an LSM-tree turns random writes into sequential ones, and what compaction is paying for
  • Compare a B-tree and an LSM-tree on write amplification, read amplification and space, and pick one for a stated workload
  • Say why an analytics query wants its data stored by column and a transaction wants it by row

This is the module where the database stops being a black box.

You will start by writing a database in two lines of shell, watch it work, and watch it become unusable at exactly the point you would predict. Fixing it — without ever giving up the thing that made it fast — walks you through hash indexes, sorted string tables, log-structured merge trees, and B-trees, in the order the industry discovered them and for the reasons it discovered them.

By the end you will be able to answer the question that decides which database to reach for: does this workload write more than it reads, and does it read one row or ten million? That question has a different answer for the checkout page than for the dashboard your CFO opens on Monday, which is why one company usually runs both kinds of engine.

This module has the most labs. That is on purpose — a storage engine is a thing you understand by building a small wrong one first.

Read alongsideChapter 3 of Designing Data-Intensive Applications.

In this module7

01The Simplest Database That Works9 min

Two lines of shell make a real database. Understanding exactly why it becomes unusable is the whole of this module in miniature.

02Hash Indexes and Where They Run Out9 min

Keep a map from key to file offset and reads become one seek. Then count how much memory that map needs, and try a range query.

03Sort the Segments, Change Everything12 min

One change — keep each segment sorted by key — fixes the memory limit and the range-query limit at once, and gives you the LSM-tree.

04B-Trees, and Choosing Between Them13 min

The other answer to the same problem — update pages in place instead of merging logs — and the three amplifications that decide which one you want.

05Rows for Transactions, Columns for Questions11 min

The checkout page and the Monday-morning dashboard want opposite physical layouts. That is why most companies run two databases and copy data between them.

labBuild a Log-Structured Store45 min

The two-line database, done properly — append-only log, in-memory index, tombstones, and compaction that never mutates what it has already written.

labSparse Lookup and the k-Way Merge50 min

Sorting bought a sparse index and a streaming merge. Write both, including the tombstone rule that stops deleted records rising from the dead.

practicePractice questions2 questions

Written exercises with worked answers, for the questions code cannot ask.

Start module 3