🗃️

Building a Database Engine: Storage & Query Fundamentals

Records, Pages, a Heap Table, a Real B-Tree & a Small SQL Engine — From Scratch

Topics covered:
A real binary record format & a slotted page layout
A file-backed heap table & a real B-tree index
A small SQL-like tokenizer, parser & query executor
Basic index-aware query planning

Capstone: a real product-inventory engine, queried end to end via real SQL text
Exercises: 27 hands-on exercises with worked, verified solutions
Format: A4 · Dark-theme code examples
Philip Osztromok · Generated with Claude

Table of Contents

  1. Why Build a Database Engine? Storage, Indexing & Queries
  2. Records: Encoding Typed Rows as Real Bytes
  3. Pages: A Fixed-Size, Slotted Page Layout
  4. A File-Backed Heap Table
  5. B-Tree Indexes: Structure & Search
  6. B-Tree Indexes: Insertion & Node Splitting
  7. A Small SQL-Like Language: Tokenizing & Parsing
  8. Query Execution: From a Parsed Query to Real Results
  9. Using the Index: Basic Query Planning
  10. Capstone — A Working Single-Table Engine
Chapter 1 of 10

Why Build a Database Engine? Storage, Indexing & Queries

Building a Database Engine: Storage & Query Fundamentals

Chapter 1 · Why Build a Database Engine? Storage, Indexing & Queries

A database is a program whose entire job is to make two things true at once: data survives being written to disk, and finding a specific piece of it later doesn't get slower and slower as more of it piles up. Those sound almost too obvious to need saying — until the naive, first-instinct way of solving each one is measured directly, and turns out to fail at exactly the scale that matters.

Scope note — read this before anything else
This course, across both of its two parts, is deliberately scoped down from a real, production database engine: no client-server networking protocol (everything runs as a local, in-process library), no full SQL — a genuine but small subset (CREATE TABLE/INSERT/SELECT/WHERE, with joins added in Course 2), no distributed or replicated storage, and no cost-based query optimizer beyond simple, honestly-stated heuristics. Course 1 — this course — builds a real, working single-table engine: storage, indexing, and querying. Transactions, crash recovery, concurrent access, and multi-table joins are Course 2's own entire subject, not attempted here.

The Pipeline Both Courses Build

StageWhat it doesBuilt in
RecordsEncoding one typed row (integers, text, ...) into real, fixed-format bytes, and decoding it backChapter 2
PagesThe real, fixed-size unit of disk I/O — packing variable-length records into a slotted layoutChapter 3
A heap tableReal pages, written to and read from an actual file — a genuine, if simple, persistent tableChapter 4
B-tree indexesA real balanced tree, giving a lookup that doesn't degrade as the table growsChapters 5–6
A query languageA small, real SQL-like grammar — tokenized and parsed, not just accepted as a stringChapter 7
Execution & planningTurning a parsed query into real results, choosing an index when one genuinely helpsChapters 8–9

Problem 1: Rewriting Everything on Every Write Doesn't Scale

The obvious first instinct for "don't lose data": keep every row in a Python list, and after each insert, write the whole list to disk — nothing can be lost if the process dies, because the file on disk is always fully up to date.

def naive_insert_full_rewrite(path, rows, new_row): rows.append(new_row) with open(path, 'wb') as f: pickle.dump(rows, f) # rewrites EVERY row already stored, every single time return rows
Verified directly — real, measured timing, growing worse than linearly
500 inserts, full-file rewrite each time: 0.153s. 1,000 inserts (2× the data): 0.454s — 2.96× the time, not 2×. 2,000 inserts (4× the data): 0.932s — 6.08× the time, not 4×. If this scaled linearly, doubling the insert count should roughly double the time. It doesn't: each insert has to re-serialize every row already stored, not just the new one — the total work for N inserts is proportional to 1+2+...+N, which is O(N²), not O(N). A version that simply appends in memory and writes once at the end, by contrast, scales cleanly linearly — 0.13ms for 500 appends, 0.91ms for 4,000, no disproportionate blowup at all.

This is exactly why a real database never rewrites its whole dataset on every write — Chapters 2–4 build the real alternative: fixed-size pages, where only the page actually touched by a write needs to change.

Problem 2: A Linear Scan Gets Slower as the Table Grows

Even setting persistence aside entirely, finding one specific row in a plain Python list means checking rows one at a time until a match turns up.

Verified directly — a real, measured, worst-case comparison count that scales with table size
A table of 1,000 rows, looking up the last row: 1,000 comparisons needed. A table of 10,000 rows, same kind of lookup: 10,000 comparisons. A table of 100,000 rows: 100,000 comparisons. The table growing 100× makes this specific lookup 100× more expensive too — a linear scan's own worst-case cost grows exactly as fast as the table itself.

log₂(100,000) ≈ 16.6 — the real target Chapters 5–6's own B-tree index is working toward: a lookup that costs roughly 17 comparisons at 100,000 rows, not 100,000.

Where This Connects

This chapter's findingWhat it connects to
Full-file rewrite growing worse than linearly with every insertChapter 3's own slotted page format and Chapter 4's own heap table — the real fix is writing only the one page that actually changed, never the whole file
A linear scan's own worst case scaling directly with table sizeChapters 5–6's own real B-tree — the direct, measured motivation for building a balanced tree instead of trusting Python's own list
This site's own established real-benchmark disciplineAlgorithms & Complexity (this site's own Maths for Programmers subject) and this project's own sibling courses (compiler1/compiler2, browserengine1/browserengine2) — every claim in this course is verified with real, hand-run Python before being written, not asserted from Big-O notation alone

Hands-On Exercises

Exercise 1

Measure naive_insert_full_rewrite's own real timing at 3,000 inserts, and compare it against the chapter's own 500-insert measurement. Confirm the ratio between the two times is worse than the 6× a linear relationship would predict for 6× the data.

📄 View solution
Exercise 2

Build a table of 5,000 rows and measure how many comparisons a linear scan needs to find the first row versus the last row. Confirm the two counts differ dramatically, and explain why a real database can't rely on the best case when giving a performance guarantee.

📄 View solution
Exercise 3

Compute log₂(n) for four table sizes — 1,000, 10,000, 100,000, and 1,000,000 rows — and compare each one against a linear scan's own worst-case comparison count at that same size. Describe, in your own words, how the gap between the two changes as the table grows.

📄 View solution

Chapter 1 Quick Reference

  • This course's own honest scope: a real single-table engine — storage, indexing, and a small SQL-like query language. No networking, no full SQL, no distributed storage, no cost-based optimizer
  • Transactions, crash recovery, concurrency, and joins are Course 2's own entire subject — not attempted here
  • Verified problem 1: rewriting the whole dataset on every insert grows measurably worse than linearly — a real, timed 6×-the-data-to-11×-the-time result
  • Verified problem 2: a linear scan's own worst-case cost grows exactly as fast as the table itself — the real, measured motivation for a B-tree index
  • The pipeline: records → pages → a heap table → B-tree indexes → a query language → execution and planning
  • Next chapter: Records — encoding a typed row as real, fixed-format bytes, and decoding it back
Chapter 2 of 10

Records: Encoding Typed Rows as Real Bytes

Building a Database Engine: Storage & Query Fundamentals

Chapter 2 · Records: Encoding Typed Rows as Real Bytes

Every later chapter in this course reads and writes raw bytes on disk. Before any of that can happen, one row — a Python list of typed values — has to become a real, fixed, unambiguous sequence of bytes, and come back out the other side exactly as it went in. That's this chapter's entire job.

Two Column Types, Two Encoding Strategies

class Schema: def __init__(self, columns): self.columns = columns # [(name, col_type), ...] -- col_type: 'INTEGER' | 'TEXT' def encode_row(schema, values): buf = bytearray() for (name, col_type), value in zip(schema.columns, values): if col_type == 'INTEGER': buf += struct.pack('>q', value) # always exactly 8 bytes, signed elif col_type == 'TEXT': buf += encode_text(value) # variable length -- needs its own length prefix return bytes(buf)

An integer is always exactly 8 bytes — struct's own '>q' format (big-endian, signed 64-bit) — so a decoder always knows exactly how far to read. Text has no fixed length at all, so it needs a length prefix: a small header recording exactly how many bytes of text follow.

A Real, Severe Bug: Character Count vs. Byte Count

def encode_text_naive(text): encoded = text.encode('utf-8') length_prefix = struct.pack('>H', len(text)) # BUG: character count, not byte count return length_prefix + encoded

Reasonable-looking — len(text) is right there, and it's a length. But UTF-8 is a variable-width encoding: plain ASCII characters take one byte each, but many real characters — accented letters, most non-Latin scripts, emoji — take two, three, or four.

Verified directly — pure ASCII text hides the bug completely
A schema [('name', 'TEXT'), ('age', 'INTEGER')], row ["Alice", 30], encoded and decoded with the naive text functions: round-trips perfectly. Every character in "Alice" is one byte in UTF-8, so the character count and the byte count are identical — the naive function's own mistake produces the exact right number, by coincidence, every single time the text happens to be pure ASCII.
Verified directly — one accented character corrupts the text AND every field after it
The same schema, row ["café", 30]. "café" has 4 characters but its UTF-8 encoding is 5 bytes — é alone takes 2 bytes. The naive encoder writes a length prefix of 4. Decoding: the text comes back as 'caf�' — the truncated, mangled remains of a multi-byte character cut off mid-way. Worse: because the decoder only advanced its own read position by 4 bytes instead of the real 5, the age field — a completely unrelated integer — gets read starting one byte too early, from data that was never meant to be a number at all. The result: -6269010681299730432 instead of 30. One wrong length prefix on a text field doesn't just corrupt that field — it corrupts every field after it in the same row.
def encode_text(text): encoded = text.encode('utf-8') length_prefix = struct.pack('>H', len(encoded)) # FIXED: the real BYTE count return length_prefix + encoded
Verified directly — both the text AND every field after it decode correctly
Same row, fixed encoder/decoder: ["café", 30] comes back exactly as it went in — the text intact, and age correctly 30, since the decoder's own read position is now byte-accurate.

Where This Connects

This chapter's findingWhat it connects to
A byte-accurate length prefix, correctly advancing the decoder's own read positionChapter 3's own slotted page format, which packs several of these encoded records, one after another, into a single page — every record's own length has to be exactly right for the next one to even be findable
A bug invisible under ASCII, severe under real-world textA genuinely common, real-world category of bug — any system distinguishing "character count" from "byte count" only when it matters (non-English names, accented characters, emoji) risks looking correct in testing and failing in production the moment real, diverse user data arrives
Fixed-width integers needing no length prefix at allChapter 5's own B-tree node layout, which will lean on exactly this property — a fixed-size key can be found at a predictable offset without scanning anything first

Hands-On Exercises

Exercise 1

Build a schema with three columns — id (INTEGER), username (TEXT), score (INTEGER) — and encode/decode a row containing a negative score and a username with a non-ASCII character. Confirm every value round-trips exactly.

📄 View solution
Exercise 2

Encode a row with a single, genuinely empty TEXT column (an empty string). Confirm it round-trips correctly and inspect the raw encoded bytes directly — how many bytes does an empty string actually produce, and why is that a completely valid, unremarkable record rather than a special case?

📄 View solution
Exercise 3

Encode and decode a row with a single INTEGER column holding a negative value. Confirm it round-trips exactly, and explain what would go wrong if struct's own format code were changed from '>q' (signed) to '>Q' (unsigned).

📄 View solution

Chapter 2 Quick Reference

  • INTEGER: always exactly 8 bytes, signed (struct's own '>q') — no length prefix needed
  • TEXT: a 2-byte length prefix, followed by the real UTF-8-encoded bytes
  • Real bug found and fixed: using the CHARACTER count instead of the real UTF-8 BYTE count as a text field's own length prefix — invisible for pure ASCII, severely corrupting for any real multi-byte character
  • The consequence goes beyond the text field itself: a wrong length prefix misaligns the decoder's own read position for every field that follows it in the same row
  • Verified: mixed schemas, empty strings, and negative integers all round-trip exactly through the fixed encoder/decoder
  • Next chapter: Pages — packing several of these encoded records into a real, fixed-size, slotted disk page
Chapter 3 of 10

Pages: A Fixed-Size, Slotted Page Layout

Building a Database Engine: Storage & Query Fundamentals

Chapter 3 · Pages: A Fixed-Size, Slotted Page Layout

A single record, from Chapter 2, is just bytes floating in memory. A real database reads and writes disk in fixed-size chunks — pages — and packs many records into each one. Since records vary in length, a page can't simply lay them end to end at predictable offsets; it needs a real, separate slot directory tracking where each one actually lives.

Two Regions, Growing Toward Each Other

The classic, real design — used by SQLite, PostgreSQL, and most real database engines — grows two regions from opposite ends of one fixed-size page: a small slot directory grows forward from right after the header; the actual record bytes grow backward from the very end of the page. Whatever gap remains between them is the page's own free space.

PAGE_SIZE = 4096 # a real page size, matching a typical OS page (this chapter's own worked # examples use a deliberately tiny page to make the numbers easy to trace) HEADER_SIZE = 4 # a single 4-byte 'num_slots' field SLOT_SIZE = 8 # each slot: 4-byte offset + 4-byte length class Page: def __init__(self): self.data = bytearray(PAGE_SIZE) self.num_slots = 0 self.free_space_end = PAGE_SIZE # records are appended growing BACKWARD from here

A Real, Severe Bug: Forgetting the New Slot's Own Space

def add_record_naive(self, record_bytes): record_len = len(record_bytes) new_free_space_end = self.free_space_end - record_len slot_dir_end = HEADER_SIZE + self.num_slots * SLOT_SIZE # BUG: no +1 for the new slot if new_free_space_end < slot_dir_end: raise ValueError("page full") self.data[new_free_space_end:new_free_space_end + record_len] = record_bytes slot_offset = HEADER_SIZE + self.num_slots * SLOT_SIZE struct.pack_into('>II', self.data, slot_offset, new_free_space_end, record_len) self.free_space_end = new_free_space_end self.num_slots += 1

Reasonable-looking: check whether the record's own bytes fit in the gap between the slot directory and the record data. The bug: storing this record also requires one new slot entry, and the check never accounts for that entry's own SLOT_SIZE bytes.

Verified directly — a record's own first bytes get silently overwritten by a LATER slot entry
A tiny 64-byte page (HEADER_SIZE=4, SLOT_SIZE=8), four 8-byte records added in sequence: b'AAAAAAAA', b'BBBBBBBB', b'CCCCCCCC', b'DDDDDDDD'. All four are naively accepted with no error. Reading them back: the first three come back correct. The fourth comes back as b'\x00\x00\x00\x08DDDD' — its own first four bytes have been silently replaced by the encoded length field from a slot entry that was written into the exact space this record's own data was occupying. The naive check let the record's data claim space that the slot directory needed for its own final entry — and since add_record writes record data first, then the slot entry, the slot entry's own write simply overwrote part of what was just stored.
def add_record(self, record_bytes): record_len = len(record_bytes) new_free_space_end = self.free_space_end - record_len slot_dir_end = HEADER_SIZE + (self.num_slots + 1) * SLOT_SIZE # FIXED: +1 for the new slot if new_free_space_end < slot_dir_end: raise ValueError("page full") # ... unchanged from here
Verified directly — the fix correctly rejects the record that would have collided, instead of corrupting it
The identical sequence of four records through the fixed Page: the first three are accepted exactly as before. The fourth is correctly rejected with a clean ValueError("page full") — because there genuinely isn't room for both its own 8 bytes of data and the slot entry that would have to describe it. Every record that was accepted reads back byte-for-byte correct.

Where This Connects

This chapter's findingWhat it connects to
A slot directory and record data growing toward each other from opposite endsChapter 4's own heap table, which writes and reads whole pages like this one to and from a real file — each page is the real unit of I/O from here on
A capacity check that forgot the new slot's own spaceChapter 2's own text-length bug — the same class of mistake (a size calculation that's correct for the DATA but forgets a piece of BOOKKEEPING that also needs room) showing up one layer up the stack
A fixed-size page rejecting a record that genuinely doesn't fitChapters 5–6's own B-tree, whose own nodes are built on exactly this same fixed-capacity-per-page idea — a node splits precisely when it hits this same kind of real limit

Hands-On Exercises

Exercise 1

Create a fresh, empty Page() and check its own free_space(). Add a single 8-byte record and check free_space() again. Confirm the drop is 16 bytes, not 8, and explain exactly which two things together account for that difference.

📄 View solution
Exercise 2

Try to add a 100-byte record to a fresh 64-byte page. Confirm this is rejected cleanly with a real error, rather than silently truncating the record or corrupting the page, and explain why this case never even reaches the interesting "off by one slot" boundary the chapter's own main bug was about.

📄 View solution
Exercise 3

Add three small, genuinely different-length records (b'a', b'bb', b'ccc') to a fresh page. Confirm all three are accepted and every one reads back byte-for-byte correct, and explain why variable-length records specifically are what makes a fixed offset table (rather than a slot directory storing real offsets) impossible to use here.

📄 View solution

Chapter 3 Quick Reference

  • A page: a fixed-size byte buffer with a slot directory growing forward from the header and record data growing backward from the end
  • A slot: a small, fixed-size entry (offset + length) describing exactly where one record's own data lives within the page
  • Real bug found and fixed: checking whether a record fits without accounting for the ONE NEW slot entry needed to describe it — verified silently overwriting a record's own first bytes with part of that later slot entry
  • The fix: the fits-check adds +1 to the slot count before computing how much space the slot directory will actually need
  • Verified: a record that genuinely can't fit under any circumstances is rejected cleanly; small, differently-sized records all round-trip correctly within one page
  • Next chapter: A File-Backed Heap Table — writing and reading real pages like this one to and from an actual file on disk
Chapter 4 of 10

A File-Backed Heap Table

Building a Database Engine: Storage & Query Fundamentals

Chapter 4 · A File-Backed Heap Table

Every page built so far has lived and died inside a single Python session, in memory, never once touching a disk. This chapter is the first time that changes — a real file, real pages written to and read back from it, and a heap table: an unordered collection of pages that insert() and scan() can actually work with.

A Real Bug, Dormant Since Chapter 3 — and Exactly Where It Was Hiding

Chapter 3's own Page class defined HEADER_SIZE = 4, with a comment calling it "a single 4-byte 'num_slots' field." That comment was aspirational — the actual code never once wrote self.num_slots into those 4 bytes. It only ever updated a plain Python attribute on the Page object.

Verified directly — a page's own real record count evaporates the moment it's rebuilt from raw bytes
A page with two real records added, num_slots = 2. Its raw bytes, taken via bytes(page.data) — simulating "this page was just written to disk" — handed to a fresh Page() object with page.data set directly. The reloaded page's own num_slots: 0. The two records' own raw bytes are still physically present in data — get_record(0) and get_record(1) still happen to return the correct values, purely by coincidence — but the page itself has genuinely forgotten it has any records in it at all, and its own free_space_end has silently reset to the full, untouched page size.
Verified directly — the real consequence: the very next insert corrupts existing data
Adding a third record to that same "reloaded" page: because num_slots wrongly reads 0, the new record's own slot entry gets written at slot index 0 — directly overwriting the real slot entry that used to describe the first record. Reading slot 0 back afterward returns b'CCCCCCCC' — the third record — instead of the original b'AAAAAAAA'. The first record isn't just orphaned; its own description in the slot directory is gone.

The Fix: Actually Write What the Comment Always Promised

# inside add_record(), after self.num_slots += 1: struct.pack_into('>I', self.data, 0, self.num_slots) # NOW actually persisted def recompute_free_space_end(page): """The real record data always occupies the region from the SMALLEST stored slot offset up to PAGE_SIZE -- derived from the slot directory itself, once num_slots is correctly known. No second header field needed.""" if page.num_slots == 0: return PAGE_SIZE min_offset = PAGE_SIZE for i in range(page.num_slots): offset, length = struct.unpack_from('>II', page.data, HEADER_SIZE + i * SLOT_SIZE) min_offset = min(min_offset, offset) return min_offset def load_page(data_bytes): page = Page() page.data = bytearray(data_bytes) page.num_slots = struct.unpack_from('>I', page.data, 0)[0] # the REAL, persisted value page.free_space_end = recompute_free_space_end(page) return page
Verified directly — a real save/reload cycle now preserves everything correctly
The same two-record page, saved and reloaded via load_page(): num_slots = 2, free_space_end matches the original exactly. Adding a third record afterward: all three slots read back correctly — b'AAAAAAAA', b'BBBBBBBB', b'CCCCCCCC' — nothing overwritten.

A Real File, and a Working Heap Table

class HeapFile: def read_page(self, page_num): self.file.seek(page_num * PAGE_SIZE) return load_page(self.file.read(PAGE_SIZE)) def write_page(self, page_num, page): self.file.seek(page_num * PAGE_SIZE) self.file.write(bytes(page.data)) self.file.flush() class HeapTable: def insert(self, values): record = encode_row(self.schema, values) n = self.heap_file.num_pages() if n > 0: page = self.heap_file.read_page(n - 1) # try the LAST page first try: slot = page.add_record(record) self.heap_file.write_page(n - 1, page) return (n - 1, slot) except ValueError: pass # full -- fall through to a new page page_num = self.heap_file.allocate_page() page = self.heap_file.read_page(page_num) slot = page.add_record(record) self.heap_file.write_page(page_num, page) return (page_num, slot) def scan(self): for page_num in range(self.heap_file.num_pages()): page = self.heap_file.read_page(page_num) for slot in range(page.num_slots): yield decode_row(self.schema, page.get_record(slot))
Verified directly — real rows, through a real file, chained across Chapters 2, 3, and 4
Three rows — including one with a real non-ASCII text value — inserted into a genuine HeapTable backed by an actual file: scan() returns [[1, 'Alice'], [2, 'Bob'], [3, 'café owner']], exactly matching what was inserted. insert()'s own "try the last page first" logic is verified too: enough rows to force a real second page allocation land correctly on page 1 once page 0 genuinely fills up — scan() still visits every row, across every page, in the right order.

Where This Connects

This chapter's findingWhat it connects to
A header field documented in Chapter 3 but never actually written until nowCourse 1's own Declaration.property-vs-.name capstone finding, and Course 2's own text-doesn't-contribute-height finding — a recurring shape of bug across both projects: something correct in isolation, only found once a LATER chapter actually exercises the gap between what was documented and what was implemented
A page's own bookkeeping surviving a real save/reload cycleChapters 5–6's own B-tree, whose own nodes are pages too — every one of them will need this exact same real persistence to survive being written to disk and read back
"Try the last page first" before allocating a new oneChapter 1's own opening finding — the naive full-file-rewrite approach wasted enormous effort; blindly allocating a fresh page for every insert would waste enormous disk space the same way, leaving every earlier page's own remaining free space forever unused

Hands-On Exercises

Exercise 1

Create a brand-new, empty HeapFile and check num_pages(). Call allocate_page() once and check num_pages() again. Confirm the counts are exactly what an empty file, then a file with one real page, should report.

📄 View solution
Exercise 2

Insert three small rows into a fresh HeapTable and inspect the (page_num, slot) row IDs insert() returns for each one. Confirm all three land on the same page, and explain which specific part of insert()'s own logic is responsible for that.

📄 View solution
Exercise 3

Insert 15 rows, each large enough that several real pages end up being used. Confirm scan()'s own output matches the original insertion order exactly, from the very first row to the very last, regardless of how many pages the rows actually ended up spread across.

📄 View solution

Chapter 4 Quick Reference

  • HeapFile: a real file, organized as fixed-size PAGE_SIZE blocks — page N lives at byte offset N * PAGE_SIZE
  • Real bug found and fixed: Chapter 3's own page header was always documented as storing num_slots, but the code never actually wrote it there — a page reloaded from real bytes forgets its own record count, and the next insert overwrites the first record's own slot entry
  • The fix: persist num_slots into the header on every insert; derive free_space_end from the slot directory itself on reload, with no second header field needed
  • HeapTable.insert(): tries the last existing page first, only allocating a genuinely new one once the last page is actually full
  • HeapTable.scan(): visits every row across every page, in insertion order, decoding each one via Chapter 2's own real record format
  • Next chapter: B-Tree Indexes — real search, replacing the linear scan Chapter 1 already measured as the true bottleneck
Chapter 5 of 10

B-Tree Indexes: Structure & Search

Building a Database Engine: Storage & Query Fundamentals

Chapter 5 · B-Tree Indexes: Structure & Search

Chapter 1 measured the real cost of a linear scan: a worst-case lookup needs a comparison against every row already stored. This chapter builds the real alternative — a genuine B-tree node structure, and the search algorithm that walks it. Balanced insertion and node splitting are Chapter 6's own job; this chapter assumes a tree already exists, and gets its own search exactly right.

A Real Node: Every Level Holds Real Data

class BTreeNode: def __init__(self, leaf=True): self.leaf = leaf self.keys = [] # sorted list of keys self.values = [] # values[i] pairs with keys[i] -- EVERY node, leaf or # internal, stores real (key, value) pairs directly self.children = [] # internal nodes only; len == len(keys) + 1

This is the classic B-tree design (not a B+tree) — an internal node isn't just a signpost pointing further down; it genuinely holds real key-value pairs of its own, alongside pointers to child subtrees holding everything in between.

The Real Search Invariant

def btree_search(node, key): i = 0 while i < len(node.keys) and key > node.keys[i]: i += 1 if i < len(node.keys) and key == node.keys[i]: return node.values[i] if node.leaf: return None return btree_search(node.children[i], key)

children[i] always holds every key strictly between keys[i-1] and keys[i] — with children[0] holding everything smaller than keys[0], and children[len(keys)] holding everything larger than the last key. After the while loop finishes, i is already the correct child index — not i-1.

A Real, Plausible Bug: The Wrong Child Index

Verified directly — and one direction of it hits Python's own negative-index wraparound
A plausible mistake: reasoning "i keys were smaller than the target, so the target belongs in the (i-1)th child" — descending into children[i - 1] instead of children[i]. A real, small tree: root keys [10, 20], three children (keys <10, between 10 and 20, and >20). Searching for 5: i ends at 0, so the buggy version descends into children[-1] — which Python silently interprets as the last child (the one holding keys >20), via the exact same negative-index wraparound Course 2's own rasterizer chapter found in a completely different context. Searching for 15: i ends at 1, so the buggy version descends into children[0] — a real, valid child, just the wrong one. Both cases: a key that's genuinely stored in the tree comes back as None.
Verified directly — the fix finds every key, whether at the root or in a leaf
All ten real keys in that same tree — three in the left child, three in the middle child, two in the right child, and two directly in the root itself — are found correctly by children[i]. Genuinely absent keys (6, between two real keys; 0 and 100, past either end) all correctly return None too — the tree doesn't just avoid crashing, it correctly distinguishes presence from absence.

Verified Against a Real Linear Scan, at Scale

Verified directly — zero disagreements across 500 real keys, and 50 genuinely absent ones
A tree bulk-loaded from 500 real, randomly-sampled keys, checked against Chapter 1's own linear scan: every single one of the 500 keys returns the identical value from both approaches. 50 genuinely absent keys checked separately: both approaches agree they're missing, every time. The B-tree isn't just faster in principle — it's verified to answer exactly the same question a linear scan answers, just far fewer comparisons at a time.

Where This Connects

This chapter's findingWhat it connects to
A negative-index off-by-one in child selectionCourse 2's own real rasterizer chapter — the exact same class of Python-specific silent misdirection (a negative index quietly meaning "the last element" instead of raising an error) showing up in a genuinely different data structure
Search verified to exactly match a linear scan, at real scaleChapter 1's own opening finding — this chapter is the direct payoff: the same 500 keys that would need up to 500 comparisons in the worst case with a linear scan are found by the B-tree in a small fraction of that
Every node, leaf or internal, storing real dataChapter 6's own real insertion and node-splitting — this chapter's own bulk-load is a legitimate but simplified stand-in; real, balanced growth of the tree over time is that chapter's entire subject

Hands-On Exercises

Exercise 1

Bulk-load a tree from just three sorted pairs — fewer than one leaf's own capacity. Confirm the resulting tree is a single leaf node, with no internal/root node at all, and that btree_search() still correctly finds every one of the three keys.

📄 View solution
Exercise 2

Using the chapter's own hand-built three-child tree, confirm that both boundary keys stored directly in the root (10 and 20) are found without the search ever needing to descend into a child at all — trace through btree_search's own logic to show exactly where the function returns for each one.

📄 View solution
Exercise 3

Reproduce this chapter's own bug directly: run both btree_search and btree_search_buggy against the hand-built tree for the key 15. Confirm the two disagree, and trace exactly which child each version ends up descending into, and why those are two genuinely different (both real) subtrees.

📄 View solution

Chapter 5 Quick Reference

  • BTreeNode: every node — leaf or internal — stores real (key, value) pairs directly; internal nodes also carry children, one more than the number of keys
  • The search invariant: children[i] holds everything between keys[i-1] and keys[i] — after the search loop, i is already the correct child index
  • Real bug found and fixed: descending into children[i-1] instead of children[i] — for i=0 this hits Python's own negative-index wraparound; for i>0 it simply picks a real but wrong subtree
  • Verified: zero disagreements against a real linear scan across 500 real keys and 50 genuinely absent ones
  • Scope note: this chapter's own bulk-load is a simplified stand-in — real, balanced insertion and node splitting is Chapter 6's entire subject
  • Next chapter: B-Tree Indexes: Insertion & Node Splitting — keeping the tree balanced as real data grows
Chapter 6 of 10

B-Tree Indexes: Insertion & Node Splitting

Building a Database Engine: Storage & Query Fundamentals

Chapter 6 · B-Tree Indexes: Insertion & Node Splitting

Chapter 5 assumed a tree already existed. This chapter builds it for real — inserting one key at a time, keeping every node within its own real capacity, and splitting whenever that capacity is exceeded, with the split propagating upward exactly as far as it needs to.

Insert, Then Split If Needed

MAX_KEYS = 3 # a node splits once it holds MORE than this many keys def insert_into_node(node, key, value): # ... find the right position, insert into a leaf or recurse into a child ... if len(node.keys) > MAX_KEYS: return split_node(node) # returns (promoted_key, promoted_value, new_right) return None def btree_insert(root, key, value): result = insert_into_node(root, key, value) if result is None: return root promoted_key, promoted_value, new_right = result new_root = BTreeNode(leaf=False) # the ROOT itself split -- height grows by one new_root.keys = [promoted_key] new_root.values = [promoted_value] new_root.children = [root, new_right] return new_root

When a node overflows, it returns a signal — a promoted key and a brand-new right sibling — to whichever caller inserted into it. That caller absorbs the promotion into its own keys, possibly overflowing in turn. If the overflow reaches all the way to the root, btree_insert itself creates a genuinely new root, and the tree grows one level taller.

A Real, Severe Bug: One Split Boundary Isn't Enough

def split_node(node): mid = len(node.keys) // 2 promoted_key = node.keys[mid] promoted_value = node.values[mid] right = BTreeNode(leaf=node.leaf) right.keys = node.keys[mid + 1:] right.values = node.values[mid + 1:] if not node.leaf: right.children = node.children[mid + 1:] # children need a DIFFERENT boundary node.keys = node.keys[:mid] node.values = node.values[:mid] if not node.leaf: node.children = node.children[:mid + 1] # than keys/values do return (promoted_key, promoted_value, right)

A node with k keys always has k+1 children — one more, always. Splitting keys and values at index mid is correct; splitting children at the same index mid is a genuinely plausible mistake that looks consistent, and is wrong.

Verified directly — the SAME real tree, built two ways, fails in TWO different modes
20 real keys, inserted sequentially into a fresh tree with MAX_KEYS = 3, correctly build a real, 3-level, 10-node tree — every key found correctly. The identical 20 keys, inserted with a splitter that uses mid as the children boundary instead of mid + 1: searching for keys 7 and 8 crashes outright with a real IndexError. Searching for keys 10, 11, and 13 returns the wrong value entirely — pulled from a completely different, unrelated subtree. The bug's own root cause is a single one: an internal node's own child at index mid — which correctly belongs to the left side, holding every key between the left node's own last remaining key and the promoted key — gets assigned to the right side instead. The left node ends up with one fewer child than its own key count actually requires, which is exactly severe enough to make some searches crash and others simply go looking in the wrong place.
Verified directly — the correctly-split tree finds every key, at real scale and in real random order
The same 20-key tree, correctly split: every key found. 50 keys inserted in a genuinely shuffled, non-sequential order: every key still found — insertion order has no bearing on correctness. Re-inserting an already-present key updates its value in place, with the tree's own node count completely unchanged, confirming no duplicate entry is ever created.

Where This Connects

This chapter's findingWhat it connects to
Two genuinely different counts (keys vs. children) needing two different split boundariesChapter 3's own slotted-page bug — a capacity check that forgot the slot directory needs its own, separate accounting from the record data it describes; the same class of "one number isn't enough" mistake, one layer up
A single root cause producing two visibly different failure symptomsChapter 5's own children[i-1] bug, and Course 2's own bounds-clipping rasterizer bug — a recurring pattern across this whole "ambitious learning projects" tier: the same underlying mistake manifesting as a crash in one case and a silently wrong answer in another, depending on exactly which values happen to be involved
The tree's own height growing only when the root itself splitsChapter 1's own real log₂(n) comparison — this is precisely the mechanism that keeps a B-tree's own height logarithmic in the number of keys, rather than growing with every single insert

Hands-On Exercises

Exercise 1

Insert 50 keys, in a genuinely shuffled (not sequential) order, into a fresh tree. Confirm every one of the 50 keys is found correctly afterward, and explain why insertion order shouldn't matter for a correctly-implemented B-tree's own final correctness, even though it can affect the tree's own exact shape.

📄 View solution
Exercise 2

Insert keys 1 through 10 into a fresh tree, note the total node count, then insert key 5 a second time with a different value. Confirm the node count is completely unchanged, and confirm the stored value for key 5 reflects the second insert, not the first.

📄 View solution
Exercise 3

Build the tree's own height at five different real data sizes — 1, 5, 15, 40, and 100 keys. Confirm the height doesn't grow smoothly with every insert, and identify roughly how many keys it actually takes to push the height from one level to the next.

📄 View solution

Chapter 6 Quick Reference

  • Insertion: find the correct leaf (same descent logic as search), insert in sorted order, then split if the node now exceeds MAX_KEYS
  • Splitting: the median key is promoted to the parent; keys/values split at mid, children split at mid + 1 — a genuinely different boundary, since a node always has one more child than keys
  • Real bug found and fixed: using mid for both splits — verified producing two distinct failure modes on the same real tree: some searches crash with IndexError, others silently return a wrong value from an unrelated subtree
  • Root splitting: the one case that grows the tree's own height — a brand-new root is created only when the split propagates all the way up
  • Verified: insertion order doesn't affect final correctness; re-inserting an existing key updates it in place with no duplication; height grows only occasionally, not with every insert
  • Next chapter: A Small SQL-Like Language — tokenizing and parsing a real, if deliberately small, query grammar
Chapter 7 of 10

A Small SQL-Like Language: Tokenizing & Parsing

Building a Database Engine: Storage & Query Fundamentals

Chapter 7 · A Small SQL-Like Language: Tokenizing & Parsing

Every chapter so far has been driven directly, in Python, by calling functions like table.insert(...). Real users type queries. This chapter builds a real, if deliberately small, tokenizer and parser for a genuine SQL-like grammar — CREATE TABLE, INSERT INTO ... VALUES, and SELECT * FROM ... WHERE — turning query text into real, structured statement objects.

Tokens, Then Statements

KEYWORDS = {'CREATE', 'TABLE', 'INSERT', 'INTO', 'VALUES', 'SELECT', 'FROM', 'WHERE', 'AND', 'INTEGER', 'TEXT'} class Token: def __init__(self, kind, text): self.kind = kind # 'KEYWORD' | 'IDENT' | 'NUMBER' | 'STRING' | 'OP' | 'PUNCT' self.text = text

The tokenizer scans identifiers/keywords (case-insensitive keyword matching, original-case identifiers), numbers, single-quoted strings, punctuation, and comparison operators. The parser is a real, hand-written recursive-descent parser: one function per statement type, each consuming exactly the tokens its own grammar rule expects.

A Real, Severe Bug: Multi-Character Operators Need a Lookahead

if ch in '=<>!': tokens.append(Token('OP', ch)) # BUG: no lookahead at all i += 1

Every real SQL dialect needs >=, <=, and != — genuinely common WHERE-clause operators, not exotic edge cases. Treating every operator character as its own token, with no lookahead, splits every one of these into two separate tokens.

Verified directly — and the failure is worse than a crash: it's a silently WRONG statement
"SELECT * FROM users WHERE age >= 18;", tokenized naively: >= becomes two separate tokens, OP('>') and OP('='). Parsing this: parse_select()'s own op = self.expect('OP').text consumes > as the operator — correctly, as far as it knows. Then val_tok = self.advance() consumes the leftover = token as if it were the WHERE clause's own value — advance() never checks a token's own kind, so an operator token is silently accepted in a position that should only ever hold a number or a string. The parser doesn't crash at all: it confidently returns SelectStatement('users', ('age', '>', '=')) — a real, wrong statement, comparing age against the literal string '='. The real value, NUMBER('18'), and the closing ;, are left completely unconsumed, discarded without a single complaint.
if ch in '=<>!': if i + 1 < n and sql[i + 1] == '=': tokens.append(Token('OP', ch + '=')) # FIXED: recognize the real two-character operator i += 2 else: tokens.append(Token('OP', ch)) i += 1
Verified directly — the fix generalizes cleanly to every affected operator
The same real query, fixed tokenizer: a single OP('>=') token, and the WHERE clause parses cleanly to ('age', '>=', 18). The identical lookahead logic — one shared check, not three separate special cases — also correctly handles <= and !=, verified independently on both.

Where This Connects

This chapter's findingWhat it connects to
A silently wrong parse, not a crashChapter 5's own wrong-child B-tree bug and Chapter 6's own split-boundary bug — a recurring theme across this course: the more dangerous failures are the ones that produce a confidently wrong answer, not the ones that raise an obvious error
A parser that never re-tokenizes string content as keywordsCourse 1's own real HTML tokenizer — the same discipline of treating quoted/delimited content as an opaque, unconditional unit, regardless of what it happens to contain
Real, structured statement objects, ready to be executedChapter 8's own query execution — CreateTableStatement, InsertStatement, and SelectStatement are the direct input; this chapter's whole job was producing something the next one can actually act on

Hands-On Exercises

Exercise 1

Tokenize and parse two WHERE clauses using <= and !=, using both the naive and the fixed tokenizer. Confirm the naive version produces two separate OP tokens in both cases, and the fixed version produces exactly one correctly-recognized operator token in both cases.

📄 View solution
Exercise 2

Parse "SELECT * FROM users;" — a real, valid query with no WHERE clause at all. Confirm it parses successfully with where set to None, and explain exactly which check in parse_select() is responsible for the WHERE clause being genuinely optional.

📄 View solution
Exercise 3

Parse an INSERT statement whose own string value contains real SQL keyword text, e.g. 'SELECT * FROM WHERE'. Confirm the value comes back as one intact string, not as separate keyword tokens, and explain exactly which part of the tokenizer's own logic guarantees this regardless of what text appears inside the quotes.

📄 View solution

Chapter 7 Quick Reference

  • Six token kinds: KEYWORD, IDENT, NUMBER, STRING, OP, PUNCT
  • Three real statement types: CREATE TABLE, INSERT INTO ... VALUES, SELECT * FROM ... WHERE (optional)
  • Real bug found and fixed: no lookahead for multi-character operators splits >=/<=/!= into two tokens — the parser doesn't crash, it silently accepts the leftover token as the WHERE clause's own value, producing a confidently wrong statement
  • The fix: a single, shared lookahead check before committing to a one-character operator token
  • Verified: the WHERE clause is genuinely optional; string literals are never re-tokenized as keywords, regardless of what they contain
  • Next chapter: Query Execution — turning these real, parsed statements into real results over a real heap table
Chapter 8 of 10

Query Execution: From a Parsed Query to Real Results

Building a Database Engine: Storage & Query Fundamentals

Chapter 8 · Query Execution: From a Parsed Query to Real Results

Chapter 7 produced real, structured statement objects. This chapter is where they actually do something — a real Database class that creates real tables, inserts real rows, and answers real SELECT queries by scanning and filtering.

Three Statements, Three Real Actions

class Database: def execute(self, sql): stmt = Parser(tokenize(sql)).parse_statement() if isinstance(stmt, CreateTableStatement): return self._execute_create(stmt) elif isinstance(stmt, InsertStatement): return self._execute_insert(stmt) elif isinstance(stmt, SelectStatement): return list(self._execute_select(stmt)) def _execute_select(self, stmt): schema, table = self.tables[stmt.table_name] column_names = [name for name, col_type in schema.columns] for row in table.scan(): if stmt.where is not None: col_name, op, where_value = stmt.where idx = column_names.index(col_name) # find the column BY NAME if not apply_where(row[idx], op, where_value): continue yield row

CREATE TABLE registers a schema and a real file-backed HeapTable. INSERT calls table.insert() directly. SELECT scans every row, and — if a WHERE clause is present — finds the named column's own position in the schema and runs a real comparison against it.

A Real, Sharp Bug: SQL's "=" Isn't Python's "="

def apply_where_naive(row_value, op, where_value): expr = f"{row_value!r} {op} {where_value!r}" return eval(expr) # BUG: builds a Python expression string, generically, for ANY op

A plausible shortcut: rather than writing out a real comparison for each of six operators, just splice the operator string straight into a Python expression and let eval() handle it.

Verified directly — the single most common WHERE clause pattern breaks immediately
apply_where_naive(5, '=', 5) builds the string "5 = 5" and hands it to eval(). Result: SyntaxError: invalid syntax. Python's own = is assignment, not comparison — eval() only ever accepts real expressions, never assignment statements. SQL's own equality operator, spelled the exact same way as Python's assignment operator, breaks the naive dispatch on contact — and equality is, by a wide margin, the single most common comparison in any real WHERE clause. Run through the full Database pipeline, the exact same real query — SELECT * FROM users WHERE age = 30; — fails with the identical SyntaxError, confirming this isn't just an isolated unit-test finding.
OPS = { '=': lambda a, b: a == b, '!=': lambda a, b: a != b, '>': lambda a, b: a > b, '<': lambda a, b: a < b, '>=': lambda a, b: a >= b, '<=': lambda a, b: a <= b, } def apply_where(row_value, op, where_value): return OPS[op](row_value, where_value) # FIXED: a real dispatch table, no eval() at all
Verified directly — a real, complete database, CREATE through a real WHERE filter
A real table created, three real rows inserted, then queried: WHERE age >= 18 correctly returns the two adults; WHERE name = 'Bob' correctly returns exactly Bob's own row; WHERE name != 'Alice' correctly excludes exactly one row, keeping the rest. A WHERE clause matching nothing at all correctly returns a real, empty list — not an error, not None.

Where This Connects

This chapter's findingWhat it connects to
eval() as a generic dispatch shortcut, breaking on the most common caseA genuinely real, well-known anti-pattern in real software — splicing untrusted or loosely-controlled text into eval() is both a correctness risk (as verified here) and, in a genuinely adversarial context, a security risk; a real dispatch table sidesteps both at once
Finding a column by name, not by assumed positionChapter 2's own Schema — decode_row() returns a plain list with no names attached at all; this chapter is what reconnects a value back to the column name a user actually typed
A complete, working pipeline: parse → execute → real resultsChapter 9's own index-aware query planning — this chapter always does a full table scan; the next one adds the choice to use a B-tree index instead, when one genuinely helps

Hands-On Exercises

Exercise 1

Build a second Database instance using apply_where_naive instead of the fixed dispatch table, create the same table, insert one row, and run SELECT * FROM users WHERE age = 30; through it. Confirm it fails with the same real error the isolated apply_where_naive test produced.

📄 View solution
Exercise 2

Run WHERE name != 'Alice' against the chapter's own three-row table. Confirm it returns exactly the two rows that don't match, and explain why this is a genuinely different result from what WHERE name = 'Alice' returns, not simply its logical opposite computed after the fact.

📄 View solution
Exercise 3

Run a WHERE clause that matches zero rows against the chapter's own table (e.g. WHERE age > 100). Confirm the result is a real, empty Python list, and trace through _execute_select's own generator to explain exactly why zero matches never becomes an error or a None.

📄 View solution

Chapter 8 Quick Reference

  • Database.execute(): parses SQL text (Chapter 7), then dispatches on the real statement type to a real action
  • SELECT execution: a full scan (Chapter 4) plus an optional WHERE filter, resolving the named column to its own index in the schema
  • Real bug found and fixed: dispatching WHERE operators through eval() breaks on SQL's own = — Python's = is assignment, not comparison, so eval() raises a SyntaxError on the single most common WHERE pattern there is
  • The fix: a real dictionary of operator functions — no string splicing, no eval(), at all
  • Verified: a complete real pipeline — CREATE, INSERT, and SELECT with a real WHERE clause — working end to end, including a genuinely empty result set
  • Next chapter: Using the Index — choosing a B-tree lookup over a full scan when a WHERE clause genuinely allows it
Chapter 9 of 10

Using the Index: Basic Query Planning

Building a Database Engine: Storage & Query Fundamentals

Chapter 9 · Using the Index: Basic Query Planning

Every piece is built: real storage, a real B-tree, a real parser, a real executor. This chapter wires the last connection — an index, built from a real table, and a real (if deliberately minimal) planner deciding when it's actually safe to use it.

Building an Index: Real Locations, Keyed by Real Values

def create_index(self, table_name, column_name): schema, table = self.tables[table_name] idx = [name for name, t in schema.columns].index(column_name) root = BTreeNode(leaf=True) for row, location in table.scan_with_locations(): # real (page_num, slot) per row root = btree_insert(root, row[idx], location) self.indexes[(table_name, column_name)] = root

scan_with_locations() is Chapter 4's own scan(), extended to also yield each row's own real (page_num, slot) — the exact row ID HeapTable.insert() already returns. The index maps column values to real, physical locations, using Chapter 6's own real btree_insert(), unmodified.

A Real, Severe Bug: An Index Can't Safely Answer Every Operator

def choose_plan_naive(where, indexed_columns): col, op, value = where if col in indexed_columns: return ('index', col, value) # BUG: ignores op entirely return ('scan', None, None)

Reasonable-looking: if there's an index on the column, use it. The problem: Chapter 5's own btree_search() only ever finds an exact match for one key — it has no way to answer "everything greater than 18."

Verified directly — a range query silently loses almost every row that should have matched
10 real rows, unique ages, indexed on age. WHERE age > 18 should return 8 rows. The naive planner, seeing an index on age, unconditionally uses it: btree_search(root, 18) finds exactly one row — the one with age exactly 18 — and returns that single row, silently discarding all seven others that genuinely satisfy age > 18. No error, no warning — a confidently wrong, drastically incomplete result set.
def choose_plan(where, indexed_columns): col, op, value = where if op == '=' and col in indexed_columns: # FIXED: only for genuine equality return ('index', col, value) return ('scan', None, None)
Verified directly — the fix falls back to a correct full scan for anything the index can't safely answer
The same real query, fixed planner: WHERE age > 18 correctly falls back to a full scan, returning all 8 real matching rows. WHERE age = 30 — a genuine equality — correctly uses the index, and its result count matches a manual scan count exactly: one row, either way.

A Second, Honest Finding: This B-Tree Only Ever Stores One Value Per Key

Verified directly — a genuinely real, out-of-scope limitation, not a bug this chapter fixes
A fresh table, five rows, three of them sharing points = 10. The real scan finds all three. The index, built the same way, finds only one — Chapter 6's own btree_insert() treats re-inserting an existing key as an update (node.values[i] = value), never as "add a second entry." Every earlier row sharing a duplicate key value is silently, permanently unreachable through the index — only the last one inserted survives. A real, non-unique/multi-value index is a genuinely separate feature, deliberately out of this chapter's own scope — the practical consequence: only ever build an index on a column with genuinely unique values.

Where This Connects

This chapter's findingWhat it connects to
An index safe for equality, unsafe for range conditionsChapter 1's own real motivation for building an index at all — the fix doesn't remove the index's own real value, it just scopes when it's honest to trust it
A B-tree storing one value per keyChapter 6's own real re-insert-as-update behavior, verified there as a deliberate, correct property — this chapter shows the same property has a real, honest cost once it's used for something other than a genuinely unique key
A real planner choosing between two real execution strategiesChapter 10's own capstone — every piece built across this course, now including the choice of HOW to answer a query, not just whether it can be answered at all

Hands-On Exercises

Exercise 1

Run WHERE age = 30 against the chapter's own real table two ways: once via db.select() (using the index), and once by manually counting matches from a plain table.scan(). Confirm the two counts agree exactly.

📄 View solution
Exercise 2

Call choose_plan() directly with a WHERE clause on a column that has no index at all (only 'age' is indexed). Confirm the plan is always ('scan', None, None), regardless of the operator used.

📄 View solution
Exercise 3

Build a fresh table with a column holding genuine duplicate values (three rows sharing the same value), index that column, and compare a real scan's own match count against the index lookup's own result count for that shared value. Confirm they disagree, and explain exactly which row survives in the index.

📄 View solution

Chapter 9 Quick Reference

  • create_index(): scans a table once, building a real B-tree mapping column values to real (page_num, slot) locations
  • Real bug found and fixed: using an index for ANY operator, not just equality — a plain B-tree exact-match search silently drops nearly every row for a real range query like >
  • The fix: the planner only chooses the index when the operator is genuinely =; every other operator falls back to a correct full scan
  • An honest, separate limitation: this course's own B-tree stores one value per key — indexing a column with real duplicates silently keeps only the last-inserted row per key; only index genuinely unique columns
  • Verified: index-based and scan-based results agree exactly for genuine equality queries, at real, checked row counts
  • Next chapter: Capstone — a single, working end-to-end engine, verified against hand-computed results
Chapter 10 of 10

Capstone — A Working Single-Table Engine

Building a Database Engine: Storage & Query Fundamentals

Chapter 10 · Capstone — A Working Single-Table Engine

Every chapter has tested its own piece in isolation, against hand-built inputs standing in for whatever the previous chapter was supposed to hand it. This chapter does what none of them did: run real SQL text through the actual tokenizer, parser, executor, storage engine, and index — the same functions, wired together — and check the results against what's actually correct.

A Real, Final Integration Bug

Wiring Chapter 8's own execute(sql) and Chapter 9's own index-aware select() into the same class, for the first time, surfaced something neither chapter's own tests ever could.

Verified directly — Chapter 9's own published Database class cannot run a single real SQL string
Chapter 8 built a real execute(sql) — tokenize, parse, dispatch. Chapter 9, adding index support, quietly built its own create_table()/insert()/select() methods, called directly with Python values — and never once reconnected the SQL-parsing layer. Calling db.execute("SELECT * FROM products;") on Chapter 9's own class, exactly as published, raises a genuine AttributeError: 'DatabaseChapter9' object has no attribute 'execute'. Nothing in either chapter's own isolated tests was ever wrong — Chapter 8's execute() was tested against its own simpler, non-indexed class; Chapter 9's index-aware methods were tested by calling them directly. The two real capabilities were each verified correct, separately, and never actually run together until now.
class Database(DatabaseChapter9): """The real capstone class: Chapter 9's own create_table/insert/ create_index/select, PLUS Chapter 8's own real execute(sql) entry point -- reconnecting real SQL text parsing to real index-aware planning, which were never actually combined in one class before now.""" def execute(self, sql): stmt = Parser(tokenize(sql)).parse_statement() if isinstance(stmt, CreateTableStatement): self.create_table(stmt.table_name, stmt.columns) return None elif isinstance(stmt, InsertStatement): return self.insert(stmt.table_name, stmt.values) elif isinstance(stmt, SelectStatement): return self.select(stmt.table_name, stmt.where) # index-aware, for real

A Real, Complete Engine — Verified End to End

A real product inventory: CREATE TABLE products (id INTEGER, name TEXT, price INTEGER, category TEXT);, five real rows, an index on id.

Verified directly — a real equality query, through real SQL text, correctly uses the index
db.execute("SELECT * FROM products WHERE id = 3;") — tokenized, parsed into a real SelectStatement, planned via Chapter 9's own choose_plan() (index, since the operator is genuine equality and id is indexed), executed via btree_search() — returns exactly [[3, 'Gizmo', 15, 'hardware']].
Verified directly — a real range query correctly falls back to a scan, and an unindexed equality correctly scans too
WHERE price > 20: three matching rows, correctly found via a full scan (Chapter 9's own operator check correctly refuses to trust the index for a non-equality condition). WHERE category = 'electronics': two matching rows, correctly found via a full scan too — category was never indexed, so choose_plan() correctly falls back regardless of the operator being a genuine equality.

What This Course Doesn't Cover

Restating the scope drawn back in Chapter 1, now that every piece of it has actually been built: no client-server networking protocol, no full SQL (a genuine but deliberately small subset — CREATE TABLE/INSERT/SELECT/WHERE only, no UPDATE, no DELETE, no JOIN, no CREATE INDEX as SQL syntax), no distributed or replicated storage, no cost-based query optimizer beyond the single honest heuristic built in Chapter 9. Beyond that original list, building this course surfaced two more, more specific boundaries worth naming honestly: this B-tree index only ever stores one value per key — a real limitation for any column with genuine duplicate values, found in Chapter 9 — and, as of this chapter, nothing in this engine survives a crash mid-write, no transaction can be rolled back, and nothing prevents two operations from corrupting each other if they ever ran concurrently. Every single chapter of this course has quietly assumed one operation runs at a time, uninterrupted, to completion.

Where This Connects: On to Course 2

Course 2, Building a Database Engine: Transactions & Concurrency, starts exactly here — write-ahead logging and crash recovery (so a real crash mid-write no longer loses or corrupts data), locking and MVCC (so two operations can safely run at the same time), multi-table support with foreign keys, and real joins. Every chapter in that course assumes this one's own finished engine as its starting point.

Course 1 Complete — Building a Database Engine: Storage & Query Fundamentals

  • Chapters 1-2: why a database engine matters (real, measured problems: O(N²) full-file rewrites, O(n) linear scans), and a real binary record format (with a severe UTF-8 byte-vs-character-count bug found and fixed)
  • Chapters 3-4: a real slotted page layout (with a slot-directory-space bug found and fixed) and a real file-backed heap table (with a dormant page-persistence bug found and fixed)
  • Chapters 5-6: a real B-tree — search (with a wrong-child-index bug found and fixed) and insertion with node splitting (with a children-vs-keys split-boundary bug found and fixed)
  • Chapters 7-8: a real SQL-like tokenizer and parser (with a multi-character-operator bug found and fixed) and real query execution (with an eval()-based WHERE-clause bug found and fixed)
  • Chapter 9: real index-aware query planning (with an operator-blind index-usage bug found and fixed, plus an honest unique-key-only limitation surfaced)
  • Chapter 10 (this chapter): every piece wired together for the first time on real SQL text — surfacing and fixing one final, genuine integration bug (a missing execute(sql) entry point) that no single chapter's own isolated tests could ever have caught
  • Nine real bugs, found and fixed, across ten chapters — every one verified with real, hand-run Python before being written up
  • Next: Building a Database Engine: Transactions & Concurrency — making this engine safe under crashes and concurrent access