CREATE INDEX — Secondary B-Trees

An index is a separate data structure that speeds up lookups on specific columns. Without an index, every query requires a full table scan. With an index, the engine can jump directly to matching rows.

How an Index Works

A secondary index is a B-tree that maps column values to rowids:

Table: users
+-------+--------+-----+
| rowid | name   | age |
+-------+--------+-----+
| 1     | Alice  | 30  |
| 2     | Bob    | 25  |
| 3     | Charlie| 35  |
+-------+--------+-----+

Index on name:
    [Bob]
   /     \
[Alice:1] [Charlie:3, Bob:2]

(B-tree with name→rowid mapping)

To find WHERE name = 'Bob':

1. Search the index B-tree for 'Bob' → rowid 2
2. Fetch rowid 2 from the table → (2, 'Bob', 25)

Two lookups instead of scanning every row.

CREATE INDEX Syntax

CREATE INDEX idx_name ON users (name)

This creates a new B-tree idx_name where:

• Keys are values from the name column
• Values are the corresponding rowids
• The tree is kept sorted by name

Maintaining the Index

Indexes must be kept in sync with the table:

INSERT INTO users VALUES ('Dave', 28)
→ Add to table (rowid=4)
→ Add ('Dave', 4) to idx_name

DELETE FROM users WHERE name = 'Bob'
→ Remove from table
→ Remove 'Bob' from idx_name

UPDATE users SET name = 'Robert' WHERE name = 'Bob'
→ Update table
→ Remove 'Bob' from idx_name, add ('Robert', 2)

Every write operation becomes more expensive because each index must also be updated.

Trade-offs

Indexes speed up reads but slow down writes. Choose wisely.

How SQLite Stores Indexes

Each SQLite index is a separate B-tree in the database file. The index B-tree's pages are interleaved with the table B-tree's pages. The sqlite_master table stores the CREATE INDEX statement, which is replayed on database open to register the index.

How PostgreSQL Stores Indexes

PostgreSQL indexes are stored in separate files from their tables. The CREATE INDEX command builds the B-tree by sorting all existing rows and bulk-loading them into pages. PostgreSQL also supports concurrent index creation (CREATE INDEX CONCURRENTLY) that doesn't lock the table.

Your Task

Implement CREATE INDEX to build a secondary B-tree. After creating an index, queries with WHERE on the indexed column should use it, and .explain should reflect this.