Database Indexing
What a B-tree index actually is, how the planner decides to use it, why column order in a composite index matters, and when an index makes things worse.
An index is a second, sorted copy of one or more columns, stored as a balanced tree whose leaves point back at the table rows. Sorted means the database can find a value, or the start of a range, in a handful of page reads instead of scanning every row. The price is paid on every write, which must update each index too, and the benefit only appears when the query's filter matches the index's order.
Why it matters
A missing index is the most common reason a feature that was instant in development times out in production: the table grew from a thousand rows to ten million and a scan that took 2 ms now takes 20 s and locks a connection the whole time. The opposite failure is quieter: a table with fifteen indexes where every insert rewrites fifteen trees and the write path is what falls over. Knowing how the planner thinks lets you add the one index that matters and leave the rest alone.
What a B-tree index is
Almost every default index (PostgreSQL, MySQL InnoDB, SQLite, SQL Server) is a B-tree: a tree where each node is one disk page holding many sorted keys. Because a page holds hundreds of keys, the tree is extremely wide and therefore shallow. A table with 10 million rows typically has a B-tree of depth 3 or 4, so an equality lookup reads 3 or 4 pages, then one more to fetch the row from the table (the "heap" in Postgres terms).
Three properties fall out of this shape and explain almost every rule that follows.
- Equality and ranges are cheap; "contains" is not. The tree can jump to
kim@or to "everything fromkonward", butLIKE '%kim%'has no starting point, so it scans the whole index or the whole table. - The index is sorted by the key, so ORDER BY on the key is free. Walking the leaf chain produces sorted output with no sort step.
- Every write touches the tree. An insert must place the key in the right leaf, splitting pages when full. Ten indexes on a table means ten trees to update per row.
How the planner decides to use it
The database does not use an index because it exists; it estimates the cost of each way to answer the query and picks the cheapest. The decisive input is selectivity: what fraction of rows the filter keeps. An index lookup costs a few page reads per matching row because rows are scattered across the heap. A sequential scan reads every page once, but each page yields many rows. Below roughly 1-5% of rows the index wins; above that the scan wins, and the planner knows.
| Plan node (Postgres) | What it does | When you see it |
|---|---|---|
| Seq Scan | Reads every table page, filters in memory. | No usable index, or the filter matches most rows. |
| Index Scan | Walks the tree, fetches each matching row from the heap. | Selective filter, few rows. |
| Index Only Scan | Answers from the index alone, never touches the heap. | Every selected column is in the index. |
| Bitmap Heap Scan | Collects matching row locations first, then reads heap pages in order. | Medium selectivity, or several indexes combined. |
EXPLAIN (ANALYZE, BUFFERS)
SELECT id, total FROM orders
WHERE customer_id = 4821 AND status = 'paid'
ORDER BY created_at DESC
LIMIT 20;
-- Before the index:
-- Limit (actual time=812.4..812.5 rows=20)
-- -> Sort (actual time=812.3..812.4 rows=20)
-- -> Seq Scan on orders (actual rows=9412)
-- Filter: (customer_id = 4821 AND status = 'paid')
-- Rows Removed by Filter: 11990588
-- Buffers: shared read=98215
-- After CREATE INDEX ON orders (customer_id, status, created_at DESC):
-- Limit (actual time=0.09..0.11 rows=20)
-- -> Index Scan using orders_cust_status_created_idx
-- Index Cond: (customer_id = 4821 AND status = 'paid')
-- Buffers: shared hit=24Read a plan bottom-up and look at three numbers: rows (how many came out of each node), Rows Removed by Filter (work thrown away, the smell of a missing index), and Buffers (pages touched). The after-plan has no Sort node because the index already delivers rows in created_at DESC order and the LIMIT stops after 20 leaf entries.
Composite indexes: column order is the whole game
A multi-column index is sorted by the first column, then by the second within equal first values, and so on, like a phone book sorted by last name then first name. The tree can only be used for a leftmost prefix of the columns: you can look someone up by last name, or by last name and first name, but not by first name alone.
The second rule: equality columns first, then the range column, then sort columns. Once a range condition is applied on a column, the tree cannot narrow further on columns after it, because within the range the later columns are no longer grouped. (customer_id, status, created_at) serves "this customer, paid, newest first" perfectly; (created_at, customer_id) would have to scan every recent order of every customer.
Covering indexes and index-only scans
If every column the query reads is in the index, the database never has to visit the heap. Postgres lets you append non-key columns with INCLUDE so they ride along in the leaves without affecting sort order. This turns the example above into an index-only scan: the answer is 20 leaf entries and nothing else.
CREATE INDEX orders_cust_status_created_idx
ON orders (customer_id, status, created_at DESC)
INCLUDE (total);
-- SELECT id, total ... now needs no heap access (id is in every index)When an index is not used, or hurts
"I added an index and nothing changed" almost always means the filter does not match the index's sorted key as written. The planner compares the expression in the query with the expression the index was built on; any transformation on the column side breaks the match.
SELECT * FROM users
WHERE lower(email) = 'ann@x.io';
-- function applied to the column:
-- the tree is sorted by email,
-- not by lower(email)CREATE INDEX users_email_lower_idx
ON users (lower(email));
SELECT * FROM users
WHERE lower(email) = 'ann@x.io';Other classic reasons the planner walks past your index:
- Low selectivity.
WHERE is_active = trueon a table where 95% of rows are active. A scan is genuinely cheaper. A partial index,CREATE INDEX … WHERE is_active = false, can still make the rare case fast. - Type mismatch. Comparing a
textcolumn to an integer parameter forces a cast on the column side. ORMs that bind the wrong type cause this silently. - Leading wildcard.
LIKE '%foo'has no prefix to seek. Use a trigram (pg_trgm) or full-text index instead. - OR across different columns.
a = 1 OR b = 2needs either two indexes combined by a bitmap scan or a rewrite asUNION. - Stale statistics. After a bulk load the planner still believes the table is small. Run
ANALYZE.
Pitfalls
- Indexing every column “to be safe”
Single-column indexes on columns that are only ever filtered together do not combine well; the planner might bitmap-AND them, but a composite index in the right order is an order of magnitude cheaper, and the extra trees tax every write.
- Putting the range column first
(created_at, customer_id)for "customer X in the last week" scans every customer's rows in that week. Equality columns go first so the range is applied within an already tiny slice. - Redundant prefixes
An index on
(a)next to one on(a, b)is almost always dead weight: the composite already serves every query the single does. The exception is when(a)is much smaller and used for index-only scans on hot paths. - Creating indexes on a live table without CONCURRENTLY
Plain
CREATE INDEXin Postgres blocks writes for the whole build; on a large table that is minutes of downtime.CREATE INDEX CONCURRENTLYtakes longer and cannot run in a transaction, but keeps the table writable. MySQL InnoDB has an equivalent online DDL path. - Forgetting that the primary key is an index (and in InnoDB, the table)
In MySQL InnoDB the table is the primary-key B-tree, and every secondary index stores the primary key as its row pointer. A wide UUID primary key makes every other index wider and every insert random. Postgres stores rows in a heap instead, which is why it needs a visibility check for index-only scans.
Interview questions
Q1What is a B-tree index and why is it the default?
A balanced tree whose nodes are disk pages holding many sorted keys, with leaves pointing at table rows and linked in order. It is wide and shallow, so lookups cost three or four page reads even on huge tables, and because it is sorted it supports equality, ranges, prefix matches and ORDER BY with one structure. That generality is why it is the default over hashes or specialised indexes.
Q2Walk me through choosing an index for SELECT … WHERE customer_id = ? AND status = ? ORDER BY created_at DESC LIMIT 20.
A composite B-tree on (customer_id, status, created_at DESC). Both equality columns go first so the tree narrows to one customer's rows of one status, and created_at last so those rows are already in the requested order and the LIMIT can stop after 20 leaf entries with no sort. If the SELECT list is small, INCLUDE those columns to get an index-only scan. I would confirm with EXPLAIN ANALYZE that the Sort node is gone.
Q3You added an index but the planner still does a sequential scan. What do you check?
In order: whether the filter applies a function or cast to the column, whether the query uses a leftmost prefix of the index columns, whether the predicate is selective enough (a scan can be cheaper above a few percent of rows), whether statistics are stale (run ANALYZE), and whether the parameter type matches the column type. EXPLAIN shows which one it is.
Q4Should you index a boolean column?
Usually not as a plain index, because the value splits rows into two huge groups and the planner will scan instead. A partial index on the rare value, such as WHERE processed = false for a job queue, is the useful form: it is tiny, always selective, and only the rows you actually look for pay the write cost.
Q5What happens to write performance as you add indexes, and how would you find unused ones?
Every insert and delete, and any update touching an indexed column, must modify every affected B-tree, so write latency and WAL volume grow roughly linearly with index count, and page splits add random I/O. In Postgres pg_stat_user_indexes shows scans per index since the last stats reset; an index with zero scans over a representative period, that is not enforcing a constraint, should be dropped.
Q6What is the difference between an index scan and an index-only scan?
An index scan finds matching entries in the tree and then reads each row from the table to get the other columns. An index-only scan answers entirely from the index because every requested column is stored in it, skipping the table reads, which is where most of the cost lives. In Postgres it additionally needs the visibility map to confirm rows are visible without visiting the heap.
Q7How does an index interact with a UNIQUE constraint or an upsert?
A unique constraint is implemented as a unique B-tree index, so it both speeds lookups on that column and makes concurrent inserts of the same key serialise at the index. That is what INSERT … ON CONFLICT relies on: the conflict target must match a unique index, and the index is the atomic check that prevents duplicates without an explicit lock.
- A B-tree is a sorted, page-based tree: equality, ranges, prefixes and ORDER BY are cheap; "contains" is not.
- The planner uses an index only when it estimates it is cheaper; selectivity is the deciding input.
- Composite indexes serve leftmost prefixes only. Put equality columns first, the range column next, sort columns last.
- A function, cast or leading wildcard on the column side hides the index; use expression or partial indexes for those cases.
- Read EXPLAIN ANALYZE bottom-up: Rows Removed by Filter and a Sort node are the two smells to fix.
- Every index taxes every write. Build the one that matches the query, drop the ones nobody scans, and use CONCURRENTLY in production.