How Indexes Work

"The fastest way to read a row is to know where it is before you look." — a database engineer's proverb

Here is a query that will one day ruin your afternoon:

SELECT * FROM users WHERE email = 'ada@example.com';

On a table of ten rows it returns instantly. On a table of ten million rows, with no index, it can take seconds — because the database has no choice but to read every single row and check whether its email matches. Ten million comparisons to find one person. Multiply that by every request hitting your login endpoint and you have an outage.

The single most valuable performance skill in databases is understanding indexes: what they are, why they turn a search from "read everything" into "jump almost straight to the answer," and what they cost. Almost every slow query you will ever debug comes down to one question — is there an index for this, and is the engine using it? By the end of this chapter you'll be able to answer that, read a query plan, and add the right index on purpose instead of by superstition.

The problem: the full table scan

When you filter a table on a column that has no index, the engine performs a full table scan — it walks every row from the first to the last, testing your WHERE condition against each one. That's O(n): double the rows, double the work. For a background job over a small table, fine. For a lookup on the hot path of a busy app, fatal.

SQLite will tell you exactly what it plans to do if you ask, using EXPLAIN QUERY PLAN. It doesn't run the query — it reports the strategy. Run this against our seed customers table (which has no index on city):

Read the output. The keyword to hunt for is SCAN — SCAN customers. That means: read the whole table, row by row, and keep the ones in Lagos. With five rows it's harmless. The word SCAN on a large, frequently-run query is the smell that starts most performance investigations.

What an index actually is

A database index is a separate, sorted data structure that stores the values of one (or more) columns, each paired with a pointer to the full row it came from. It is a copy of part of your data, kept in order, purpose-built for fast lookup. The table stays where it is; the index sits beside it.

Because the index is sorted, the engine can find a value without scanning — it can navigate. And the structure almost every relational database uses to keep it sorted-yet-fast-to-update is one you already met in Volume 4: the balanced search tree. Specifically, the B-tree (and its close cousin the B+-tree).

Why a B-tree, and why O(log n)

In Volume 4 you learned that a balanced binary search tree lets you find any value in O(log n) steps, because each comparison halves the space still to search. A B-tree is that same idea, generalized for disk: instead of one key and two children per node, each node holds many keys and many children — often hundreds. A node is sized to a disk page (say 4–16 KB), so one read from disk pulls in hundreds of keys at once.

That high fan-out makes the tree extraordinarily shallow. A binary tree over a billion rows is ~30 levels deep; a B-tree with a fan-out of a few hundred reaches a billion rows in 3 or 4 levels. Since each level is one page read, the database finds any row in a billion with a handful of reads instead of a billion. That is the whole game: O(log n) instead of O(n), with a logarithm base large enough that the tree is basically flat.

The B+-tree variant (used by MySQL/InnoDB, and effectively by SQLite's tables) adds one refinement: all the actual data lives in the leaf level, and the leaves are linked together like a sorted linked list. This buys three superpowers at once, all from the same structure:

1. Point lookups — WHERE email = ? — descend the tree, O(log n).
2. Range scans — WHERE age BETWEEN 25 AND 40 — descend to the start of the range, then walk the linked leaves in order until you fall out of range. No re-navigation per row.
3. Ordered traversal — ORDER BY age — the leaves are already in sorted order, so the engine can return sorted rows without a separate sort step.

CREATE INDEX: making one

You create an index with one line of DDL:

CREATE INDEX index_name ON table_name (column_name);

That's it — the engine reads the column, builds the sorted B-tree, and from then on maintains it automatically on every write. Let's prove the payoff. First, build a small table inline and ask for the plan of a lookup before any index exists:

The plan says SCAN people — every row gets read. Now the same table and query, but with an index created first. Watch the plan change:

Now it reads SEARCH people USING INDEX idx_people_city (city=?). That single word change — SCAN to SEARCH — is the difference between reading the whole table and diving straight to the matching rows through the B-tree. This is the most important diagnostic you will run in your career: EXPLAIN it, and look for SEARCH USING INDEX.

It works on the seed tables too. Our customers.city had no index (that first block said SCAN). Add one and re-check:

Same story: SEARCH customers USING INDEX idx_cust_city. The index you create in a block lives only for that run (the DB resets each time), which is perfect for experimenting.

Ranges and ordering, for free

Because the B-tree is sorted, an index helps with more than equality. Create one on age and notice the plan handles a range and an ORDER BY without a separate sort:

The plan shows SEARCH customers USING INDEX idx_cust_age (age>?) — it seeks to the first qualifying row and walks the sorted leaves. No USE TEMP B-TREE FOR ORDER BY line, because the index already delivers rows in age order. Seeing USE TEMP B-TREE in a plan is a hint you could add an index to skip the sort.

Indexes and joins

Joins are where missing indexes hurt most, because a join without one can degrade toward O(n×m) — for each row on one side, scan the whole other side. An index on the join column turns each of those inner scans into a fast seek. Compare the plan for a join filtered by city, once we index both the filter column and the foreign key:

The plan uses idx_cust_city to find the Lagos customers, then idx_ord_custid to seek their orders directly — SEARCH o USING INDEX idx_ord_custid. Rule of thumb: index your foreign keys. Almost every join and every "find the children of this parent" query depends on them.

The cost: why you don't index everything

If indexes make reads fast, why not index every column? Because an index is not free — it is a second copy of data that must be kept in sync:

• Writes get slower. Every INSERT must also insert into every index on that table; every UPDATE to an indexed column must move it within the index B-tree; every DELETE removes it from each index. A table with eight indexes does roughly nine writes for every one logical write. Indexes trade write speed and CPU for read speed.
• Storage grows. Each index is real bytes on disk (and in RAM cache). Over-indexed tables can carry more index than data.
• The planner can be misled. Too many overlapping indexes give the query optimizer more choices and occasional wrong guesses.

So indexing is a deliberate trade, made per query pattern, not per column. Index the columns you actually filter, join, and sort on in your hot queries; leave the rest alone; and periodically drop indexes nothing uses.

Clustered vs non-clustered

There are two flavours of index, and the distinction matters at work:

• A clustered index is the table — the rows themselves are stored in the leaves of the B-tree, physically ordered by the index key. A table can have only one, because the data can only be laid out one way. In SQLite, ordinary tables are stored in a B-tree keyed by a hidden rowid; if you declare a column INTEGER PRIMARY KEY, it becomes an alias for that rowid, so your primary key is the clustered index — lookups by it are as fast as it gets. (MySQL/InnoDB works the same way: the primary key clusters the table. SQL Server lets you choose the clustered key.)
• A non-clustered (secondary) index is the separate structure we've been building all chapter: its leaves hold the indexed value plus a pointer (in SQLite, the rowid) back to the full row. Finding a row through it takes two hops — search the index to get the rowid, then fetch the row from the table. That extra hop is why a covering index (which needs no table fetch) can be meaningfully faster.

Notice the plan says SEARCH accounts USING INTEGER PRIMARY KEY (rowid=?) — no separate index needed, because the primary key clusters the table itself. Compare that to a lookup on the non-indexed owner, which would SCAN.

Hash indexes, briefly

B-trees aren't the only index structure. A hash index stores keys in a hash table, giving O(1) average-time equality lookups — potentially faster than a B-tree for pure WHERE x = ?. The catch: a hash has no order, so it cannot do range scans (>, BETWEEN) or ORDER BY, and it's useless for prefix matches. PostgreSQL offers USING HASH indexes for equality-only workloads; many in-memory engines (like Redis) are hash-based at their core. SQLite has no hash index type — its B-trees handle everything. The lesson: B-trees win by default because they serve equality, ranges, and ordering all at once; reach for a hash index only when you have equality-only lookups and measured proof it helps.

Common Mistakes

• No index on a hot lookup column. The classic. If you filter or join on it constantly, index it. EXPLAIN and look for SCAN.
• Indexing everything. Each index taxes every write and eats storage. Index for real query patterns, not hypothetically.
• Wrong column order in a composite index. (a, b) cannot serve WHERE b = ? alone. Put the most selective / most-often-filtered column first, respecting the leftmost-prefix rule.
• Defeating the index with a function on the column. WHERE lower(email) = ? or WHERE strftime('%Y', created) = '2026' can't use a plain index on the raw column — the engine would have to compute the function per row. Store/normalize the value, or create an expression index.
• Assuming an index is used — never verifying. The optimizer may skip an index it deems unhelpful (e.g. a low-selectivity column where most rows match). Always confirm with EXPLAIN QUERY PLAN.
• Forgetting to index foreign keys. Joins and cascade operations quietly do full scans without them.

Summary

• Without an index, a filtered query does a full table scan — O(n), reading every row. EXPLAIN QUERY PLAN shows this as SCAN.
• An index is a separate, sorted structure holding column values plus pointers to their rows — the back-of-the-book index for your table.
• Databases build indexes as B-trees / B+-trees: balanced, high-fan-out trees that give O(log n) point lookups, plus range scans and ordered reads for free, just 3–4 levels deep even over billions of rows.
• CREATE INDEX builds one and the engine maintains it automatically; a good plan reads SEARCH ... USING INDEX.
• Indexes cost write speed (every write updates every index) and storage — so index deliberately, matched to real query patterns, and index your foreign keys.
• Clustered index = the table stored in key order (SQLite's rowid / INTEGER PRIMARY KEY); non-clustered = a separate index pointing back at rows. Hash indexes give O(1) equality but no ranges or ordering.

Knowing that an index exists is one thing; knowing whether the engine chose to use it — and why it sometimes doesn't — is the next. We'll open the query planner and learn to read a full execution plan.