STAGE 5 · THE CARD CATALOG

The Card Catalog

A table is just a B-tree, and the list of tables is just another one.

What you're wiring up

So far the engine stores bytes to bytes. A database stores tables: named collections of typed rows. The move that makes this cheap is realizing you need no new storage machinery at all, only new opinions about keys and values.

A table is a B-tree keyed by primary key whose values are encoded rows. The catalog, the list of tables, is itself a table living in a tree at a well-known root page. A secondary index is one more tree, mapping an indexed column value to a primary key. Many trees share one file because each one only needs its own root page id, which is exactly what a catalog row stores.

The subtle work is encoding. Encode keys order-preserving, big-endian integers with the sign bit flipped and text with a terminator, and the tree's byte-wise sort becomes the semantic sort. Stage 3's cursors then hand you typed range scans for free.

# order-preserving key encoding
int64 -5  ->  7F FF FF FF FF FF FF FB
int64  5  ->  80 00 00 00 00 00 00 05
# byte comparison now agrees with numeric order

# secondary index entry
encode(colValue) + encode(pk)  ->  pk

Assembly steps

[ 01 ]

Write the row codec: encode and decode a row of typed values (int64, text, bool, null) as a type tag, a length and a payload per column.

hint

Property-test decode(encode(row)) equals row before wiring anything else. Codec bugs found later look exactly like tree bugs and eat an evening.

[ 02 ]

Make key encoding order-preserving: big-endian integers with the sign bit flipped, text as bytes plus a terminator.

hint

Property-test that a < b if and only if encode(a) < encode(b) over random pairs. That one test kills the subtlest bug class in this stage.

[ 03 ]

Build the catalog at a fixed root page: rows map a table name to its column definitions, primary key and root page id. CreateTable allocates a fresh empty tree and records it.

hint

The catalog cannot describe itself, so its own root page id is a compile-time constant. Every real database does a version of this bootstrap.

[ 04 ]

Add typed table operations (tinsert, tget, tscan) checked against the catalog, with clean errors on wrong arity or type and rejection of duplicate primary keys.

hint

Each of these is a five-line wrapper over Stage 2 and 3 calls on the right tree. If one grows large, you are rebuilding something you already own.

[ 05 ]

Add secondary indexes: createindex builds a tree of encoded column value plus primary key; inserts and deletes maintain the table and all its indexes inside one WAL transaction; tfind seeks the index and then fetches rows.

hint

One transaction is not a nicety here. The crash test for this stage exists purely to catch the half-updated version.

Go deeper (after it passes)

Pair this with DDIA on encoding and evolution. You just wrote a tiny Avro, and the awkward question of adding a column to a table full of old rows is the same question that chapter answers. Keep filling in docs/file-format.md; the catalog section is the one worth writing carefully.