Architecture/Fundamentals/database-indexing-strategies

Database Indexing Strategies

Concept

An index is a separate, ordered data structure that lets a database find rows matching a query without scanning the entire table. Without one, a lookup for WHERE user_id = 42 on a 100-million-row table means a full table scan — reading every row to check the condition. Most relational databases build indexes as B-trees by default: a balanced tree structure that keeps lookups, range scans, and ordered traversal at O(log n) instead of O(n), which is why an indexed lookup on a huge table returns in milliseconds while an unindexed one degrades linearly with table size.

The index isn't free, though — it's a second data structure the database has to keep in sync with the table on every write. Every INSERT, UPDATE, or DELETE that touches an indexed column has to also update every index covering that column, which is why tables with many indexes see slower write throughput than the same table with fewer. A composite index (covering multiple columns) only helps queries that filter on a left-prefix of its column order — an index on (country, city) speeds up queries filtering on country alone or country AND city together, but does nothing for a query filtering on city alone, because the tree is sorted by country first. A covering index goes further, including every column a query needs directly in the index itself, letting the database answer the query from the index alone without a second lookup into the actual table row (avoiding what's called a "bookmark lookup" or "table access by rowid").

Beyond B-trees, specialized index types exist for specialized query shapes: hash indexes for pure equality lookups (no range queries), GiST/GIN indexes (Postgres) for full-text search and array/JSONB containment queries, and geospatial indexes for location queries — picking the wrong index type for the query shape means paying the write-cost of an index that never actually gets used by the query planner.

Tradeoffs

Choice	Read benefit	Write cost	Storage cost
No index	None	None	None
Single-column index	Fast lookups/range scans on that column	One extra write per row change on that column	Moderate
Composite index (multi-column)	Fast lookups on left-prefix combinations	Higher — must stay sorted across multiple columns	Higher
Covering index	Query answered from index alone, no table access	Highest per-index write cost (more columns to maintain)	Highest
Over-indexing (index on every column)	Marginal or no gain on unused indexes	Compounds across every index on every write	Can exceed the table's own size

The core tension is read speed against write speed and storage: every index accelerates the reads it's actually used for, but adds real cost to every write, whether or not that write's query pattern benefits. A table optimized purely for read-heavy analytics can carry many indexes profitably; a write-heavy table (event ingestion, high-frequency trading order books) pays that cost on every single write and needs indexes chosen much more sparingly, matched precisely to the queries that actually run.

When to use / when not to

Index columns used in WHERE, JOIN, and ORDER BY clauses on tables large enough that a full scan is measurably slow — the exact threshold depends on table size and query frequency, not a fixed row count.
Use composite indexes when queries consistently filter on the same combination of columns together, ordering the columns by selectivity/usage pattern (most-restrictive or most-frequently-filtered-alone column first, as the left-prefix rule dictates).
Use covering indexes on hot, latency-sensitive queries where the extra write cost is worth eliminating the second table lookup — not as a default for every index.
Don't index low-cardinality columns (a boolean flag, a status column with 3 values) in isolation — the index barely narrows the search compared to a full scan, so the write cost isn't earning its keep.
Don't add an index speculatively "in case a query needs it later" — every unused index is pure write-cost and storage overhead with zero benefit; add indexes in response to observed slow queries, not in anticipation of hypothetical ones.

Common pitfall

Adding indexes reactively to fix every slow query without ever removing old ones, until the table carries a dozen overlapping or unused indexes — each one silently taxing every write. Query patterns change over time (a feature gets deprecated, a query gets rewritten to use a different filter), but the index added for the old pattern usually doesn't get cleaned up, because removing an index feels riskier than adding one. The fix is treating the index set as something to audit periodically against actual query patterns (most databases expose index-usage statistics for exactly this), not a monotonically growing pile.

Principal Engineer Lens

Indexing decisions are one of the clearest places where "it depends on the read/write ratio" is a real, defensible answer rather than a dodge — being able to name the actual tradeoff (this index speeds up this specific query pattern at this specific write cost, measured against this table's actual read/write mix) is what separates a reviewed indexing strategy from cargo-culted "just add an index." In trading and payments systems specifically, write-heavy tables (order books, transaction ledgers) are exactly where over-indexing quietly becomes a latency problem under load, making index discipline a direct performance-and-correctness lever, not just a DBA housekeeping task.