How database indexes actually work

I spent six months adding indexes to every slow query before I understood what an index actually does. Turns out, some of those indexes made things worse.

The problem was not the indexes themselves. The problem was that I treated them like magic. Slow query? Add an index. Still slow? Add another one. I never looked at what the database was actually doing with them.

What an index is

An index is a separate data structure that sits alongside your table. Think of a book's index at the back. The book itself has all the content in order of chapters and pages. The index at the back is sorted alphabetically, and each entry tells you which page to find that topic on.

A database index works the same way. Your table stores rows in the order they were inserted (roughly). The index stores a sorted copy of specific columns, with pointers back to the full rows. When you search for a value, the database can look it up in the sorted index instead of scanning every row in the table.

B-tree indexes

The default index type in PostgreSQL (and most relational databases) is a B-tree. It is a balanced tree structure where every path from the root to a leaf has the same length. This guarantees logarithmic lookup time regardless of table size.

Here is a simplified view of how a B-tree organizes values from 1 to 100:

graph TD
    A["Root: 50"] --> B["10, 30"]
    A --> C["70, 90"]
    B --> D["1-9"]
    B --> E["11-29"]
    B --> F["31-49"]
    C --> G["51-69"]
    C --> H["71-89"]
    C --> I["91-100"]

The root node contains a value that splits the data in half. Internal nodes split their range further. Leaf nodes at the bottom contain the actual indexed values and pointers to the corresponding table rows. To find a specific value, the database starts at the root and follows the appropriate branch down. For a table with a million rows, this takes maybe 3 or 4 hops instead of scanning all million rows.

The leaf nodes are also linked together, so range queries like WHERE id BETWEEN 50 AND 70 can find the starting point and then scan forward through the linked leaves.

Reading EXPLAIN ANALYZE

You cannot reason about index performance without looking at query plans. EXPLAIN ANALYZE runs the query and shows you exactly what the database did.

Here is a query without an index on a users table with 100,000 rows:

EXPLAIN ANALYZE SELECT * FROM users WHERE email = 'john@example.com';

Seq Scan on users  (cost=0.00..1834.00 rows=1 width=68) (actual time=12.431..12.431 rows=1 loops=1)
  Filter: (email = 'john@example.com'::text)
  Rows Removed by Filter: 99999
Planning Time: 0.085 ms
Execution Time: 12.456 ms

Seq Scan means the database read every single row. It checked 100,000 rows to find one match. The cost=0.00..1834.00 is the planner's estimate (in arbitrary units) of how expensive the operation is. The actual time is the real wall-clock time in milliseconds.

Now add an index and run it again:

CREATE INDEX idx_users_email ON users (email);
EXPLAIN ANALYZE SELECT * FROM users WHERE email = 'john@example.com';

Index Scan using idx_users_email on users  (cost=0.42..8.44 rows=1 width=68) (actual time=0.028..0.029 rows=1 loops=1)
  Index Cond: (email = 'john@example.com'::text)
Planning Time: 0.091 ms
Execution Time: 0.052 ms

Index Scan means it used the B-tree to jump directly to the matching row. Execution time dropped from 12ms to 0.05ms. That is a 240x improvement for this query.

There is also a third scan type: Bitmap Index Scan. PostgreSQL uses this when the query matches too many rows for a regular index scan but not enough to justify a full sequential scan. It builds a bitmap of matching pages in memory, then fetches those pages from the table. You will see this with queries that return a moderate number of rows, maybe 5-15% of the table.

When indexes hurt

Indexes are not free. Every time you insert, update, or delete a row, the database has to update every index on that table too. Five indexes means five extra write operations for every insert. For write-heavy tables, this overhead adds up fast.

Low selectivity columns are useless to index. If you have a status column with two possible values and a roughly 50/50 split, an index on that column will not help. The database is smarter than you think. It knows that scanning half the table through an index (with all the random I/O that implies) is slower than just doing a sequential scan. A good rule of thumb: if a query returns more than 10-15% of the table, the planner will probably ignore your index.

Index bloat. In PostgreSQL, when you update a row, the old version sticks around (this is how MVCC works). The index entries pointing to dead rows pile up over time. Regular VACUUM cleans this up, but on busy tables the bloat can get significant before vacuuming catches up.

Memory pressure. Indexes live in memory when they are being used. More indexes means more memory consumed by the buffer cache for index pages, leaving less room for actual table data.

Composite indexes and column order

A composite index covers multiple columns. The column order matters a lot.

CREATE INDEX idx_orders_customer_date ON orders (customer_id, created_at);

This index works like a phone book sorted by last name, then first name. It can efficiently serve:

• WHERE customer_id = 42 (uses the first column)
• WHERE customer_id = 42 AND created_at > '2022-01-01' (uses both columns)
• WHERE customer_id = 42 ORDER BY created_at (uses both columns)

But it cannot efficiently serve:

• WHERE created_at > '2022-01-01' alone (the first column is not constrained)

This is the leftmost prefix rule. The index is sorted by the first column first, then by the second column within groups of the first. Without constraining customer_id, the created_at values are scattered throughout the index. The database would have to scan the whole index, which is no better than a sequential scan.

If you need to query by created_at alone, you need a separate index on that column.

Partial and expression indexes

These are two of my favorite PostgreSQL features. They let you build smaller, more targeted indexes.

Partial indexes only include rows that match a condition:

CREATE INDEX idx_active_users_email ON users (email) WHERE active = true;

If 90% of your users are inactive and you only ever query active ones, this index is 10x smaller than a full index on email. Smaller means faster to scan, less memory, less write overhead.

Expression indexes let you index the result of a function:

CREATE INDEX idx_lower_email ON users (lower(email));

Now WHERE lower(email) = 'john@example.com' uses the index. Without this, a regular index on email would not help because the lower() function transforms the value, and the planner does not know that lower('John@example.com') matches john@example.com in a plain index.

Rules of thumb

After enough time staring at EXPLAIN ANALYZE output, here is what I actually follow:

• Index columns you filter on (WHERE), join on (JOIN ON), and sort on (ORDER BY)
• Put equality columns before range columns in composite indexes
• Do not index boolean columns or anything with very few distinct values
• Check for unused indexes periodically. pg_stat_user_indexes tells you how often each index gets scanned
• Every index you add slows down writes. If a table gets way more writes than reads, think twice
• Always measure with EXPLAIN ANALYZE. Do not guess. The planner is smarter than your intuition

I wrote more about SQLite's approach to indexing, which has its own quirks. And I have a broader collection of PostgreSQL tips that covers more than just indexes.

Sources

• PostgreSQL Documentation: Indexes
• Use The Index, Luke
• PostgreSQL Documentation: Using EXPLAIN
• PostgreSQL Documentation: Index Types