rgoussu.dev
rgoussu@goussu: ~/library/data-storage/exercises
❯ ~/library/data-storage/exercises cat build-your-own-database-subject.md

Build your own database — subject

# The build spec for a SQLite-style engine — REPL grammar, row and page formats, pager, B-tree node layouts and splits, WAL with crash-proof replay, and a secondary index.

Subjectsaved 2026-08-08source #exercise#databases#storage#data-structures#subject

Brief

Build a single-file, single-table database engine with an interactive shell, in any language (C follows the original most closely; the formats below are language-neutral). The table is fixed-schema — id INTEGER PRIMARY KEY, username VARCHAR(32), email VARCHAR(255) — which keeps parsing trivial and puts all the difficulty where it belongs: pages, trees, and durability. By the end, rows survive kill -9, lookups are logarithmic, and you can explain every byte in the file.

Instructions

1. REPL and grammar

An interactive prompt (db > ) accepting:

  • Meta-commands, prefixed with a dot: .exit; add .btree (print the tree) and .constants (print layout constants) as you go — they are your debugger.
  • Statements:
    • insert <id> <username> <email> — id is a positive integer; strings are space-delimited (no quoting needed).
    • select — print every row as (id, username, email) in key order.
    • Later: select <id> (point lookup) and select where email = <value> (via the secondary index).
  • Unrecognized input gets a specific error (Unrecognized keyword at start of '…'), oversized strings and negative ids are rejected at parse time — the statement is validated before it executes.

2. Row format and in-memory pages

  • A serialized row is fixed-size: id u32 little-endian, username 32 bytes, email 255 bytes, null-padded — offsets are compile-time constants.
  • Storage is organized in 4096-byte pages held in a page array; rows pack contiguously. First version: append-only, full-scan select, memory only.

3. The pager

  • All page access goes through a pager: get_page(page_num) returns a cached page, reading it from the database file on first touch (a page-sized cache slot per page; no eviction needed at this scale).
  • On .exit, flush dirty pages to the file at page_num * 4096. Reopening the file finds the data: file length / page size tells you what exists.

4. B-tree leaf nodes

Replace the packed array with one page = one B-tree node. Common node header: node-type byte, is-root byte, parent pointer (u32). Leaf body: cell count (u32), next-leaf pointer (u32, 0 = none, for range scans), then cells — each cell a key (u32) + serialized row, kept sorted by key.

  • Insert finds the position by binary search; duplicate keys are an error (Error: Duplicate key.).
  • When a leaf overflows, split: allocate a sibling, move the upper half of the cells, wire the next-leaf pointers, push the split key to the parent.

5. Internal nodes and the full tree

Internal body: key count (u32), rightmost-child pointer (u32), then pairs of (child pointer u32, max key in that child u32).

  • Root split: the root's contents move to a fresh page; the root page itself becomes the new root (internal node with two children) so the root's page number never changes (page 0 forever).
  • Point lookups and inserts descend by binary search over the keys; select walks the leftmost leaf then follows next-leaf pointers.
  • Internal-node splitting must work too — inserting thousands of keys in random order may not corrupt the tree (.btree output stays consistent).

6. Write-ahead log

Durability, past the tutorial's edge:

  • Record format (yours to refine, but at least): record type (page-write/commit), page number, page image (or a delta), and a checksum (CRC32 over the record) so a torn tail is detectable.
  • Every mutation appends its record(s) plus a commit record to the WAL and fsyncs the WAL before acknowledging the insert; only then may the pager write the page in place (or defer it).
  • On open: scan the WAL, discard anything after the last valid-checksummed commit, replay the rest onto the data file, fsync, then truncate.
  • Checkpoint: when the WAL exceeds a threshold (or on a .checkpoint meta-command), flush all replayed/dirty state to the main file, fsync it, truncate the WAL.
  • Write the crash-test harness: a script that spawns the REPL feeding it inserts, kill -9s it at random points in a loop, reopens, and verifies every acknowledged row is present and the tree is well-formed.

7. Secondary index

  • A second B-tree (same node formats) keyed on email (fixed 255-byte key or a hash of it — decide and document), whose values are row ids (the primary key).
  • Maintained in the same logical write as the primary insert — WAL covers both, so a crash can't leave them out of sync.
  • select where email = … descends the index then the primary tree.
  • Benchmark: N random inserts and M point reads by email, with and without the index — show the read speedup and measure the write tax.

Examples

db > insert 1 user1 person1@example.com
Executed.
db > insert 2 user2 person2@example.com
Executed.
db > select
(1, user1, person1@example.com)
(2, user2, person2@example.com)
Executed.
db > insert 1 dup dup@example.com
Error: Duplicate key.
db > .exit

Constraints

  • No storage, B-tree, or serialization libraries — stdlib file I/O and memory only. (Testing libraries and a CRC implementation are fine.)
  • Page size stays 4096 bytes everywhere; all multi-byte integers little-endian.
  • Every stage keeps the previous stage's tests passing; keep a growing test file of REPL sessions (script in / expected out).

Acceptance

Mapped to the exercise's milestones:

  1. REPL — the session in Examples behaves exactly as shown for the happy paths; bad input (unknown keyword, string too long, negative id) yields the specific error and a clean next prompt.
  2. In-memory table — insert then select round-trips rows; a row exactly filling the last page slot works; inserting past the page-array cap reports a full table rather than corrupting.
  3. Pager — insert, .exit, reopen, select: rows are back. Hexdump the file and point at a row's bytes.
  4. Leaf nodes — out-of-order inserts come back sorted; duplicate key errors; overflowing one leaf produces a split visible in .btree.
  5. Full tree — 10k random-order inserts: select returns all in order, select <id> touches only ~log-depth pages (instrument the pager to count), .btree shows a balanced multi-level tree.
  6. WAL — the crash-test harness runs ≥100 kill-reopen cycles with zero acknowledged-row loss and zero malformed trees; a WAL with a torn final record opens cleanly, dropping only the unacknowledged tail.
  7. Secondary index — email lookups return the same rows as a full scan; crash-testing during indexed inserts never de-syncs the two trees; the benchmark table (reads/sec, writes/sec, with/without index) is committed with the code.

Related