Skip to content
Tutorials Center
My learning

Topics

Lesson 75 of 79 ยท Projects

Project: Build a Mini Database Engine

Build a tiny database engine in Python: paged heap storage, a B+ tree index, a small SQL parser and a write-ahead log that recovers after a crash.

You have spent this tutorial learning how database engines work from the outside: pages, indexes, parsers, logs. The best way to make that knowledge stick is to build a small engine yourself. In this project you will write about 250 lines of Python that store rows in pages, find them through a B+ tree, understand a small SQL dialect and survive a simulated crash by replaying a write-ahead log.

It is a toy, and it is honest about that: no concurrency, no variable-length records, no disk files, and almost no error handling. But every box in the architecture diagram from DBMS Architecture and Components will exist as a real class or function that you can run, print and break.

Four layers, built bottom up

Heap pages Rows live in fixed-size pages.
B+ tree Key to row id in a few node visits.
Parser SQL text becomes a small tree.
Write-ahead log Log first, then change data.

Each TryIt below runs on its own, and the last one combines everything.

1 / 2

Step 1: storage in pages

Real engines never read single rows from disk; they read pages (see Disks, Pages and the Buffer Pool). Our Heap class keeps a list of pages, each holding at most three rows so you can see the pages fill up. Inserting a row appends it to the last page, opening a new page when that one is full, and returns a row id (page, slot). A full scan visits every page; a fetch by row id touches exactly one. We count page reads, because I/O, not CPU, is what a real engine tries to save.

Step 2: a B+ tree index

A heap alone forces a scan for every lookup. The BPlusTree maps a key to a row id. Its leaves hold sorted keys and are chained together for range scans; inner nodes hold separator keys that guide a search downward. The only tricky operation is the split, covered in B-Trees and B+ Trees: when a node holds more than order keys, it breaks in the middle and the middle key moves up to the parent. If the root splits, the tree grows one level taller, which is the only way a B+ tree gets taller.

Python Heap pages plus a B+ tree index

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Read the output with the cost model in mind. The full scan touches every page of the heap. The index lookup walks three nodes (root, one inner node, one leaf) and then fetches one heap page. With twelve rows the difference is small; with twelve million rows the scan reads millions of pages while the lookup still walks only three or four nodes. The leaf chain answers range queries: after finding the start, the engine just follows next pointers without returning to the top.

Try changing order to 5 or adding more ids to the list, and watch the levels printout change. You will see leaves split, inner nodes split, and eventually a new root.

Step 3: a tiny SQL parser

Between a string and an operation sits the front end of the query processing pipeline. We write the two classic stages by hand:

  1. A tokenizer uses one regular expression to cut the text into numbers, quoted strings, operators, punctuation and words. Words are lower-cased, so SELECT and select are the same keyword.
  2. A recursive-descent parser has one method per statement (p_create, p_insert, p_select, p_delete). Each method consumes tokens in the order the grammar demands, raising a SyntaxError when the next token is wrong, and returns a plain dictionary: the abstract syntax tree.
Python From SQL text to a syntax tree

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Notice what the parser does not do. It never checks that books exists or that price is a column; that is the job of the executor, which consults the catalog. Keeping syntax and meaning apart is how every real engine is organized, and it is the reason the SELECT * FROM books WHERE error message talks about a missing word rather than a missing table.

Step 4: executor and write-ahead log

Now we connect the layers. The Database class owns the tables (heap plus index) and a log. Its rules are the heart of the project.

  • Log before data. Every change first appends a record to the log and only then calls apply. This is the write-ahead rule from Logging and Write-Ahead Logging. Our log is a Python list standing in for a file that is flushed to disk before the change happens.
  • Commit is a record. A transaction is durable once its commit record is in the log. Statements outside an explicit BEGIN run in their own automatic transaction.
  • One code path for changes. apply performs a logged change. Normal execution calls it after logging; recovery calls it while reading the log. Sharing it guarantees that replaying the log recreates exactly what the original run did.
  • Choosing a plan. matching looks at the WHERE clause. An equality test on the first column, our primary key, uses the B+ tree; anything else scans the heap. SELECT returns the plan's name next to the rows so you can see the optimizer's choice.
  • Recovery. After a crash, memory is gone but the log remains. recover finds the transactions that have a commit record and redoes their changes onto an empty database. A transaction with no commit record is ignored, which is atomicity in action: its half-finished work simply never reappears.
Python The complete mini engine, with a crash

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The output tells the whole story. Point lookups use the index, range-like conditions scan, and the duplicate key is rejected by the index before anything is logged as an insert. In the open transaction the delete and the new row are visible to the same session. Then the crash happens: the log has 19 records, but the open transaction has no commit, so recovery rebuilds exactly the four committed books. Dune is back, and the "never committed" row is gone.

This engine uses a no-steal, redo-only design: tables are never written to disk before commit, so recovery never needs to undo anything. Real engines allow dirty pages to reach disk early (steal) for speed, which is why they also log before-images and run an undo phase, as described in Failure Classification and Recovery Goals.

Where to go next

Each limitation below is an extension and a chance to apply a lesson from this tutorial.

  • Deletes in the tree. remove just deletes a key from a leaf. Add merging or redistribution so leaves never become nearly empty.
  • Secondary indexes. Let CREATE INDEX build a second tree on another column, and teach matching to choose it, using the cost ideas from Statistics, Cost Estimation and Plan Search.
  • More SQL. Add UPDATE, AND in WHERE, and ORDER BY. Each needs a parser rule and an executor case.
  • Checkpoints. The log grows forever. Write a checkpoint that snapshots the tables and lets recovery start from the snapshot (Checkpoints, ARIES and Backups).
  • Real files. Serialize pages to bytes with struct and write them with os.fsync. This is where the difference between "written" and "durable" becomes real.
  • Locking. Add a lock table and make two interleaved sessions behave serially (Two-Phase Locking).

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why does the engine write the log record before it applies a change?

    This is the write-ahead rule. If the data change were made first and the machine crashed before logging it, there would be no record to redo or undo the change.
  2. 2. In the final demo, why is the row 'Never committed' missing after recovery?

    That INSERT belonged to an explicit transaction that never reached COMMIT. Its log records exist, but recovery skips every transaction without a commit record, so the row never reappears.
  3. 3. When does the engine use the B+ tree instead of scanning the heap?

    The index is keyed on the first column, so only an equality test on that column can be answered by a tree lookup. Conditions such as price < 9 fall back to a full scan in this simple design.
  4. 4. What is the main advantage of the leaf chain (each leaf pointing to the next)?

    After one root-to-leaf search finds the start of a range, the engine follows next pointers through sorted leaves.

Summary

  • A small engine needs four layers: paged storage, an index, a parser and a log, and each can be written in a few dozen lines.
  • Pages are the unit of I/O, so the cost of an access is the number of pages it touches; an index turns a full scan into a handful of node visits.
  • A tokenizer and a recursive-descent parser turn SQL text into a syntax tree and never check whether tables exist; the executor does that.
  • The write-ahead rule (log first, then change) plus commit records let recovery redo committed work and ignore unfinished transactions.
  • Real engines add steal/no-force buffering, undo, checkpoints, concurrency control and variable-length records, all topics from earlier lessons.

Next: Project: A Normalization Toolkit.