Indexes: the four types you actually use

The first time you see EXPLAIN ANALYZE change from Seq Scan on users (cost=0.00..18432.00) to Index Scan using users_email_idx (cost=0.42..8.44) and the query goes from 1.8 seconds to 1.8 milliseconds, you become an indexes person for life. The trap is that the lesson most people take away from that moment — more indexes make queries faster — is just barely true enough to be dangerous. Every index speeds up some queries and slows down every write. Choosing them well is one of the few places in databases where a small amount of theory pays for itself within a week.

Why an index exists at all

A table on disk is a heap. Rows are stored in pages of typically 8KB, in whatever order they were inserted. To find one row by some predicate, the database has to read every page — that's the Seq Scan. On a 10GB table that's a lot of disk I/O.

An index is a separate, ordered data structure that maps from a key to the location of the matching row in the heap. Searching the index is fast because it's sorted. The trade is that every write now has to update both the heap and every index that mentions the column, plus storage doubles or triples depending on how many indexes you've built.

The four index types you'll meet in Postgres (and conceptually in every other modern database) each answer a different question: what shape of search do you need?

B-tree — the default, and almost always the right call

B-tree is what you get from CREATE INDEX. It's a balanced tree sorted by the indexed column(s). It excels at:

• Equality lookups: WHERE email = 'x'
• Range scans: WHERE created_at BETWEEN ... AND ...
• Sorting: ORDER BY price LIMIT 10 reads in index order, no sort needed
• Prefix matching: WHERE name LIKE 'A%' (but not LIKE '%A%')

It fails at unsorted predicates: WHERE tags @> ARRAY['a'] (contains) doesn't use a B-tree, and shouldn't.

Multi-column B-trees follow a critical rule: leftmost prefix only. An index on (a, b, c) can serve queries that filter on a, on a, b, or on a, b, c, but not queries that filter only on b or only on c. The order of columns in the index is one of the most under-discussed decisions in database design.

Most "missing index" advice is actually wrong column order. The query filters on (org_id, status) but the index is on (status, org_id) and only the very rare status = ? lookup uses it.

The column-order rule of thumb: most selective column first, but only if it's actually filtered on in queries. If 95% of your queries filter org_id and 50% additionally filter status, you want (org_id, status) regardless of which is more selective.

Hash — the niche specialist

Hash indexes do one thing very well: equality lookup on the indexed column. WHERE id = 42. They cannot do range scans, cannot do sorting, cannot do prefix matching. The only thing they offer over a B-tree is slightly smaller storage and slightly faster equality lookups for fixed-size keys.

In Postgres they used to be unlogged and unreliable. They've been production-ready since 10. Even so, most teams never use them — a B-tree handles equality lookups well enough that the slim performance edge doesn't justify maintaining a second tool. The exception is when you have a very large table and only equality lookups on a column and storage size matters.

GIN — for "contains" and full-text

GIN (Generalized Inverted iNdex) is for indexing values that contain many things — arrays, JSON, full-text documents. Where a B-tree stores one key per row, a GIN stores one entry per element inside the row's value.

WHERE tags @> ARRAY['urgent'] on a million-row table without a GIN: 1.5 seconds of seq scan. With a GIN: 4 milliseconds. The difference is that the GIN has already inverted the structure — it knows which rows contain "urgent" because it indexed every tag as a key pointing to row IDs.

GIN is what makes JSON-as-a-column survivable in Postgres. Without CREATE INDEX ON events USING gin (payload), every WHERE payload @> '{"k": "v"}' is a seq scan. With it, those queries are routine. The trade-off is that GINs are slow to update — every insert into a JSON column has to find or create N inverted entries — and they're larger than B-trees.

BRIN — the giant-table trick

BRIN (Block Range INdex) is for tables so large that maintaining a full B-tree would be enormous, but which have a natural ordering on disk. Time-series data is the canonical case: events are inserted in roughly time order, so block 1042 of the heap contains rows from roughly 2025-04-10 10

A BRIN doesn't index rows — it indexes ranges of blocks. For each block range, it records the min and max value of the indexed column. A query WHERE created_at > '2025-04-10 10:00' consults the BRIN, which says "only blocks 1042-1100 might match", and the database seq-scans just those blocks.

BRIN is 100× smaller than the equivalent B-tree on a 100GB table. It returns more candidate blocks than a B-tree would for the same query, so the heap fetch is heavier — but on tables where a B-tree wouldn't fit in RAM anyway, BRIN wins by being the index that actually fits.

Covering indexes and index-only scans

The expensive part of using an index is not the index lookup; it's the heap fetch that follows. The index points to a row, the database reads the heap page that contains it, and disk I/O is what that costs.

A covering index includes every column the query needs in the index itself, so the database can answer the query without touching the heap at all. In Postgres: CREATE INDEX idx ON orders (org_id, created_at) INCLUDE (total, status). Now SELECT total, status FROM orders WHERE org_id = ? AND created_at > ? is an index-only scan — answered entirely from the index, no heap I/O.

The trade-off is index size and write cost. Each INCLUDEd column makes the index larger and slows every update. Covering indexes shine when the read load on a specific query is high enough to justify the extra write cost.

Partial indexes

Most production indexes don't need to cover every row. If 99% of your orders are in state completed and you almost always query pending or failed, build a partial index:

CREATE INDEX idx ON orders (created_at)
  WHERE status IN ('pending', 'failed');

It's 100× smaller than a full index, 100× faster to update, and answers the queries you actually care about. Partial indexes are under-used because authors think of indexes as "one per (table, column)". The real shape is "one per (query pattern, with whatever filters narrow the index)".

The write-amplification tax

Every index costs every write. A table with 5 indexes pays 5× the index-update cost on every INSERT, UPDATE, and DELETE (kind of — Postgres only updates indexes whose columns changed). On a write-heavy table this dominates.

It's worth doing the arithmetic once, because it reframes how you think about adding "just one more" index. Take a table sustaining 10,000 writes/sec, and say each index update costs roughly 5µs of CPU plus a WAL write:

The numbers are rough, but the shape is real: index maintenance scales linearly with index count and write rate, and it competes for the exact CPU and I/O your writes need. The 20-index table isn't "a bit slower" — it has a whole core doing nothing but bookkeeping, and that's the core that disappears first under a write spike.

The fix is to delete indexes you don't need. pg_stat_user_indexes tells you which indexes haven't been read since the last reset; if the count is zero and the table sees writes, the index is pure cost. Production databases routinely have 30-50% of their indexes unused because someone created them for a query that was later optimized away or never shipped.

The production gotchas

Auto-incrementing keys make hot-spot leaves. A B-tree on a monotonically-increasing column (bigserial PK) always writes to the rightmost leaf. At high write rates this leaf becomes a contention point. The fix is either UUIDs (random insert pattern, much higher index churn) or a UUID variant that's monotonic but prefix-randomized (UUIDv7).

Index bloat. Postgres MVCC means UPDATEs leave dead tuples in indexes until vacuum cleans them. Heavily-updated tables grow indexes 2-3× their real size; REINDEX CONCURRENTLY shrinks them. Schedule it before you have a problem, not after.

Cardinality matters. An index on a boolean column (is_active) doesn't help — the planner correctly decides it's cheaper to seq-scan than to use a 50%-selective index. Either combine it into a multi-column index or make it a partial index on the rare value.

EXPLAIN lies sometimes. It shows estimated rows from statistics. If statistics are stale, the plan it picks may be terrible. ANALYZE updates them; autovacuum does this for you in healthy databases. Suspect stale stats whenever a query that was fast yesterday is slow today with no schema change.

When to walk away from adding an index

• The table is small (under 10K rows) — seq scan is fine and the planner knows it.
• The query runs once a day for a batch job — pay the seq scan, save the write tax.
• You're optimizing a query before measuring — EXPLAIN ANALYZE it first; the bottleneck is often elsewhere (a sort, a hash join, a network round-trip).

[CONCEPT]lsm-vs-btrees explains why some databases organize their primary storage as a B-tree and others (Cassandra, RocksDB, ScyllaDB) flip the trade-off entirely. [CONCEPT]sharding-strategies is where indexes get really interesting — a global index across shards is a small distributed system on its own.