When should I add a database index?

Add an index when a column is used in WHERE clauses, JOIN conditions, or ORDER BY on a frequently-queried table. Don't add one to columns that are rarely queried, that have very low cardinality (booleans), or to write-heavy tables where the index maintenance cost outweighs the read benefit. Always check EXPLAIN ANALYZE before and after to confirm the optimiser uses the new index.

What is a covering index?

A covering index is one that includes all the columns a query needs, so the database can answer the query from the index alone without touching the underlying table (heap). For a query like SELECT name, email FROM users WHERE id = ?, an index on (id, name, email) covers it; an index on just (id) does not. Covering indexes are faster for read-heavy workloads at the cost of larger index size and slower writes.

13 min read · Guide · Storage

How it works · Storage

How a database index finds a row without scanning.

A database without indexes scans every row of every table. With them, it lands on the right row in O(log n) page reads, using a tree.

Parts01 – 08 InteractiveLive B-tree PrereqSQL / pages

Why a table without an index is slow

A database index is an auxiliary data structure that lets the database find rows without scanning the whole table. The dominant index type is the B-tree (or B+ tree); equality-only indexes can use hashes. Rudolf Bayer and Edward McCreight introduced B-trees in 1972; they remain the primary index in PostgreSQL, MySQL, SQLite, SQL Server, Oracle.

Tables are stored as a sequence of fixed-size pages (typically 8 KB or 16 KB) on disk, kept warm by the database's buffer-pool cache. Without an index, finding a row means reading every page in turn. The reads are sequential, which is fast per byte, but they cover every byte of every row, which is slow per query. A 100-million-row table can be gigabytes of sequential read per lookup.

The cost grows linearly with table size. Finding one user out of ten million means reading the entire users table. The query planner shows this as Seq Scan in EXPLAIN, which is a prompt to ask whether an index could replace it.

B-tree indexes, and why they are the default

A B-tree is a search tree in which each node holds many keys (not one or two like a binary tree), so the tree stays shallow even for very large datasets. Each node fits in one disk page, so descending a level costs a few key comparisons and one disk read. A trillion-row B-tree is roughly 6 levels deep, which means about six page reads to find any row.

Inserts walk the tree to a leaf, add the key in sorted order, and split the leaf if it overflows. The middle key is promoted to the parent and the rest stay in two new leaves. Splits cascade upward when parents overflow too, and a split at the root grows the tree by one level. The simulator below shows this.

How a B-tree splits on insert

Below is a B-tree of order 4 (max 4 keys per node). Type a number to insert or look it up. Inserts split nodes when they overflow, and lookups highlight the path the engine takes.

1 node · depth 1 · 0 keys

Hash indexes: instant, but only for exact matches

A hash index applies a hash function to the key, lands in a bucket, and finds the row pointer in (effectively) constant time. It can be faster than a B-tree on equality lookups, especially on very large tables. Postgres supports them; MySQL's memory engine does too.

The trade-off is that hash indexes can't answer range queries (WHERE age > 30), can't scan in order, can't support ORDER BY. Their bucket layout is also random-access on disk, which does not suit sequential reads. Use one only when every query is an exact-equality lookup and the table is very large.

B-tree

The default choice

Equality, range, ordered scans, prefix matches, ORDER BY. Right for almost every index you will create.

Hash

Equality only, rarely needed

Single-key lookups by hash code. Faster on huge tables, but useless for ranges. Use it when profiling justifies the trade-off.

Covering indexes: answering a query from the index alone

A normal index lookup finds a row pointer, then visits the table page (the "heap") to read the rest of the columns. A covering index includes every column the query needs in the index itself, so the engine can answer without touching the heap.

In Postgres: CREATE INDEX ... INCLUDE (col_a, col_b). The included columns are stored in the leaf nodes. They are not part of the search path but are available without a separate fetch. EXPLAIN shows Index Only Scan when this works. This can be a 2–10× speedup on narrow read-heavy queries.

Multi-column indexes and the leftmost-prefix rule

An index on (country, city, age) can be used for queries filtering by country, by country + city, or by all three, but not by city alone, and not by age alone. This is the leftmost-prefix rule. The index is sorted in the order of its columns; you can chop off the right side of that order, but not the left.

Column order therefore matters. Put the most selective column first when most queries filter on a single column. When queries vary, put the column used in the most queries first. Get it wrong and you have an index that costs storage and is never used.

-- Index
CREATE INDEX users_loc_age ON users (country, city, age);

-- Used by:
SELECT * FROM users WHERE country = 'NL';
SELECT * FROM users WHERE country = 'NL' AND city = 'Amsterdam';
SELECT * FROM users WHERE country = 'NL' AND city = 'Amsterdam' AND age = 30;

-- NOT used by (no leftmost):
SELECT * FROM users WHERE city = 'Amsterdam';
SELECT * FROM users WHERE age = 30;

When not to add an index

Every index also adds write cost. Every INSERT / UPDATE / DELETE on the table must update every index too, and each of those updates also goes through the write-ahead log. Five indexes on a write-heavy table mean every write does six writes. The right number of indexes minimises read cost within the write-cost budget.

low cardinality

Don't index boolean columns

An index on is_active matches half the rows, so the planner will scan instead. Use a partial index (WHERE is_active = true) or skip it.

tiny tables

Let small tables scan

Tables that fit in a few pages are faster to read sequentially, and the B-tree descent would touch similar bytes anyway. A 200-row lookup table doesn't need an index.

write-heavy

Cut indexes you don't need

On a logging table receiving thousands of inserts per second, every index is a candidate for removal. Check which indexes are used and drop the ones that aren't.

Read the query plan first

The query planner picks the index. If it picks badly, more indexes won't help, and adding them blindly is how production tables end up with twenty, half unused. Running EXPLAIN ANALYZE on the slow query is the first step.

Things to look for: a Seq Scan on a large table probably needs an index. An Index Scan with a badly wrong row estimate means statistics are stale, so run ANALYZE on the table. A Bitmap Heap Scan visiting most of the table means the index isn't selective enough, and a composite or covering index may serve the query better.

Index hygiene, weekly

Postgres exposes pg_stat_user_indexes with idx_scan counts. Indexes with zero scans over weeks are deletion candidates, though dropping one inside an active transaction takes a heavy lock, so plan the window. Most production databases accumulate indexes over years, and pruning them periodically is a cheap way to cut write cost.

The other index types, and when each one fits

B-tree · default: Fits most cases. Equality, range, ORDER BY and GROUP BY all benefit.
GIN (Generalized Inverted Index) · Postgres: For arrays, JSONB, full-text search. Each value points back to all rows containing it. Writes are slower, and contains-style queries are much faster.
GiST (Generalized Search Tree) · Postgres: Geometric, range, full-text alternatives. The PostGIS extension uses GiST for spatial queries.
BRIN (Block Range Index) · Postgres 9.5+: Stores min/max per block range. Very small (on the order of 100 KB for a 100 GB table), at the cost of slower lookups. A good fit for time-series tables where rows are physically clustered by time.
Partial index: Index only rows matching a predicate: CREATE INDEX ON orders (id) WHERE status = 'pending'. Smaller index, faster scans on the matching subset.
Expression index: Index a function of a column: CREATE INDEX ON users (lower(email)). The query must use the same expression to hit the index.
Hash index · Postgres: Equality only, never range. Was unsafe before Postgres 10 (not WAL-logged); since 10 it's WAL-logged. Rarely beats a B-tree in practice.

Expression indexes. A query can fail to use the index because the planner sees a different expression. WHERE email = 'foo' won't use an index on lower(email); you'd need WHERE lower(email) = 'foo'. Verify with EXPLAIN ANALYZE.

A closing note

An index is usually a B-tree, occasionally a hash, and sometimes an LSM-tree variant (see the storage-engine simulator), chosen to match the query shape. Read the plan, match the index to the query, watch write cost, and drop what isn't used. Most index-related performance problems come down to that loop.