Understanding SQL indexes
B-trees by default — and the five other kinds for when they're not enough.
What the leftmost-prefix rule means, which queries each index type accelerates, and how to spot indexes that cost more than they save.
B-tree is the default for a reason.
A balanced n-ary tree of (key, row-pointer) pairs. Lookups, range scans, ordered retrievals — all O(log n). Almost every CREATE INDEX creates one of these. The whole database can run on B-trees alone. The other index types exist for specific data shapes B-trees handle poorly — full-text search, set containment, geographic queries.
The leftmost-prefix rule.
A composite index on (a, b, c) can serve queries that filter by: a; (a, b); (a, b, c). It cannot serve queries that filter only by b, or by (b, c), or by c alone — the B-tree's key order requires the leftmost column to be specified. Surprising number of "the index isn't being used" complaints come down to this. The fix: pick the column order to match your most common query.
The five non-B-tree types.
Hash: O(1) lookup, no range, no ordering — Postgres has them, MySQL effectively doesn't. GIN (Generalized Inverted Index): for multi-valued columns — arrays, JSONB, tsvector full-text. Containment queries (@>) use GIN. GiST (Generalized Search Tree): geometric, range types, kNN search. BRIN (Block Range Index): a tiny summary per page, useful for huge tables with naturally clustered data (timestamps in append-only logs). SP-GiST: space-partitioned, for non-balanced shapes like trie-based text.
Partial indexes.
An index with a WHERE clause: CREATE INDEX idx_active_users ON users (email) WHERE deleted_at IS NULL. Only active users are in the index; lookups for active users use it, the soft-deleted rows don't bloat it. Especially valuable when a small fraction of rows are queryable. Postgres has them; MySQL doesn't (functional indexes are the closest workaround).
Covering indexes.
An index that includes all columns the query needs — the planner can answer from the index alone without visiting the table. Postgres's INCLUDE clause:CREATE INDEX idx ON orders (user_id) INCLUDE (total). The index tree is keyed on user_id but the leaves carry total. QuerySELECT user_id, total WHERE user_id = 42 reads only the index. Index Only Scan in EXPLAIN is the giveaway.
A worked tuning.
A reporting query: SELECT user_id, SUM(total) FROM orders WHERE created_at > '2026-01-01' AND status = 'completed' GROUP BY user_id. Existing single-column indexes on each column → bitmap scans, sort spills to disk. New composite index on (status, created_at, user_id) with INCLUDE(total) → Index Only Scan, in-order aggregation, no sort. Query time drops from 12 seconds to 80 ms. One CREATE INDEX, two minutes of EXPLAIN reading.
Reporting query
3 columns + INCLUDE
Order matters; INCLUDE avoids the heap.
(status, created_at, user_id) INCLUDE (total)
= 12s → 80ms
Don't over-index.
Every index slows writes and consumes disk. A table with 10 indexes does 11× writeamp on every UPDATE (worst case). Indexes that haven't been used in a month should probably be dropped — pg_stat_user_indexes in Postgres shows read counts. The discipline: add an index when EXPLAIN tells you to, never preemptively, and review unused indexes quarterly.