Database Indexing: How Indexes Speed Up Reads (and Cost Writes)

This article owes its position to two earlier ones in the Databases cluster. Database sharding deferred the mechanics here (its decision was only where an index lives across a fleet, not how one works) and named indexing the cheaper lever to exhaust before splitting a dataset. The sharding vs replication comparison then fixed the ladder this article sits at the bottom of: indexing first, caching second, read replicas third, sharding the last resort. And the caching series made the same point from its side of the boundary: an index composes with caching, while a cache in front of a broken query only hides it. This is the article about fixing the query.

A database index is a data structure the database maintains alongside a table (sorted entries for a chosen subset of columns, each pointing at the row it summarizes) so that a query filtering on those columns can find its matches by descending a small structure instead of reading the table end to end. The read gets faster because the work gets smaller: a full scan’s cost grows with the table; an index lookup’s cost grows with the logarithm of it. The write gets slower for the same reason, because every index is another structure the write must maintain; the trade this whole article keeps pricing.

The read lever before all others

Without an index, a filtered read is a full scan: the database visits every page of the table and discards what does not match, so the query’s cost grows in lockstep with the table. With one, the cost grows with the logarithm of the table, the difference between work proportional to the dataset and work proportional to its depth. The database’s planner makes the choice per query, comparing the estimated cost of a scan against the estimated cost of an index descent, which is why the same query can flip plans as the table and its statistics change.

The ladder position is the strategic point, and the sharding vs replication comparison fixed it: index first, cache second, add read replicas third, and shard only when all of it is exhausted. Indexing is the first rung because it is the cheapest in every currency; local (no new component, no new consistency surface), reversible (an index can be dropped), and measurable (the database will show its chosen plan before and after the change, and reading that plan is the whole discipline of the fix). A read problem solved by an index stays solved on every path the read can take; a read problem solved by sharding is now a fleet’s problem.

Two asymmetries make the lever worth its price. Most workloads read far more than they write, so a cost moved from the read path to the write path lands on the rarer operation, the ledger indexes favor by default. And scans are indiscriminate about memory: a full scan evicts the buffer pool’s hot pages to make room for the table it is traversing, so one unindexed query slows the queries around it; an index lookup touches only its own few pages and leaves the pool to the working set. An index is thus also a memory decision, not only a query one.

The B-tree index: sorted, balanced, range-friendly

The default structure is the B-tree, and the two properties in its name are the two properties that matter. It is sorted: entries live in key order, so a lookup knows at every level which child to descend into, and a handful of comparisons per level narrows the candidates from millions to one. It is balanced: every leaf sits at the same depth, maintained by splits and merges as entries come and go, so no key hides in an unusually deep branch and every lookup costs the same number of page reads; a few levels cover tables with millions of rows, because each level multiplies the fan-out of the one above it.

Sortedness also buys the operations a filter alone doesn’t. A range predicate (dates in an interval, IDs between two values) walks the leaves in order instead of testing every row. A prefix match on a string starts at the prefix and stops where it ends. An ORDER BY on the indexed column can skip the sort entirely, because the index already did it. Hash indexes are the contrast worth knowing: constant-time equality lookups, but no order, so no ranges, no prefixes, no sort avoidance, a specialist for exact-match workloads. The generalization search engines use (the inverted index, the same sorted-copy idea pointed at words instead of column values) is another article’s machinery, and the same reasoning powers it.

Three variants complete the toolkit. A unique index is a constraint and an index at once; the database enforces uniqueness by consulting the structure it was going to search anyway. A partial index covers a filtered slice: the active orders, the unarchived rows, and leaves the cold bulk alone, shrinking the structure and its write tax for workloads whose queries only ever touch that slice. An expression index indexes a function of the columns; the lower-cased email, the extracted date, so a query that filters on the function can use it; the trap is symmetric: the query must apply the same expression the index did.

Clustered vs non-clustered: where the table lives

A clustered index decides where the table lives. The rows are stored in the index’s key order, which makes the clustered index the table: exactly one exists per table, usually on the primary key. The consequences reach writes, not just reads: sequential keys (auto-incrementing integers) append to the end of the structure, while random keys (hashes, random UUIDs) insert into the middle, forcing page splits and scattered storage. This is why table-design folklore warns against random primary keys: the row’s address is its position in a sorted structure, and sorting is a cost.

A non-clustered index (the secondary index) is a separate sorted structure whose entries point back at the row. In a heap table the pointer is physical; in a clustered table the secondary index stores the clustered key, and the lookup becomes two descents: find the entry, then find the row. That second hop is why the covering index exists: when the query’s selected and filtered columns all live in the index, the database answers from the index alone and never visits the table; the fastest read an index can serve, and the design answer to a hot query that will not go away.

The interplay between the two forms decides real costs on a clustered table. A secondary index’s entries carry the primary key as their pointer, so a fat primary key fattens every secondary index on the table; the small integer key is folklore for a structural reason. And the double descent a secondary index pays is why the covering decision is reviewed on hot queries first: an index that answers the query outright turns two log-depth descents into one, which on a frequently paged path is not a rounding error but a halving.

Composite indexes and the leftmost rule

A composite index sorts by more than one column, and the sort is lexicographic: first by the first column, then by the second within it, a phone book sorted by surname then first name. The consequence is the leftmost rule: the index serves any query that filters a leftmost prefix of its columns. An index on (tenant_id, created_at) serves a query on both columns, a query on tenant_id alone, and nothing at all for a query on created_at alone; the second column is only ordered within the first, like first names within a surname.

Column order is therefore a query-shaped decision, the same lesson database sharding taught about shard keys: the structure must match the access pattern, not the schema’s column list. The working rules: equality columns before range columns, because a range on an early column un-orders everything after it; the most frequently filtered columns first, subject to the range rule; and one composite index in the query’s shape beats several single-column indexes; the planner can combine single indexes, but the composite delivers the entries pre-joined, in order, and ready to satisfy a sort without doing one.

A worked example pins the rules together. The query is a tenant’s recent orders: WHERE tenant_id = ? AND created_at > ? ORDER BY created_at DESC LIMIT 20. An index on created_at alone is a walk through every tenant’s orders in date order, discarding strangers’ rows. An index on (created_at, tenant_id) sorts by date first, so the tenant’s rows are scattered through it; the leftmost rule fails the query. The right structure is (tenant_id, created_at): equality on the first column, range and sort on the second, twenty entries read off the leaf in order and nowhere else: the access pattern, visible directly in the index’s shape.

Index trade offs: what the write path pays

Every index is a write-time obligation. An INSERT places entries in every index the table carries; an UPDATE of an indexed column deletes the old entry and places the new; a DELETE removes all of them. The write amplification is proportional to the index count (a table with two indexes does roughly three times the structural work of a bare insert) and it lands on the path where latency is measured and budgets are thin. Indexes buy read speed with write speed, and the accounting question is always which side of the ledger the workload lives on.

The second cost is storage, and the third is trust. Each index is a sorted copy of a column subset: disk for the structure, and memory for the hot pages of it. And the planner’s cost estimates come from statistics the database gathers about column distributions; stale statistics produce confidently wrong plans, which is why index maintenance includes refreshing them. None of these costs are visible in the query the index speeds up; all of them are visible on the invoice the write path and the storage budget receive.

Indexes also age. Page splits leave structures half-empty, deletes leave gaps the entries never refill, and updates scatter entries across the leaves; the plan stays correct while the index grows slower per level. The maintenance answer is periodic reorganization: rebuild or compact the structure on the maintenance windows the operations team already has, and monitor the bloat rather than the existence. An index is a component with a service schedule, not a schema decoration.

How many indexes are too many has no fixed number; it has a method. Each index must name the query it serves, because each one taxes every write; a review that asks “which query does this serve?” catches decoration indexes before they ship. The trend lines are the arbiter: write latency creeping up as indexes accumulate is the tax arriving, and an index-usage audit that finds structures no plan has touched in months is the tax collected for nothing. The healthy count is the smallest set that serves the workload’s queries, the same minimalism every lever in this cluster eventually teaches.

So, when not to index. Columns with few distinct values: a boolean flag’s index narrows a search to half a scan, and the planner will often ignore it. Write-heavy tables whose read savings cannot pay the maintenance. Tiny tables, whose scans were never the problem. And the index that appears in no query plan at all, which is a write tax collected for nothing. The audit is the discipline: databases will list which indexes were used and which never scanned, and an unused index is the rare infrastructure decision that is safely reversible: drop it, watch the write path, keep the savings.

The caching series set one composition rule for this article, and it closes the ladder: indexing and caching stack, in that order. The index makes the database read cheap enough to survive; the cache keeps the read from happening at all. A cache in front of an unindexed query serves the same expensive miss on every expiry (slower than the fix it hides) so the first two rungs of the ladder are not alternatives; they are prerequisites of each other, and caching in system design takes the second one.

FAQ

How do database indexes work?

By keeping a sorted copy of one or more columns, with each entry pointing at the row it summarizes. A filtered query descends the sorted structure instead of scanning the table, so its cost grows with the logarithm of the table rather than the table itself, and every write pays to keep the copy in order.

What is the difference between clustered and non-clustered indexes?

A clustered index stores the table in the index’s key order: one per table, usually the primary key. A non-clustered index is a separate sorted structure whose entries point back at the rows; on a clustered table the pointer is the primary key, so uncovered lookups descend twice. A covering index avoids the second descent by holding every column the query needs.

Does the order of columns in a composite index matter?

It decides what the index can serve. Entries sort by the first column, then the second within it, so only leftmost prefixes are usable: an index on (tenant_id, created_at) helps queries on tenant_id, but a lone filter on created_at cannot use it. Put equality columns before range columns, and match the order to the queries.

Do indexes slow down writes?

Yes, by design. Every insert, update of an indexed column, and delete maintains every applicable index, so the more indexes a table carries, the more structural work each write performs. The decision is a ledger: read savings on one side, write amplification and storage on the other.

When should you not add an index?

On low-selectivity columns (few distinct values), on write-heavy tables where the read savings cannot pay the maintenance, on tables small enough that scans are cheap, and on any index the query plans never touch. The database can show which indexes are unused; those are the first to drop.

Why is my index not being used?

Usually one of five reasons: the statistics are stale, so the planner’s estimates favor a scan; the column’s selectivity is too low to be worth a descent; the query wraps the column in a function the index does not cover; the types do not match the expression; or the table is small enough that scanning is genuinely cheaper. Reading the query’s plan, not re-adding the index, is the fix; the planner is usually right about what it saw.

Related articles

• Next read: SQL vs NoSQL; the data-model decision that follows the read levers: what the database should be shaped like before the levers are pulled.
• database sharding, what happens to indexes when the table splits: local vs global placement, and the fan-out that follows.
• sharding vs replication; the scaling ladder this article is the first rung of.
• caching in system design; the rung above: the cache that never has to hide a slow query again. Fix the query first; the cache composes on top.
• database replication, the cluster anchor: copies of the tables these indexes live in. An index on a lagging copy answers questions a moment behind the truth.
• search engines in system design, the inverted index: the same sorted-copy idea pointed at words. The generalization this article linked twice earns its own full treatment there.