Database Indexing Deep Dive

Two developers write the exact same query against the exact same data. For one of them it returns in two milliseconds. For the other it takes two minutes and drags the whole server down with it. The SQL is identical. The difference is invisible — it lives in a data structure the database keeps quietly on the side, called an index. Indexes are the single highest-leverage tool you have for database performance, and also the one most developers understand the least. Add too few and everything crawls; add too many and every write slows down and your disk fills up. Let's demystify them.

The Mental Model: A Book's Index

Imagine a 900-page book with no index. To find every mention of "Postgres," you'd read all 900 pages. That's a full table scan — the database reading every row to find the ones you want. Now imagine the index at the back: "Postgres … 42, 118, 351." You flip straight to those pages. That's an index seek. The book's content didn't change; you just added a sorted lookup structure that points into it.

A database index is the same idea. It's a separate, sorted copy of one or more columns, with pointers back to the full rows. The database maintains it automatically as you insert, update, and delete. You trade a little write speed and disk space for potentially enormous read speed.

The Workhorse: The B-Tree

The default index in essentially every relational database — Postgres, MySQL, SQL Server, SQLite — is a B-tree (specifically a B+ tree). Picture a shallow, bushy tree: a root node at the top, a few layers of branches, and the actual sorted keys in the leaves. Because the tree is wide and shallow, even a table with a billion rows is only a handful of levels deep. Finding a value means following three or four pointers instead of scanning a billion rows.

That structure is why B-trees are good at so many things:

CREATE INDEX idx_users_email ON users (email);

SELECT * FROM users WHERE email = 'ada@example.com';   -- equality
SELECT * FROM users WHERE email > 'm';                 -- range
SELECT * FROM users ORDER BY email;                    -- sorted output
SELECT * FROM users WHERE email LIKE 'ada%';           -- prefix match

All four benefit from the same index, because a B-tree keeps keys in sorted order. Note the last one carefully: LIKE 'ada%' (a prefix) can use the index, but LIKE '%ada' (a suffix) cannot — there's no way to seek to "words ending in ada" in an alphabetical list.

Composite Indexes and the Left-Prefix Rule

You can index several columns at once. The order matters enormously:

CREATE INDEX idx_orders_cust_date ON orders (customer_id, order_date);

Think of this like a phone book sorted by last name, then first name. It's great for finding "everyone named Smith" and "Smith, John" — but useless for finding "everyone named John," because first names are scattered throughout. This is the left-prefix rule: a composite index can be used for a query only if the query filters on a leading subset of its columns.

-- Uses the index (leading column present):
WHERE customer_id = 42
WHERE customer_id = 42 AND order_date > '2026-01-01'

-- Does NOT use the index efficiently (skips the leading column):
WHERE order_date > '2026-01-01'

The practical rule: put the columns you filter on by equality first, and the column you filter by range (or sort by) last.

A corollary that saves real disk and write overhead: a leading column of a composite index already acts as an index on that column by itself. If you have INDEX (name, age), don't also create INDEX (name) — anything the narrower index could do, the composite already does just as well, since a B-tree's sorted order means the leading column(s) alone are perfectly seekable. Keep the single-column index only if it's genuinely smaller and serves a hot, name-only query where trimming the extra key width measurably helps — otherwise it's a duplicate the database still has to maintain on every write for zero benefit.

Covering Indexes: Never Touch the Table

Normally an index gets you to the right rows, then the database goes back to the main table to fetch the columns you actually asked for. But if the index already contains every column the query needs, the database can answer entirely from the index and skip the table lookup. That's a covering index, and it's one of the biggest wins available:

-- Query needs only customer_id and total
SELECT total FROM orders WHERE customer_id = 42;

-- This index "covers" it — total comes along for the ride
CREATE INDEX idx_orders_cust_total ON orders (customer_id) INCLUDE (total);

(In MySQL, you'd add the extra column to the key itself; Postgres and SQL Server support the dedicated INCLUDE clause, which keeps the extra columns in the leaves without making them part of the searchable key.)

When You Need More Than a B-Tree

B-trees are the default for good reason, but some problems call for specialized index types (the richest set lives in PostgreSQL):

• GIN — for "many values inside one row." Full-text search, JSONB, and array columns. If you're querying inside a JSON document or asking "does this array contain X," you want GIN.

  CREATE INDEX idx_docs_body ON docs USING GIN (to_tsvector('english', body));
  CREATE INDEX idx_events_data ON events USING GIN (payload jsonb_path_ops);

• GiST / SP-GiST — for geometric, spatial, and range data. "Find every store within 5 km" (PostGIS) or overlapping time ranges.

• BRIN — Block Range INdex. Tiny and brilliant for huge tables where the data is naturally ordered on disk, like an append-only log with a timestamp. A BRIN index on a billion-row time-series table can be a few kilobytes instead of many gigabytes.

  CREATE INDEX idx_logs_time ON logs USING BRIN (created_at);

• Hash — equality only, no ranges. Rarely worth choosing over a B-tree in practice.

Specialized Tricks: Partial and Expression Indexes

Two features that punch well above their weight.

A partial index covers only the rows matching a condition — smaller, faster, and cheaper to maintain:

-- 95% of orders are 'complete' and never queried by status.
-- Only index the ones you actually search for.
CREATE INDEX idx_orders_pending ON orders (created_at)
    WHERE status = 'pending';

An expression index indexes the result of a function, so a transformed lookup can still use an index:

-- WHERE lower(email) = ... normally can't use a plain email index.
CREATE INDEX idx_users_email_lower ON users (lower(email));
SELECT * FROM users WHERE lower(email) = 'ada@example.com';   -- now indexed

The Silent Killers: Why Your Index Isn't Being Used

Adding an index is no guarantee it gets used. The classic reasons a query ignores a perfectly good index:

1. A function wraps the column. WHERE lower(email) = ... can't use an index on email (use an expression index).
2. A leading wildcard. LIKE '%term' can't use a B-tree.
3. Implicit type mismatch. WHERE phone = 5551234 when phone is text forces a conversion that defeats the index.
4. Low selectivity. If a column is 90% the value you're filtering for, a full scan is genuinely faster than bouncing in and out of an index — and the planner knows it.
5. Stale statistics. The planner decides based on its estimate of how many rows match. If those stats are out of date, it guesses wrong. Run ANALYZE (Postgres) or ANALYZE TABLE (MySQL) to refresh them.

Your Most Important Tool: EXPLAIN

Never guess whether an index is helping — ask the database. EXPLAIN ANALYZE shows the actual plan and real timings:

EXPLAIN ANALYZE
SELECT * FROM orders WHERE customer_id = 42;

What you're looking for:

• Seq Scan / "Full Table Scan" on a big table you filter heavily → probably a missing index.
• Index Scan / Index Seek → good, the index is being used.
• Index Only Scan → excellent, it's a covering index; the table was never touched.
• A rows estimate that's wildly different from actual rows → stale statistics; run ANALYZE.

The Cost Side: Why Not Index Everything?

Every index is a second data structure the database must keep in sync. That has real costs:

• Writes slow down. Every INSERT and DELETE touches every index on the table, since a row is fully added or removed. An UPDATE only pays for the indexes on the columns it actually changes — but a table with ten indexes still means ten times the maintenance work on the columns that get touched most.
• Disk and memory. Indexes can easily rival the size of the table itself, and they compete for cache.
• The planner has more to think about, and unused indexes are pure overhead — cost with no benefit.

Find the dead weight and drop it. Postgres tracks index usage in pg_stat_user_indexes:

SELECT indexrelname, idx_scan
FROM pg_stat_user_indexes
WHERE idx_scan = 0;   -- indexes that have never been used

Quick Reference: Which Index When

Indexing Checklist

✅ Index the columns in your WHERE, JOIN, and ORDER BY clauses
✅ In composite indexes, put equality columns before range columns
✅ Use EXPLAIN ANALYZE to confirm an index is actually used
✅ Consider a covering index for hot, read-heavy queries
✅ Use partial indexes when most rows are irrelevant to the query
✅ Keep statistics fresh with ANALYZE
✅ Periodically drop indexes with zero scans

Conclusion: Turns out that indexing isn't a dark art after all - it's a set of trade-offs you can reason about. An index is a sorted shortcut: it makes matching reads dramatically faster in exchange for a little write overhead and disk. Learn to read EXPLAIN, understand why a B-tree loves sorted ranges and hates leading wildcards, and reach for the specialized types when the shape of your data calls for them. Do that, and the difference between the two-millisecond query and the two-minute one stops being luck — it becomes something you control.