How SQLite B-Tree Indexes Work and Why Indexes Trade Reads for Writes

Learning outcomes

Chapter 9 showed why every extra write has concurrency consequences. An index is one of those extra writes: it can make an important read path dramatically cheaper, but SQLite must also store and maintain that index whenever affected rows change. The right question is therefore not “should this column be indexed?” It is “which measured access pattern deserves an additional maintained B-tree?”

From prerequisite B-tree intuition to SQLite storage

You already know the abstract B-tree idea: sorted keys let an engine navigate toward a small key range instead of testing every row. SQLite makes this concrete. An ordinary rowid table is stored in a table B-tree keyed by its integer rowid. A separately declared SQL index is stored in an index B-tree. For a rowid table, an index entry contains the indexed key values plus enough row identity to reach the corresponding table row.

rowid table B-tree                     secondary index B-tree
------------------                     ----------------------
key = rowid                             key = indexed value(s), rowid
payload = row columns                   payload/key identifies table row

       SEARCH index                         table lookup (if needed)
            |                                      |
            v                                      v
   matching rowid(s) ----------------------> rowid table B-tree

Chapter 11 will inspect pages, interior/leaf cells, overflow, and file-format details. Here, this model is enough to explain why a non-covering secondary-index lookup may involve both an index traversal and one or more table lookups.

The first indexing rule: start from a query, not a column

Suppose FieldNotes frequently asks for all maintenance notes for one device. Without a supporting index on maintenance_note.device_id, SQLite may have to examine the whole table and test the predicate. A suitable index gives the planner another algorithm: navigate to the matching key range and visit only candidate entries. But the planner is cost-based; merely creating an index does not force it to use the index.

EXPLAIN QUERY PLANSELECT note_id, occurred_at, status, summaryFROM maintenance_noteWHERE device_id = 42;

On the chapter dataset before the index exists, the important plan word should be SCAN maintenance_note. Treat exact formatting as diagnostic output, not a stable interface.

CREATE INDEX idx_note_deviceON maintenance_note(device_id);EXPLAIN QUERY PLANSELECT note_id, occurred_at, status, summaryFROM maintenance_noteWHERE device_id = 42;

The important change is normally from SCAN to a SEARCH ... USING INDEX idx_note_device (device_id=?)-style access path.

Build the reusable FieldNotes planner database

The chapter uses enough rows to make access-path differences visible while remaining small and disposable. The SQL below defines the schema. A short Python seeder then creates 100 sites, 1,000 devices, and 30,000 maintenance notes with deliberately non-uniform status values.

PRAGMA foreign_keys = ON;DROP TABLE IF EXISTS maintenance_note;DROP TABLE IF EXISTS device;DROP TABLE IF EXISTS site;CREATE TABLE site(  site_id INTEGER PRIMARY KEY,  site_code TEXT NOT NULL UNIQUE,  name TEXT NOT NULL);CREATE TABLE device(  device_id INTEGER PRIMARY KEY,  site_id INTEGER NOT NULL REFERENCES site(site_id),  device_code TEXT NOT NULL UNIQUE,  kind TEXT NOT NULL,  active INTEGER NOT NULL DEFAULT 1 CHECK(active IN (0,1)));CREATE TABLE maintenance_note(  note_id INTEGER PRIMARY KEY,  device_id INTEGER NOT NULL REFERENCES device(device_id),  occurred_at TEXT NOT NULL,  status TEXT NOT NULL CHECK(status IN ('open','closed','deferred')),  priority INTEGER NOT NULL CHECK(priority BETWEEN 1 AND 5),  technician TEXT NOT NULL,  duration_min INTEGER NOT NULL CHECK(duration_min >= 0),  cost_cents INTEGER NOT NULL CHECK(cost_cents >= 0),  summary TEXT NOT NULL);

import sqlite3from pathlib import Pathpath = Path("fieldnotes-planner.db")path.unlink(missing_ok=True)con = sqlite3.connect(path)con.executescript(open("schema.sql", encoding="utf-8").read())con.executemany(    "INSERT INTO site(site_code,name) VALUES(?,?)",    [(f"SITE-{i:03d}", f"Operations Site {i:03d}") for i in range(1,101)])con.executemany(    "INSERT INTO device(site_id,device_code,kind,active) VALUES(?,?,?,?)",    [((i-1)%100+1, f"DEV-{i:05d}", ("pump","fan","sensor")[i%3], 0 if i%23==0 else 1)     for i in range(1,1001)])rows=[]for i in range(1,30001):    status = "open" if i%10==0 else ("deferred" if i%17==0 else "closed")    rows.append((        (i-1)%1000+1,        f"2026-{(i%8)+1:02d}-{(i%28)+1:02d}T{(i%24):02d}:{(i%60):02d}:00Z",        status, (i%5)+1, f"tech-{i%40:02d}", i%181, 500+(i%25000),        f"Routine field observation {i}"    ))con.executemany("""INSERT INTO maintenance_note(device_id,occurred_at,status,priority,technician,duration_min,cost_cents,summary)VALUES(?,?,?,?,?,?,?,?)""", rows)con.commit()print(con.execute("SELECT COUNT(*) FROM maintenance_note").fetchone()[0])  # 30000con.close()

CREATE INDEX, UNIQUE INDEX, and implicit indexes

An explicit index is a named schema object you create with CREATE INDEX. CREATE UNIQUE INDEX adds a uniqueness rule: two rows may not have equal non-NULL index keys, while SQLite treats NULL values as distinct for UNIQUE index purposes. Separately, SQLite may create persistent internal indexes to implement many UNIQUE and non-rowid PRIMARY KEY constraints.

Inspect what SQLite actually created

Schema introspection prevents accidental duplicate indexes and reveals whether an index came from your DDL or a constraint.

.indexes.schema device.schema maintenance_noteSELECT type, name, tbl_name, sqlFROM sqlite_schemaWHERE type = 'index'ORDER BY tbl_name, name;PRAGMA index_list('device');PRAGMA index_list('maintenance_note');PRAGMA index_xinfo('idx_note_device');

For an internal autoindex, the sql column in sqlite_schema is normally NULL because no independent CREATE INDEX statement exists. PRAGMA index_list also reports origin information that helps distinguish CREATE INDEX, UNIQUE-constraint, and PRIMARY-KEY origins.

Indexes trade read work for write/storage work

Every maintained index is another sorted structure SQLite must update when an INSERT, DELETE, or relevant UPDATE changes its keys. That may add B-tree searches, page modifications, journal/WAL frames, cache pressure, and file space. On the read side, the same structure may avoid scanning thousands of irrelevant rows or may deliver rows in an order that avoids a separate sort.

A qualitative storage observation

Use page counts as an observation, not a benchmark. Record the database page count before and after creating a full index. The count may grow because the new B-tree needs pages. Dropping the index frees its pages for reuse, but the database file need not immediately shrink; Chapter 11 will explain freelist and VACUUM behavior.

PRAGMA page_size;PRAGMA page_count;CREATE INDEX idx_note_device ON maintenance_note(device_id);PRAGMA page_count;DROP INDEX idx_note_device;PRAGMA freelist_count;PRAGMA page_count;

Failure cases and safer corrections

Baseline lab: prove the plan transition

Start from a fresh chapter database. Record the plan for device_id=42, create idx_note_device, record the plan again, and run the query to verify the result count is unchanged. The index changes the algorithm, not query semantics.

SELECT COUNT(*) AS notes_for_device_42FROM maintenance_noteWHERE device_id = 42;-- With 30,000 notes distributed over 1,000 devices, expect 30.DROP INDEX idx_note_device;EXPLAIN QUERY PLANSELECT COUNT(*) FROM maintenance_note WHERE device_id=42;-- Return to the baseline scan before Lesson 2.

Production judgment and bridge

Indexing is now an evidence loop: define the access pattern, inspect the baseline plan, create the smallest candidate structure, inspect the new plan, test realistic data, and account for write/storage cost. Lesson 2 moves from single-column indexes to the harder design problem—column order in composite indexes and whether one index can serve filtering, sorting, and projection together.

Authoritative references

• SQLite — Query Planning.
• SQLite — Database File Format: representation of SQL indices.
• SQLite — CREATE INDEX.
• SQLite — EXPLAIN QUERY PLAN.