Build your own database

Goal

Build a minimal SQLite clone following cstack's Let's Build a Simple Database (C; any language works — build-your-own.org's database book is a Go-flavored alternative), then push past the tutorial into durability. It proves you understand what happens between INSERT and bytes on disk — the layer DDIA describes and this exercise makes you implement.

Subject: full brief & instructions

Practices

• Databases and other storage systems — storage engines, indexing, WAL, and the write tax, from the inside.
• Algorithms & data structures — the B-tree is the star data structure of the storage world.

Milestones

1. REPL and statement parser — read input, recognize insert/select, reject the rest with a decent error. Shippable: an interactive shell that echoes parsed statements.
2. In-memory table — serialize fixed-size rows into 4KB pages in memory; insert appends, select scans. Shippable: insert rows, select them back.
3. The pager — persist pages to a file, read them back on demand through a page cache; open the file, find your data still there. Shippable: rows survive restart.
4. B-tree leaves — replace the append-only array with a leaf-node format: sorted cells, binary search, duplicate-key rejection, leaf splitting. Shippable: inserts out of order, selects in order.
5. Full B-tree — internal nodes, root splits, traversal for point lookups and range scans; print the tree structure to watch it grow. Shippable: thousands of rows with logarithmic lookups.
6. Beyond the tutorial: WAL — write-ahead-log every mutation, fsync before acknowledging, replay on startup. Shippable: kill -9 mid-insert-storm loses nothing acknowledged (write the crash-test script that proves it).
7. Secondary index — a second B-tree mapping a non-key column to row IDs, kept in sync on writes. Shippable: a benchmark showing the read speedup and the write tax from the concept note, measured on your own engine.

Stretch goals

• MVCC-style snapshot reads: readers see a consistent version while a writer works.
• An LSM-tree variant of milestone 6–7 and a write-throughput comparison — the B-tree/LSM fork of the concept note, benchmarked in your own code.
• Graduate to CMU 15-445's BusTub for buffer-pool eviction, query executors, and real concurrency control with an autograder.

Related

• Build your own database — subject — the standalone build spec: grammar, byte formats, WAL semantics, and acceptance per milestone.
• Databases and other storage systems — the concept note this drills; its Practice section cites this exercise.
• End-to-end ELT pipeline — the analytical other half of the theme.
• Algorithms & data structures — where the B-tree lives as theory.