Index
A data structure that speeds up reads on a column (or columns) at the cost of write overhead and storage. The single most important performance lever in a database. B-tree for range/equality, hash for equality, LSM for write-heavy.
- Columns in WHERE/JOIN/ORDER BY clauses.
- Covering indexes for hot queries.
- Low-selectivity columns (most rows match).
- Write-heavy tables where the index isn't used.
Definition
An index is an auxiliary structure mapping key(s) to row locations. B-trees keep sorted data for range and equality; hash indexes for equality only; LSM-trees (write-optimized) for high write throughput; bitmap for low-cardinality.
Why it exists
Scanning a whole table to find matching rows is O(N). An index makes lookups O(log N) or O(1), turning slow queries fast. The tradeoff is write amplification and storage.
How it works
On write, the DB updates the index structure(s). On query, the planner uses index stats to decide if an index helps. Composite indexes help multi-column predicates in order; covering indexes include all needed columns to avoid table lookups.
Scaling limits
Every index slows writes and adds storage. Too many indexes hurt write throughput and maintenance. Index-only scans need covering indexes. Index choice depends on the query workload, which changes.
Cost shape
Storage + write amplification per index. Blow-ups: many indexes on a write-heavy table, and large indexes bloating memory/disk.
Alternatives
- Materialized view — Precompute query results instead of indexing, more storage.
- Denormalization — Avoid the join needing the index by duplicating data.
Failure modes
- Unused indexes slowing writes.
- Missing indexes causing table scans.
- Index bloat from churn.