Indexes — B-tree, Hash, GIN, BRIN

TL;DR

An index is a side data structure the database maintains so it can find rows faster than a full table scan. Without indexes, every WHERE id = 42 reads every row. With a B-tree on id, the same query is O(log n) — for a billion-row table, ~30 disk reads instead of a billion.

Postgres ships five index types. You’ll use B-tree 95% of the time:

Indexes are not free. Every INSERT/UPDATE/DELETE updates every relevant index. On a table with 10 indexes, writes are 10× the work of an unindexed table. The right number of indexes is “as few as your queries actually need.”

The picture in your head

A B-tree index is the same data structure as the alphabetical tabs in a physical dictionary. Look up “queue” → flip to Q, scan ~5 pages, found. A linear scan would mean reading every page. Each lookup is O(log n) instead of O(n).

The index is sorted by key, so a B-tree also helps with:

• Range queries — once you’ve found the first matching row, the rest are physically next to it.
• Sorting — ORDER BY indexed_column can scan the index in order and skip a sort step.
• Prefix lookups — LIKE 'foo%' works because B-tree is sorted; it finds the prefix and walks forward.

But not with:

• Suffix or substring matches — LIKE '%bar' or '%bar%' can’t use a B-tree (the prefix is unknown). Use a pg_trgm GIN index or a real search engine.
• Negation — WHERE x <> 5 rarely uses a B-tree (almost every row qualifies).
• Function results — WHERE LOWER(email) = 'a@b.com' can’t use an index on email. Index on LOWER(email) instead.

A worked example — same query, with and without an index

CREATE TABLE events (
    id      bigserial PRIMARY KEY,
    user_id int       NOT NULL,
    ts      timestamptz NOT NULL,
    payload text
);
-- assume 100M rows, no indexes other than the implicit PK

EXPLAIN ANALYZE
SELECT * FROM events WHERE user_id = 42 AND ts >= '2026-04-01';

Without an index on (user_id, ts):

Seq Scan on events  (cost=0.00..2050000 rows=520 width=...) (actual time=0.1..8200 rows=520 loops=1)
  Filter: ((user_id = 42) AND (ts >= '2026-04-01'))
  Rows Removed by Filter: 99,999,480
Planning Time: 0.2 ms
Execution Time: 8203.7 ms

8 seconds. The planner read every row, threw away 99.99% of them.

After:

CREATE INDEX events_user_ts ON events (user_id, ts);

Index Scan using events_user_ts on events  (cost=0.56..125 rows=520 width=...) (actual time=0.1..2.3 rows=520 loops=1)
  Index Cond: ((user_id = 42) AND (ts >= '2026-04-01'))
Execution Time: 2.4 ms

3,400× faster. Same query, same answer.

Composite indexes — column order matters

A B-tree on (a, b, c) supports queries on:

• WHERE a = ?
• WHERE a = ? AND b = ?
• WHERE a = ? AND b = ? AND c = ?
• WHERE a = ? AND b > ?
• ORDER BY a, b, c

It does not efficiently support:

• WHERE b = ? alone (skips the index — Postgres can sometimes do an “index skip scan” but it’s a fallback).
• WHERE c = ? alone.

The rule: leading columns must be used for the index to help. Pick the leading column as the one most often used for equality or range, and the most selective.

For events_user_ts (user_id, ts):

• WHERE user_id = 42 AND ts >= '...' → index works perfectly.
• WHERE ts >= '...' (without user_id) → no help. Make a separate index on (ts).

Specialized indexes

Hash

CREATE INDEX users_email_hash ON users USING hash (email);

Equality only. In Postgres 10+, hash indexes are crash-safe and work, but the wins over B-tree are rarely worth the loss of range support. Default to B-tree; reach for hash only if benchmarking shows a real win.

GIN — Generalized Inverted Index

For containment in arrays, jsonb, full-text:

CREATE INDEX events_payload_gin ON events USING gin (payload);
-- supports: WHERE payload @> '{"kind":"click"}'

CREATE INDEX docs_body_fts ON docs USING gin (to_tsvector('english', body));
-- supports: WHERE to_tsvector('english', body) @@ 'machine learning'

GIN is the right index for jsonb fields and Postgres full-text search. See JSON in SQL (SQL 206) for details.

GiST

For geometry (PostGIS), ranges, and similarity (pg_trgm for substring matching):

CREATE EXTENSION pg_trgm;
CREATE INDEX users_name_trgm ON users USING gist (name gist_trgm_ops);
-- supports: WHERE name ILIKE '%john%'

BRIN — Block Range INdex

For very large, naturally-ordered tables (event logs, time-series). Stores the min/max value per block of pages. Tiny — orders of magnitude smaller than B-tree — but only useful when the column is correlated with physical order on disk.

CREATE INDEX events_ts_brin ON events USING brin (ts);

For an append-only events table where rows arrive in time order, a BRIN index on ts is ~1000× smaller than a B-tree and almost as fast for range scans. For mixed-update tables, BRIN degrades fast.

Partial and expression indexes

Partial — index only some rows

CREATE INDEX active_users_email
    ON users (email)
    WHERE deleted_at IS NULL;

Only the live users are indexed. Smaller, faster, and queries that include the same predicate (WHERE deleted_at IS NULL) can use the index.

Excellent for:

• “Active” / “current” subsets of soft-deleted tables.
• Sparse status flags (WHERE status = 'pending' when 0.1% of rows are pending).
• Avoiding indexing NULL values: WHERE col IS NOT NULL.

Expression — index a computed value

CREATE INDEX users_email_lower ON users (LOWER(email));
-- now: WHERE LOWER(email) = 'foo@bar.com'  uses the index

The query expression must match the index expression exactly. Useful for case-insensitive lookups, day-truncation of timestamps, JSON path extracts.

Covering indexes — INCLUDE for index-only scans

CREATE INDEX events_user_ts_inc
    ON events (user_id, ts)
    INCLUDE (payload);

The included columns aren’t part of the search key but are stored in the index leaves. A query that only reads payload after looking up by (user_id, ts) can use index-only scan — never touches the table. Useful for hot read paths where you want to skip the heap entirely.

The cost: the index gets bigger. Don’t INCLUDE everything.

When indexes hurt

• Write amplification. Every INSERT/UPDATE/DELETE updates every relevant index. 10 indexes on a high-write table → 10× the write cost.
• Plan misuse. A composite index on (country, signup_date) doesn’t help a query that filters only by signup_date — but it’s still on disk, still costs writes.
• Bloat. Postgres MVCC means deleted rows aren’t immediately removed; indexes accumulate dead pointers until VACUUM. Heavily-updated tables develop bloated indexes that hurt performance.
• Index hot spots. A monotonically increasing key (auto-increment ID, recent-timestamp) concentrates writes on the rightmost B-tree page, potentially serializing inserts on that lock.

The “more indexes is always better” instinct is wrong. The right answer is “index the columns your real queries filter and join on, no more.”

Common pitfalls

• No index on the FK side of a join. JOIN child ON child.parent_id = parent.id is slow if child.parent_id isn’t indexed.
• Function on the column kills the index. WHERE LOWER(email) = ... ignores idx(email). Index LOWER(email) instead.
• Cast on the column kills the index. WHERE id::text = '42' ignores idx(id). Cast the literal: WHERE id = 42.
• OR across two columns rarely uses two indexes. Postgres can do a “BitmapOr” but it’s often faster to rewrite as UNION.
• Wrong column order. (date, user_id) doesn’t help WHERE user_id = ?; (user_id, date) does. Pick the equality leading column.
• Index on a low-cardinality column. WHERE is_active = true over a column with two values isn’t worth indexing — the planner usually picks a sequential scan anyway. A partial index WHERE is_active = true can win.

Production patterns for ML

1. The “feature lookup” composite index. Almost every per-user feature query is WHERE user_id = ? AND ts >= ?:

CREATE INDEX features_user_ts ON features (user_id, ts);

This single index supports point-in-time lookups efficiently. If you also query “the most recent feature value”:

CREATE INDEX features_user_ts_desc ON features (user_id, ts DESC);

The DESC matters when you ORDER BY ts DESC LIMIT 1 — the index is already in the right order, no sort needed.

2. BRIN for event logs. A 10TB events table append-only by ts:

CREATE INDEX events_ts_brin ON events USING brin (ts);

vs a B-tree at hundreds of GB. Range scans (WHERE ts BETWEEN ...) work nicely; equality lookups don’t. Pair with a B-tree on (user_id) for the per-user lookup path.

Resources

• Use The Index, Luke — use-the-index-luke.com — the canonical free book on indexing.
• PostgreSQL — index types — postgresql.org/docs
• PostgreSQL — index documentation — postgresql.org/docs
• PostgreSQL documentation — postgresql.org/docs
• Designing Data-Intensive Applications, ch. 3 — dataintensive.net — storage internals.