Building Secondary Indexes

CREATE INDEX — Secondary B-Trees

Until now, the only column your engine could seek on efficiently is whatever it uses as the primary key/rowid. This lesson lets users declare a secondary index on any column, giving the query planner a fast path for lookups that don't touch the primary key at all.

The core idea: an index is just another B-tree

A secondary index is structurally the same B-tree you already built for the table's primary storage — it just maps a different key. Instead of rowid → row, it maps indexed_column_value → rowid:

CREATE INDEX idx_name ON users (name)

builds a B-tree keyed by name, where each leaf entry points at the rowid of the matching row in the underlying table:

B-tree keyed on `name`:
    "Alice" -> rowid 3
    "Bob"   -> rowid 1
    "Carol" -> rowid 7

To answer WHERE name = 'Alice', the planner now has an alternative to a full table scan: search this B-tree for "Alice" (O(log n)), get back rowid 3, then fetch that one row directly from the table (a single random-access lookup) instead of comparing every row's name column.

What you need to implement

1. Parse CREATE INDEX <idx_name> ON <table> (<column>) and respond OK.
2. Build the index eagerly at creation time: iterate every existing row in the table, insert (column_value, rowid) into a fresh B-tree, and register it (e.g. in a dict keyed by table name → column name → B-tree, or table name → index name).
3. Keep the index in sync going forward: every INSERT/UPDATE/DELETE on the indexed table needs a matching insert/update/delete in the index B-tree. An index that silently goes stale after the first write is a correctness bug, not just a performance one — a stale index can return wrong rows or miss rows entirely.
4. Wire it into the planner you built in the table-scan-vs-index-scan lesson: when a WHERE predicate references an indexed column, the planner should now choose the index scan path and report it via .explain:

.explain SELECT * FROM users WHERE name = 'Alice'
→ SEARCH TABLE users USING INDEX idx_name

Why "secondary" index specifically

"Primary" usually refers to the structure the table's rows are physically stored in (often the rowid/primary-key B-tree — this is what SQLite calls a "clustered" index). A secondary index is an additional structure layered on top, pointing back at the primary storage rather than holding the row data itself. That indirection is exactly why every secondary index lookup costs one extra hop (index seek, then row fetch) compared to a lookup that's serviced directly by the primary structure.

Edge cases to watch

• Creating an index on a table that doesn't exist, or on a column that doesn't exist, should be an error rather than silently creating garbage.
• Creating an index with a name that already exists — decide whether to reject or replace, and be consistent.
• Non-unique values: multiple rows can share the same indexed value (e.g. two users both named "Alice"), so each key in the index B-tree must be able to map to multiple rowids, not just one.
• Index maintenance cost is real: every write now touches N structures instead of 1 (the table plus each index on it) — this is the classic read/write tradeoff indices introduce, and it's why databases don't index every column by default.