SQL Indexes
An index is an auxiliary data structure that lets the database find rows without scanning the whole table — trading extra storage and slower writes for much faster reads.
Learning objectives
- Explain how a B-tree index turns an O(n) full table scan into an O(log n) lookup.
- Distinguish clustered from non-clustered indexes and describe composite (multi-column) indexes and the left-prefix rule.
- Recognize covering and unique indexes and when each avoids extra work.
- Decide when NOT to add an index and read a query plan with EXPLAIN.
Simple explanation
Imagine a 900-page reference book with no index at the back. To find every mention of "B-tree" you would have to read all 900 pages, cover to cover. That is a full table scan. Now add the alphabetical index at the back: you flip to "B", find "B-tree — pages 44, 210, 733", and jump straight there. A database index is exactly that back-of-the-book index — a separate, sorted structure that points at the rows you want so the database does not have to read every row.
The catch is the same as with a real book: the index takes extra pages (storage), and every time you edit the book you also have to update the index (slower writes). Indexes make reads fast and writes a little slower. That single sentence explains almost every decision you will make about them.
Technical explanation
An index is an auxiliary data structure maintained alongside a table. The overwhelmingly common implementation is a B-tree (more precisely a B+tree): a balanced, sorted tree where each node holds many keys and the leaves are linked in sorted order.
Without an index, finding WHERE email = 'ada@example.com' forces the engine to examine every row — a full table scan, which costs O(n) and gets linearly worse as the table grows. With a B-tree index on email, the engine descends from the root to a leaf, comparing keys at each level. Because the tree is balanced and shallow (a B-tree of a few levels can index millions of rows), the lookup costs O(log n) — a handful of page reads instead of millions.
Two broad kinds:
- Clustered index — the table's rows are physically stored in the order of this index. There can be only one per table because the data can only be sorted one way. In many engines the primary key is the clustered index (e.g. InnoDB in MySQL). The leaf level *is* the row data.
- Non-clustered (secondary) index — a separate structure whose leaves hold the indexed key plus a pointer (a row id or the primary key) back to the actual row. You can have many of these per table.
A composite (multi-column) index on (a, b, c) sorts rows by a, then b within equal a, then c. Because of this ordering it obeys the left-prefix rule: the index can serve queries that filter on a *leading prefix* of the columns — (a), (a, b), or (a, b, c) — but not (b) or (b, c) alone, just as a phone book sorted by (last name, first name) is useless for finding everyone named "Ada" regardless of surname.
A covering index contains every column a query needs (in the key or as included columns), so the engine answers the query from the index alone and never touches the table. This avoids the extra "look up the full row" step and is one of the biggest wins available.
A unique index additionally enforces that no two rows share the indexed value; it both speeds lookups and guarantees a constraint (a primary key is backed by a unique index).
Why it matters
Indexes are the single highest-leverage tool for query performance. A missing index can turn a 5-millisecond query into a 5-second one once a table has millions of rows; a redundant index can silently slow every INSERT and inflate storage and backups. Knowing which indexes to create — and, just as importantly, which *not* to — separates code that survives production scale from code that falls over.
How it works
For a query like SELECT * FROM users WHERE email = 'ada@example.com':
- The query planner estimates, using table statistics, whether using an index or scanning is cheaper.
- If it chooses the
emailindex, it starts at the root node and compares the target to the node's keys to pick a child. - It descends level by level — each step discards a large fraction of the remaining keys — until it reaches a leaf.
- The leaf holds either the row (clustered) or a pointer to it (non-clustered); a non-clustered hit then does a row lookup ("bookmark lookup") to fetch the remaining columns — unless the index is *covering*.
- On writes, the engine must also insert/update/delete the entry in every affected index and keep each tree balanced — this is the write cost you pay for read speed.
You inspect these decisions with EXPLAIN (or EXPLAIN ANALYZE in PostgreSQL), which prints the query plan: whether it used a *Seq Scan* / *Index Scan* / *Index Only Scan*, the estimated rows, and the cost.
Real-world analogy
Think of a warehouse. The clustered index is how the boxes are physically arranged on the shelves — you can sort the whole warehouse only one way (say, by product ID). A non-clustered index is a separate card catalog that says "product named 'widget' → shelf B12". Looking up the catalog is fast, but you still have to walk to shelf B12 to get the box (the row lookup). If the card itself already wrote down everything you needed — price and quantity — you never walk to the shelf at all: that is a covering index.
Important terminology
- Full table scan (Seq Scan) — reading every row to satisfy a query; O(n) and the thing indexes exist to avoid.
- Cardinality — the number of distinct values in a column. High cardinality (e.g. email) indexes well; low cardinality (e.g. a boolean
is_active) usually does not. - Selectivity — how effectively a condition narrows the rows. Highly selective predicates benefit most from an index.
- Left-prefix rule — a composite index on
(a, b, c)can be used for a query filtering on a leading prefix (a, ora, b, …) but not for one that skipsa. - Covering index — an index that contains all columns a query reads, letting it be answered without touching the table.
Key definitions
- Index
- An auxiliary, sorted data structure that lets the database locate rows without scanning the whole table, at the cost of storage and slower writes.
- B-tree
- The balanced, sorted tree (usually a B+tree) most indexes use; its shallow, balanced shape gives O(log n) lookups even for millions of rows.
- Composite index
- A multi-column index sorted by its columns in order; it serves queries filtering on a leading prefix of those columns (the left-prefix rule).
- Covering index
- An index that contains every column a query needs, so the query is answered from the index alone without a row lookup into the table.
Must memorize
Must memorize
- Indexes speed up reads and slow down writes (INSERT/UPDATE/DELETE must maintain every index).
- A B-tree lookup is O(log n); a full table scan is O(n).
- Left-prefix rule: an index on (a, b, c) helps queries on a, or (a, b), or (a, b, c) — never on b or c alone.
- A covering index answers a query without touching the table; a unique index also enforces a no-duplicates constraint.
Real-world example
A login lookup on a 10-million-row users table
Authentication runs SELECT * FROM users WHERE email = ? on every login. Without an index this is a full scan reading all 10M rows — hundreds of milliseconds under load. Adding a unique index on email makes it an O(log n) B-tree lookup of a few page reads (sub-millisecond) and simultaneously guarantees no two accounts share an email.
A dashboard "recent orders per user" query
A dashboard runs SELECT id, total FROM orders WHERE user_id = ? ORDER BY created_at DESC LIMIT 20. A composite index on (user_id, created_at) that also includes id and total is covering: the database finds the user's rows already sorted by date and returns the needed columns straight from the index, skipping both the sort and the row lookups.
Code example
-- Speed up lookups that filter by email.
CREATE INDEX idx_users_email ON users (email);
-- A unique index both speeds lookups AND forbids duplicate emails.
CREATE UNIQUE INDEX uq_users_email ON users (email);
-- Now this query uses the index instead of scanning every row.
SELECT id, name FROM users WHERE email = 'ada@example.com';A single-column index and a unique index.
-- Order matters: equality column (user_id) first, range/sort column next.
-- INCLUDE adds columns to the leaf so the index can answer the query alone.
CREATE INDEX idx_orders_user_created
ON orders (user_id, created_at DESC)
INCLUDE (id, total);
-- Covered by the index above (no table lookup needed):
SELECT id, total
FROM orders
WHERE user_id = 42
ORDER BY created_at DESC
LIMIT 20;
-- NOT served by that index (skips the leading user_id column):
-- SELECT * FROM orders WHERE created_at > now() - interval '1 day';A composite index (column order matters) that also covers the query.
-- PostgreSQL: ANALYZE actually runs the query and reports real timing.
EXPLAIN ANALYZE
SELECT id, total
FROM orders
WHERE user_id = 42
ORDER BY created_at DESC
LIMIT 20;
-- A good plan shows an "Index Only Scan using idx_orders_user_created".
-- A "Seq Scan on orders" would mean the index is missing or unusable
-- (e.g. a function on the column, or a leading-prefix mismatch).Inspecting the query plan with EXPLAIN to confirm the index is used.
Common mistakes
Mistake
Over-indexing — adding an index for every column "just in case".
Do this instead
Every index slows writes and consumes storage. Add indexes to match real query patterns, and drop unused ones. Also avoid indexing low-cardinality columns (e.g. a boolean) where a scan is often cheaper than the index.
Mistake
Putting composite-index columns in the wrong order, e.g. (created_at, user_id) when you filter by user_id.
Do this instead
Because of the left-prefix rule the index cannot be used for a query on user_id alone. Order columns so the most-filtered (equality) column comes first, then range columns — here (user_id, created_at).
Interview questions
Quiz
Flashcards
Show answer · Space