How SQL Indexes Work
IntermediateA database index is a separate data structure that lets the database find rows matching a condition without scanning every row in the table. The default index type — the B-tree — stores column values in a balanced tree so any value can be found in O(log n) comparisons. A table with 100 million rows can be searched in roughly 27 comparisons with an index, versus 100 million comparisons without one. Understanding indexes is the single highest-leverage skill for database performance.
Think of it like a book's index
Without an index, finding every page that mentions "MVCC" in a 600-page textbook means reading every page. With the index at the back, you jump directly to "MVCC — pages 47, 203, 418". The index takes up extra pages and must be updated when content changes, but reading becomes orders of magnitude faster. Database indexes work exactly the same way.
Step by Step
Key Concepts
B-Tree (Balanced Tree)
The default index type. A self-balancing tree where all leaf nodes are at the same depth. The tree stays balanced on insert/delete by splitting and merging nodes. Supports equality (=), range (<, >, BETWEEN), ORDER BY, and IS NULL queries. Height is O(log n) — typically 3–4 levels for millions of rows.
Selectivity
The fraction of rows a predicate matches. High selectivity = few matching rows (e.g., WHERE email = 'alice@...' matches 1 in 1 million). Low selectivity = many matching rows (e.g., WHERE status = 'active' matches 80% of rows). Indexes are most valuable for high-selectivity queries. For low-selectivity queries, a full table scan can be faster because it reads pages sequentially.
Composite Index
An index on multiple columns: CREATE INDEX idx ON orders(user_id, created_at). Useful for queries that filter on multiple columns. Column order matters: a composite index on (a, b) can be used for WHERE a = 1, WHERE a = 1 AND b > 5, but NOT for WHERE b > 5 alone (leftmost prefix rule). Put the most selective or equality-filtered column first.
Covering Index
An index that contains all columns a query needs, eliminating the heap fetch. CREATE INDEX idx ON orders(user_id) INCLUDE (status, total). A query SELECT status, total FROM orders WHERE user_id = 123 can be answered entirely from the index — never touching the heap. Index-only scans are faster because they avoid random I/O into heap pages.
Partial Index
An index on a filtered subset of rows: CREATE INDEX idx ON orders(created_at) WHERE status = 'pending'. If pending orders are 1% of the table, the index is 100x smaller and faster to traverse. Ideal when you frequently query a specific subset and other values are rarely needed.
Index Scan vs Seq Scan
Index scan: follow the B-tree to find matching rows, then random-access the heap pages. Seq scan: read all pages sequentially from start to finish. Sequential reads are faster on spinning disks and can be parallelised. The planner chooses seq scan when a large fraction of rows match — random I/O for thousands of scattered rows is slower than one sequential pass.
EXPLAIN ANALYZE
The essential tool for query optimisation. EXPLAIN ANALYZE SELECT ... shows the execution plan chosen by the planner, estimated vs actual row counts, and time spent at each step. "Seq Scan" where you expected "Index Scan" reveals a missing or unused index. "Rows Removed by Filter" reveals an index being used but poorly.
Index Bloat
Over time, UPDATE and DELETE operations leave dead index entries that VACUUM must clean up. Heavy write workloads cause index pages to become partially empty, wasting space and degrading performance. REINDEX or VACUUM FULL reclaims this space. Monitor bloat with pg_stat_user_indexes and the pgstattuple extension.
Key Facts
- A B-tree index of height 4 can cover a table with up to ~256 million rows. Height 3 covers ~4 million rows. This is why index lookups are nearly constant-time for typical table sizes.
- PostgreSQL supports 8 index types: B-tree, Hash, GiST, SP-GiST, GIN, BRIN, Bloom, and RUM. B-tree is the default and covers 95% of use cases.
- A Hash index is O(1) for equality lookups (vs B-tree's O(log n)) but doesn't support range queries. PostgreSQL's B-tree is so fast in practice that Hash indexes offer little advantage.
- GIN (Generalised Inverted Index) is used for full-text search and JSONB queries. It stores a mapping from each element (lexeme/key) to the list of rows containing it — similar to a search engine's inverted index.
- Indexes are never free: every index on a table adds ~10–30% overhead to INSERT operations and increases storage by roughly the size of the indexed column multiplied by row count.
- NULL values are stored in B-tree indexes in PostgreSQL (since 8.3). This means IS NULL and IS NOT NULL queries can use an index.
Real-World Applications
Diagnosing a slow query
Run EXPLAIN (ANALYZE, BUFFERS) on the slow query. Look for Seq Scan on large tables and high "rows removed by filter". Add an index on the filter column and re-run. If the planner still chooses a seq scan, run ANALYZE to update statistics or check if selectivity is genuinely too low to justify the index.
Optimising a multi-column filter
A query like WHERE tenant_id = 5 AND status = 'active' AND created_at > '2024-01-01' benefits from a composite index. Put tenant_id first (highest selectivity from an equality filter), then created_at (range benefits from leftmost prefix), then include status as an INCLUDE column if needed for a covering index.
Foreign key indexes
PostgreSQL does NOT automatically create indexes on foreign key columns. A DELETE from the parent table requires a scan of the child table to check for referencing rows. Without an index on orders.user_id, deleting a user causes a full table scan of orders. Always index foreign key columns.
Unique indexes
UNIQUE constraints in PostgreSQL are implemented as unique B-tree indexes. CREATE UNIQUE INDEX idx ON users(email) enforces uniqueness and enables fast equality lookups simultaneously. Partial unique indexes allow conditional uniqueness: CREATE UNIQUE INDEX ON orders(reference_number) WHERE status != 'cancelled'.
Frequently Asked Questions
Why is my query not using my index?
Several reasons: (1) Low selectivity — the planner estimates a seq scan is faster because too many rows match. (2) Stale statistics — run ANALYZE to refresh. (3) Type mismatch — WHERE id = '123' on an integer column forces a cast, breaking index use. (4) Function on the column — WHERE LOWER(email) = 'alice' — use a functional index instead: CREATE INDEX ON users(LOWER(email)). (5) Very small table — seq scan is faster when the whole table fits in a few pages.
How many indexes should a table have?
It depends on the read/write ratio. OLTP tables with heavy writes should have fewer indexes (typically 2–5). Analytical tables that are mostly read can have more. Start with indexes only on primary keys, foreign keys, and WHERE/JOIN columns in your most-used queries. Profile with EXPLAIN ANALYZE before adding speculative indexes — each extra index has a real cost on every write.
What is the difference between a clustered and non-clustered index?
A clustered index determines the physical order of rows on disk — the table data IS the index. SQL Server tables have one clustered index (typically the primary key). PostgreSQL does not have clustered indexes by default (tables are "heaps"), but the CLUSTER command can reorder the table according to an index once. Non-clustered (heap) indexes are separate structures pointing back to the table.
Should I index every column that appears in a WHERE clause?
No. Index columns that are highly selective (few matching rows per value), appear frequently in WHERE/JOIN/ORDER BY clauses, and are in tables that are queried far more than they are written to. Low-cardinality columns like boolean flags, status enums with few values, and gender fields rarely benefit from indexes because the planner will prefer a seq scan anyway.