Build a B-tree storage engine (SQLite-style)
11 scenes · ~77 min · build the primitive

Build your own B-tree storage engine (SQLite-style)

What actually happens when you run INSERT INTO users(...). One file of fixed-size pages, organized as B-trees, with a write-ahead log that turns commits into appends. Build it from a SQL writer's perspective and feel why every knob exists.

Scenes
11 interactive scenes
Time
about 77 minutes
Topic
Storage Engines & Databases

What you are building, and why

You wrote INSERT INTO users(id, name) VALUES (42, 'Alice'). SQLite acked. Where did the row go?

You probably know it ended up in users.db somewhere. You may have heard the words "B-tree" and "WAL." You probably don't know — yet — that users.db is one file divided into 4 KB pages; that every read or write touches a whole page; that your users table is a B-tree of those pages with hundreds of children per interior page; that your INSERT walked from the root down through three pages to find its home leaf, wrote one cell, and (if you were lucky) came back without having to split anything; that the row didn't actually mutate users.db — it appended a frame to users.db-wal and fsynced that file; that the main file will catch up "later" (a checkpoint); that if a long-lived reader is open, that "later" never comes and your WAL grows to 20 GB.

This curriculum builds that picture, in order, from a SQL writer's perspective. Each scene starts with the question your last scene left unanswered, shows the next mechanism in a diagram you can drive with a slider, asks you to predict a consequence, and captures a one-line answer. By the end you can size a SQLite deployment for write-heavy logging, read-heavy reference data, or OLTP — and trace every knob's failure mode back to the scene that explains it.

The point is not to "describe SQLite." The point is to feel why a database is the shape it is. Once you've built this picture, every subsequent storage engine — InnoDB, Postgres heap, RocksDB, FoundationDB — collapses to "B-tree with this knob different" or "the LSM answer to this exact problem."

What you will be able to explain afterwards

  • fixed-size pages as the unit of disk I/O
  • B-tree of pages — interior keys, leaf rows, branching factor
  • binary-search descent: O(log_B N) page reads
  • leaf split + cascading parent split + root split
  • freeblocks, VACUUM, incremental_vacuum
  • secondary indexes as a second B-tree (write amplification)
  • page cache (pager) + LRU + working set
  • WAL + fsync — durability without rewriting the file
  • checkpoint + the long-reader starvation failure
  1. 01
  2. 02
  3. 03
  4. 04
  5. 05
  6. 05a
  7. 06
  8. 07
  9. 08
  10. 09
  11. 10

The brief

Why a flat or sorted file isn't enough.

  1. 01
    Find the row — why a file scan won't do — point, range and indexed lookups in one file
    A SQL engine has to answer point, range, and indexed lookups against ONE file — the only family of structures that can do all three is an ordered tree.
    ~7 min

Anatomy

Pages, the tree of pages, and how a search descends.

  1. 02
    The file is a strip of pages — 4 KB page reads and OS block alignment
    The DB file is a strip of identical fixed-size pages — every read/write is one whole page because the disk and OS work in pages.
    ~7 min
  2. 03
    Pages linked into a tree — branching factor of hundreds across three levels
    Pages are linked into a tree where leaves hold rows and interior pages hold keys + pointers — branching factor is hundreds, so 3 levels = ~64M rows.
    ~7 min
  3. 04
    Searching — a cursor descends the tree — one page I/O per tree level
    A point query reads exactly ONE page per tree level — three I/Os to find one row in a tree of millions, even on a miss.
    ~7 min

Mutations

Insert, split, delete — and why the file doesn't shrink.

  1. 05
    Insert and split — the tree grows — separator keys promoted to the parent page
    An INSERT writes one cell when there's room; when full, the leaf splits and a separator promotes to the parent — cascades grow the tree.
    ~7 min
  2. 05a
    Delete and VACUUM — the file doesn't shrink
    DELETE doesn't shrink the file — pages get freeblocks but never merge; only VACUUM rebuilds the file (at 2x disk cost).
    ~7 min

Indexes

Every CREATE INDEX is a second B-tree to keep current.

  1. 06
    Indexes — a second B-tree — two descents per read and write amplification
    Each CREATE INDEX builds a second B-tree; reads do TWO descents, but every write must update every index.
    ~7 min

Speed & durability

Page cache, WAL+fsync, and the checkpoint that keeps WAL bounded.

  1. 07
    The page cache — RAM is 1000x faster than disk
    The pager caches pages in RAM with LRU; you're fast iff the working set fits, slow the moment it doesn't.
    ~7 min
  2. 08
    WAL — durability without rewriting the file every commit
    Commits append page-images to the WAL and fsync; the main DB file is left alone until checkpoint — fast, and readers don't block.
    ~7 min
  3. 09
    Checkpoint — and the 20 GB WAL
    Checkpoints copy frames back to the DB file and rewind the WAL — but a long-lived reader can pin the WAL open forever, blowing it up.
    ~7 min

Design canvas

Size SQLite for write-heavy logging, read-heavy reference, OLTP.

  1. 10
    Design canvas — size a SQLite deployment
    Workloads pick different knob combinations; each knob has a 'too low' and 'too high' failure mode you can name from earlier scenes.
    ~7 min

More in Storage Engines & Databases

Open the box every design diagram labels "DB": pages, logs, LSM trees, wide-column, documents, graphs and columnar scans, built from scratch.

Prefer to design it yourself?

The same subject as a staged workspace: draw the architecture, and a simulator traces requests through the boxes you drew.

Open the Build a B-tree storage engine (SQLite-style) workspace