A Database Index Is Just a Sorted List You Paid For

A query that took eleven seconds on a table of two million rows dropped to four milliseconds the moment I added one index, and the person watching over my shoulder asked what magic had just happened. There wasn’t any. The table went from being scanned row by row, in whatever physical order it happened to be stored, to being looked up through a sorted structure that could jump straight to the matching rows without touching the rest. That’s the entire trick behind every index in every database — Postgres, MySQL, SQLite, all of them. It’s a sorted copy of some columns, maintained automatically, that lets the database avoid checking rows it already knows can’t match.

The word “index” carries some unearned mystique because most people encounter it only as a CREATE INDEX statement that either works or doesn’t, with the internals hidden behind the query planner. Open that box up and the internals are genuinely graspable — a specific, well-understood tree structure doing a specific, well-understood job, with a real cost attached that the marketing-free version of every database tutorial should mention up front and usually doesn’t.

Life without an index: the sequential scan

Without an index, finding a row means the database checks every single row in the table, in whatever order they physically sit on disk, comparing each one against your WHERE clause. This is a sequential scan, and it’s exactly as slow as it sounds for a large table:

1
2
3

EXPLAIN ANALYZE SELECT * FROM orders WHERE customer_id = 48213;
-- Seq Scan on orders  (cost=0.00..48291.00 rows=12 width=96)
--                     (actual time=0.031..142.887 rows=12 loops=1)

Every row gets examined, whether or not it matches, because nothing tells the database where the matching rows live. For a small table this costs nothing noticeable. For a table with millions of rows, checking every single one to find twelve matches is the entire eleven seconds from that opening story.

What CREATE INDEX actually builds

Run CREATE INDEX idx_customer ON orders (customer_id); and Postgres (like almost every mainstream database) builds a B-tree: a balanced tree structure where every leaf node is at the same depth, keys are kept in sorted order, and each internal node holds enough keys to point efficiently to the right child. The genuinely important property is that looking up a value takes roughly log(n) comparisons instead of n — for a million rows, that’s the difference between checking a million rows and checking around twenty.

You can watch the plan change immediately after creating the index:

1
2
3
4

EXPLAIN ANALYZE SELECT * FROM orders WHERE customer_id = 48213;
-- Index Scan using idx_customer on orders
--   (cost=0.43..8.45 rows=12 width=96)
--   (actual time=0.019..0.024 rows=12 loops=1)

The planner walked down the B-tree, found the leaf nodes holding customer_id = 48213, and read only those rows plus a small amount of tree traversal — a few page reads instead of the entire table. That’s the entire performance win, and it’s why “add an index” is the single highest-leverage change most people can make to a slow query without touching a line of application code.

The part every “just add an index” tutorial skips

A B-tree doesn’t maintain itself. Every INSERT, UPDATE or DELETE on the indexed column has to update the tree’s structure to keep it sorted and balanced — inserting a new key in the middle of a full leaf node, splitting that node, potentially cascading the split up through parent nodes. That work happens on every single write, not just occasionally, and it happens for every index on the table, not just one. A table with six indexes pays that maintenance cost six times per write:

1
2
3
4
5

-- watch write latency increase as indexes accumulate
CREATE INDEX idx1 ON orders (customer_id);
CREATE INDEX idx2 ON orders (order_date);
CREATE INDEX idx3 ON orders (status);
-- every INSERT into orders now updates three B-trees, not one

This is the trade-off nobody puts on the tin: an index makes reads faster by making writes slower, and the slowdown compounds with every additional index on the table. Postgres tuning for homelabbers covers several settings that interact directly with this cost — maintenance_work_mem in particular controls how efficiently Postgres can build and rebuild these structures in the first place.

Why a covering index sometimes skips the table entirely

There’s a refinement worth knowing because it explains otherwise-confusing EXPLAIN output: if every column your query needs is already present in the index itself, Postgres can answer the query straight from the B-tree without ever touching the underlying table row — this is an index-only scan.

1
2
3
4

CREATE INDEX idx_covering ON orders (customer_id) INCLUDE (order_date, status);

EXPLAIN ANALYZE SELECT order_date, status FROM orders WHERE customer_id = 48213;
-- Index Only Scan using idx_covering on orders

INCLUDE bundles extra columns into the index’s leaf nodes purely so queries needing only those columns never have to visit the table’s actual heap storage at all — a second, smaller layer of “don’t touch data you don’t strictly need,” stacked on top of the B-tree’s own “don’t touch rows you don’t strictly need.”

Composite indexes and the column-order trap

An index on multiple columns is sorted by the first column, then the second within each group of equal first-column values, then the third within that, exactly like sorting a spreadsheet by three columns in sequence. This means column order in a composite index matters enormously, and it’s the single most common reason a seemingly correct index doesn’t get used:

1
2
3
4
5
6
7

CREATE INDEX idx_multi ON orders (customer_id, order_date);

-- uses the index efficiently: customer_id is the leading column
SELECT * FROM orders WHERE customer_id = 48213 AND order_date > '2023-01-01';

-- can't use the index efficiently: order_date alone isn't the leading column
SELECT * FROM orders WHERE order_date > '2023-01-01';

The second query can’t skip through the B-tree the way the first one does, because the tree is sorted by customer_id first — every order_date value is scattered across the whole structure rather than sitting together. Getting composite index column order backwards is responsible for a large fraction of “I added an index and the query is still slow” support questions.

Why B-trees and not hash tables, when hashing is faster for equality

It’s a fair question: a hash index looks up an exact match in constant time, O(1), faster in principle than a B-tree’s O(log n). Postgres does actually offer hash indexes, and for pure equality lookups they can be marginally faster. The reason B-trees are the default and hash indexes are the exception comes down to what a hash table gives up to get that speed: it destroys ordering entirely. A hash function scatters keys uniformly across buckets specifically to avoid clustering, which means a hash index can answer “does this exact value exist” but has no way to answer “give me everything between these two values” without checking every bucket:

1
2
3
4
5
6
7

-- a hash index handles this well
CREATE INDEX idx_hash ON orders USING hash (customer_id);
SELECT * FROM orders WHERE customer_id = 48213;

-- a hash index cannot help with this at all — no ordering to exploit
SELECT * FROM orders WHERE order_date BETWEEN '2023-01-01' AND '2023-06-30';
SELECT * FROM orders ORDER BY order_date;

Range queries, sorting, and >/< comparisons all depend on the index preserving order, which a B-tree does by construction and a hash table actively can’t. Since range and sort queries vastly outnumber pure-equality-only lookups in most real applications, B-trees end up the sensible universal default, with hash indexes reserved for the narrow case of high-volume exact-match lookups where ordering genuinely never matters.

Partial indexes: paying the write cost on fewer rows

Not every row in a table is equally worth indexing. A status column on an orders table might have millions of completed rows and a few hundred pending ones, with almost every query that cares about status specifically asking for the pending ones. A plain index covers every row regardless of which values actually get queried; a partial index restricts the B-tree to only the rows matching a condition:

1
2
3
4

CREATE INDEX idx_pending ON orders (order_date) WHERE status = 'pending';

SELECT * FROM orders WHERE status = 'pending' ORDER BY order_date;
-- uses idx_pending, a fraction of the size of a full-table index

The maintenance cost drops to match: an UPDATE that changes a completed row’s order_date never touches idx_pending at all, because that row was never eligible for inclusion in the first place. This is one of the most underused optimisations in ordinary application databases — most schemas either index a column fully or not at all, when the actual query pattern only ever cares about a slice of the table’s rows.

Troubleshooting: when the index doesn’t help

• EXPLAIN shows a sequential scan even though an index exists. Check whether the query actually matches the index’s leading column, whether a function is wrapping the indexed column (WHERE LOWER(email) = ... won’t use a plain index on email), and whether table statistics are stale — ANALYZE orders; refreshes the planner’s row-count estimates, which sometimes flip its decision entirely.
• Writes got noticeably slower after adding several indexes. This is expected, not a bug — every index is B-tree maintenance work on every write. Audit pg_stat_user_indexes for indexes with near-zero scans; an unused index is pure write overhead with no corresponding read benefit and is usually safe to drop.
• An index exists but the planner still avoids it. For very small tables, a sequential scan can genuinely be cheaper than an index scan, because reading the whole tiny table sequentially costs less than the random-access page reads a B-tree traversal requires. The planner isn’t confused; a small enough table makes indexes actively pointless.
• Index bloat after heavy update/delete churn. Postgres B-trees don’t always reclaim space from deleted or updated entries immediately, leaving pages emptier than they should be over time. REINDEX CONCURRENTLY idx_name; rebuilds the structure without blocking writes, and is worth scheduling periodically on tables with heavy churn.
• A composite index exists but a query using only the second column is slow. This is the column-order trap from above — check pg_stat_user_indexes to confirm the index genuinely isn’t being scanned, then either reorder the composite index if the second-column query pattern is common enough to matter, or add a separate single-column index specifically for it.
• Building an index on a large existing table locks writes for too long. A plain CREATE INDEX takes a lock that blocks writes to the table for the duration of the build, which can be minutes on a large table. CREATE INDEX CONCURRENTLY builds the index without blocking writes, at the cost of a slower build and a small risk of needing a retry if it fails partway through.

Why “just add an index” is bad advice without a query in hand

The reflexive advice to index every foreign key and every column that ever appears in a WHERE clause treats indexes as free, and the B-tree maintenance cost above shows exactly why that reflex backfires on write-heavy tables. The better question to ask before adding one is: which specific, real query is slow, and what does EXPLAIN ANALYZE actually show it doing? An index added speculatively, without a slow query driving the decision, is a bet placed with no evidence — sometimes it pays off when that query pattern eventually shows up, more often it sits unused in pg_stat_user_indexes quietly taxing every write to a table nobody ever queries that way.

Is it worth reaching for

Every index you add is a bet that the read speedup on some specific query pattern is worth the write slowdown on every insert, update and delete touching that column, forever. For a table that’s read constantly and written rarely — a lookup table, a reference dataset — that bet is nearly always worth making. For a table under heavy write load with queries that rarely filter on a given column, an index there is pure cost with no corresponding benefit, and the honest answer to “should I index this” is to check pg_stat_user_indexes or the equivalent in your database, not to index defensively and hope. SQLite already ships as a production database for your homelab, and its B-tree indexes work through exactly the same trade-off — sorted structure bought at the price of write overhead, the same deal every database on the market is making on your behalf every time you type CREATE INDEX.