Database Indexes: From B-Trees to Production

Every backend eventually meets the same slow query. The table grows, the page that used to load in 50 milliseconds now takes 3 seconds, and someone says "just add an index." Sometimes that fixes it. Often it does not, and now you have slower writes too. This article covers how indexes actually work, when they help, when they hurt, and how to read a query plan before you touch anything, with Postgres examples throughout.

1. What an index really is

An index is a separate data structure that lets the database find rows without scanning the whole table. Postgres's default, the B-tree, keeps keys in sorted order across pages, so a lookup walks down the tree in logarithmic time instead of reading every row. Think of it like the index at the back of a textbook: you look up the term, get the page numbers, and jump straight there instead of reading the book cover to cover.

The key insight: an index speeds up reads by paying a price on writes. Every INSERT, UPDATE, and DELETE must also maintain each index on the table. That is the trade you are making, every time, with every index.

2. Read the plan before you add anything

The fastest optimization is information. Run EXPLAIN ANALYZE on the slow query against production-like data:

EXPLAIN ANALYZE
SELECT id, email FROM users WHERE email = '[e-mail]';

Estimated plans can lie, so look at the actual row counts. The gap between "rows estimated" and "rows actual" is where most performance mysteries live. Then check the scan type:

1. Seq Scan on a large table: the usual suspect. The planner read every row.
2. Index Scan or Bitmap Heap Scan: the index is being used. If it is still slow, check selectivity below.
3. Index Only Scan: the best case. The query never touched the table at all.

3. Selectivity decides whether the index matters

An index on a boolean column with two values is nearly useless: the planner still reads half the table. Indexes win when they are selective, when the lookup narrows millions of rows down to a handful. A unique email column is the perfect candidate. A status column with three values is usually not, unless it is combined with something else.

This is why "add an index on the WHERE column" is incomplete advice. Ask first: how many rows does this filter actually eliminate?

4. Composite indexes: order matters

When a query filters on two columns, one composite index beats two single-column indexes:

CREATE INDEX idx_orders_customer_date
ON orders (customer_id, created_at);

Column order follows selectivity and usage: the most selective, most frequently filtered column first. And remember the leftmost-prefix rule: this index serves queries filtering on customer_id alone, or on both columns, but not queries filtering only on created_at.

5. Covering indexes: skip the table entirely

Sometimes the query uses the index but still goes back to the table for one more column per row. Those heap fetches add up. A covering index includes the extra columns so the query is answered from the index alone:

CREATE INDEX idx_users_email_covering
ON users (email) INCLUDE (id, name);

That Index Only Scan in the plan is the payoff. Use INCLUDE for columns you read but never filter on; keep the key itself narrow.

6. The invisible index killers

These show up in plans as sequential scans that "should" have used an index:

1. Functions on the indexed column. WHERE lower(email) = ... disables a plain B-tree on email. Fix it with an expression index: CREATE INDEX ... ON users (lower(email)).
2. Type mismatches. Comparing a text column to a number forces a cast on every row. Match the types.
3. Leading wildcards. LIKE '%smith' cannot use a B-tree. Use trigram indexes (pg_trgm) if you need that pattern.
4. Stale statistics. If the planner's row estimates are wildly off, run ANALYZE on the table before blaming the index.

7. When indexes hurt

Every index costs on the write path and in storage. Tables with heavy INSERT loads and many indexes will show it in write latency. Bloated or unused indexes are pure cost: find them with pg_stat_user_indexes and drop the ones with near-zero scans. The engineers who add few deliberate indexes outperform the ones who add many hopeful ones.

Production checklist

1. EXPLAIN ANALYZE on production-like data before adding anything.
2. One composite index, ordered by selectivity, over several single-column ones.
3. Covering indexes (INCLUDE) for hot read paths.
4. Expression indexes where functions wrap filtered columns.
5. Monitor unused indexes with pg_stat_user_indexes; drop the dead ones.
6. Re-check after major data growth: selectivity changes, and so should your indexes.

Indexes are the highest-leverage tool in query performance, and the easiest to misuse. Measure first, add deliberately, and re-verify. Your write path will thank you.

What is the most surprising thing a query plan ever showed you?