Back
PostgreSQLBackendPerformance

How Database Indexes Actually Work

June 24, 202512 min read

I once asked my senior a question that seemed obvious to me at the time: if indexes make queries faster, why don't we just put an index on every column?

He smiled, didn't answer, and asked me to figure it out myself. So I did. I dug into docs, read through Postgres internals, and found this video by Arpit Bhayani that clicked everything into place. This post is my attempt to write down what I learned in a way that would have helped past me.

What is an index, really?

At its core, an index is a separate data structure that your database maintains alongside your table. It stores a sorted copy of one or more columns, along with pointers back to where the actual rows live on disk.

Think of it like the index at the back of a textbook. The book's pages are your table rows — stored in the order they were written. The index is that sorted list at the end: "Concurrency — pages 142, 231, 408." Without it, you'd have to read every page. With it, you jump straight to what you need.

PostgreSQL's most common index type is a B-tree (balanced tree). That's what you get when you run CREATE INDEX without specifying a type.

What actually happens when you run CREATE INDEX?

This is the part most tutorials skip. Let's say you do:

CREATE INDEX idx_orders_user_id ON orders(user_id);

Here's what PostgreSQL actually does:

  1. 1Full sequential scan of the table. Postgres reads every row in orders to extract the user_id values and their corresponding row addresses (called ctid — the physical location on disk).
  2. 2Sort the extracted values. It sorts all those (user_id, ctid) pairs. This is potentially a large sort — if the table is big, it might spill to disk.
  3. 3Build the B-tree bottom-up. Sorted data is perfect for building a B-tree efficiently. Postgres fills leaf pages left to right, then builds internal pages up from those. This is much faster than inserting one value at a time.
  4. 4Write index pages to disk. The finished B-tree gets written as a set of 8KB pages — same page size as the table itself.
  5. 5Lock the table (briefly, or not at all). A regular CREATE INDEX locks writes for the entire duration. CREATE INDEX CONCURRENTLY does multiple passes and only takes short locks — but it takes longer and can fail if there are conflicts.

The whole thing can take minutes on a large table. During that time, your database is doing real work — reading, sorting, writing. It's not free.

The B-tree structure

A B-tree has three kinds of nodes: the root, internal nodes, and leaf nodes.

Leaf nodes are where the actual index entries live. Each entry contains the indexed value and a pointer to the row (ctid). Leaf nodes are linked together in a doubly-linked list — this is what makes range queries fast. You find the start of the range, then just walk forward.

Internal nodes are the routing layer. They store separator keys that tell you "go left for values less than X, go right for values greater than X." A B-tree stays balanced — every leaf node is at the same depth from the root.

When you query WHERE user_id = 12345, Postgres starts at the root, follows the right pointers at each level, and arrives at a leaf node in O(log n) time. For 8 million rows, that's roughly 23 comparisons instead of 8,000,000.

When the query planner uses your index (and when it doesn't)

Here's something that surprises people: adding an index doesn't mean Postgres will use it.

The query planner estimates the cost of each possible plan and picks the cheapest one. For very selective queries — "find me this one user" — an index scan is almost always cheaper. But for low-selectivity queries — "find all users where status = 'active'" where 70% of rows are active — a sequential scan might actually be faster. Reading 70% of a table via random index seeks is worse than just scanning the whole thing in order.

You can see exactly what Postgres decides with:

EXPLAIN ANALYZE SELECT * FROM orders WHERE user_id = 12345;

Look for Index Scan vs Seq Scan. If Postgres is ignoring your index on a query where you think it should use it, check the selectivity — and make sure your table statistics are up to date with ANALYZE.

Composite indexes: order matters more than you think

If you index on (user_id, created_at), that index is useful for:

  • Queries filtering on user_id alone
  • Queries filtering on user_id AND created_at
  • Queries ordering by user_id, created_at

But it's not useful for queries filtering on created_at alone. The leftmost column rule: a composite index can only be used if you include the leading columns in your query predicates.

This is why index design matters. The order you specify columns in your index should match the most common access patterns — most selective column first is a common heuristic, but it's not always right.

Covering indexes: the hidden win

After finding the right rows in an index, Postgres usually has to go back to the actual table to fetch the columns you selected. This is called a "heap fetch" and it involves random disk reads — slow.

A covering index includes all the columns your query needs, so Postgres never has to touch the table at all:

-- If you always query these three columns together:
CREATE INDEX idx_covering ON orders(user_id) INCLUDE (status, created_at);

Now a query for SELECT status, created_at FROM orders WHERE user_id = 12345 can be answered entirely from the index. Postgres calls this an index-only scan. It shows up in EXPLAIN and it's noticeably faster for read-heavy workloads.

The real cost of indexes

Nobody talks enough about the downsides. Here's what you're paying for every index you add:

Write overhead

Every INSERT, UPDATE, and DELETE has to update all relevant indexes. An UPDATE on an indexed column is basically a delete + insert in the index. If you have 6 indexes on a table and you do a bulk insert of 100,000 rows, you're maintaining 6 additional data structures in real time. This compounds under high write load.

Storage

Indexes take space. A B-tree index on a UUID column in a table with 10 million rows can easily be 500MB+. Multiply by multiple indexes and you're looking at a significant storage bill, especially in cloud environments. Run SELECT pg_size_pretty(pg_relation_size('your_index_name')) to check.

Index bloat

When rows get updated or deleted, Postgres marks old index entries as dead but doesn't immediately reclaim the space. Over time, your indexes grow and have gaps — "bloat." This makes them slower because more pages need to be read. REINDEX or VACUUM helps, but bloat in write-heavy tables is a real operational concern.

Planning time

The more indexes you have, the more plans the query planner has to evaluate. For simple queries this is negligible. For complex queries with many joins and many indexes, planning time can become measurable.

When NOT to add an index

Indexes are not always the answer. Skip them when:

  • The table is small. Sequential scans on small tables are often faster because everything fits in memory anyway.
  • The column has very low cardinality. Indexing a boolean is_deleted column where 95% of rows are false often won't help — Postgres will just scan the table.
  • You're write-heavy and read-light. A table that gets millions of inserts per hour and is rarely queried will suffer more from index maintenance than it will gain from lookup speed.
  • You're running analytics on the whole table. Full table scans for aggregations are expected. Adding an index won't help a SELECT COUNT(*) FROM events that has to touch every row.

What I do now

After going through this, my process has changed. I don't add indexes upfront based on intuition. I:

  1. Ship the feature, let it run
  2. Check slow query logs and pg_stat_statements to find actual slow queries
  3. Run EXPLAIN ANALYZE on the offenders
  4. Add targeted indexes only where the data shows I need them
  5. Monitor index usage with pg_stat_user_indexes — unused indexes are pure overhead

The answer to my original question — why not index every column — should be obvious by now. Every index you add is a promise you're making to maintain a separate data structure on every write, forever. That cost compounds. Index what your queries actually need, verify with EXPLAIN ANALYZE, and drop what isn't being used. That's the whole game.