Database Indexing at Scale
An index is an auxiliary data structure that lets a database find rows matching a condition without scanning the entire table. Without an index, a query like WHERE email = '[email protected]' on a hundred-million-row table forces a full table scan — reading every row to check if it matches, which is prohibitively slow at scale. Indexes trade extra storage and write overhead for dramatically faster reads on the columns they cover, and choosing which columns to index (and how) is one of the highest-leverage decisions in database performance tuning.
Cricket analogy: Without an index, finding every ball a specific bowler bowled in a decade of matches means scanning every single delivery ever recorded, like a scorer flipping through every scorebook page by hand; an index lets them jump straight to that bowler's entries, at the cost of maintaining an extra card catalog.
B-tree indexes: the default workhorse
Most relational databases default to B-tree (or B+tree) indexes, a balanced tree structure that keeps data sorted and allows lookups, range scans, and ordered traversal in logarithmic time — O(log n) instead of O(n). Because the tree stays balanced as data is inserted and deleted, lookup performance degrades gracefully even as a table grows into the billions of rows, which is why B-trees remain the default choice for primary keys, foreign keys, and any column frequently used in WHERE, ORDER BY, or JOIN clauses.
Cricket analogy: A B-tree index is like a well-organized scorecard binder sorted by player name, letting a statistician find any player's record in a handful of flips rather than paging through the whole binder — and it stays quick to search even as decades of matches are added.
Other index types
Hash indexes offer O(1) average lookup for exact-match equality queries but can't support range queries (WHERE price > 100) since they don't preserve order. Composite (multi-column) indexes speed up queries that filter on multiple columns together, but column order matters enormously — an index on (country, city) speeds up queries filtering by country alone or by both, but not by city alone. Specialized indexes exist for specific data shapes: GiST/GIN indexes for full-text search and JSON containment, and geospatial indexes (R-trees) for location-based queries.
Cricket analogy: A hash index is like an instant name-to-locker lookup for players — fast for finding one exact player but useless for 'all players batting between 20-40' range queries; a composite index like (team, player) speeds up team-then-player lookups but not player-alone, and geospatial indexes help find 'grounds within 50km' queries.
The write-amplification cost
Every index must be updated on every insert, update, or delete that touches an indexed column, so adding indexes is not free — it slows down writes and consumes additional storage, sometimes multiple times the size of the underlying table. At scale, teams must be deliberate: index the columns that dominate query patterns (foreign keys, frequently filtered columns), and avoid indexing columns that are rarely queried or that change extremely frequently, since the write overhead there rarely pays for itself.
Cricket analogy: Every added scorecard index must be re-sorted on every ball bowled, slowing down live scoring, so scorers index only the columns actually queried often (bowler, batsman) and skip indexing rarely-checked fields like weather notes that would just add overhead without payoff.
-- Composite index: column order determines which query patterns benefit
CREATE INDEX idx_orders_user_status ON orders (user_id, status);
-- Benefits from the index (uses leftmost prefix):
SELECT * FROM orders WHERE user_id = 42;
SELECT * FROM orders WHERE user_id = 42 AND status = 'shipped';
-- Does NOT benefit (status alone is not a prefix of the index):
SELECT * FROM orders WHERE status = 'shipped';
-- EXPLAIN shows whether the planner chose an index scan or a full table scan:
EXPLAIN SELECT * FROM orders WHERE user_id = 42;
-- Index Scan using idx_orders_user_status (cost=0.42..8.60 rows=3)At very large scale, some systems use covering indexes — indexes that include every column a query needs — so the database can answer the query entirely from the index without a second lookup ('bookmark lookup') into the base table, roughly halving I/O for that query.
Over-indexing is a real anti-pattern: teams sometimes add an index for every column 'just in case,' which bloats storage and silently degrades write throughput on a hot table without providing proportional read benefit, since only a fraction of those indexes are ever actually used by the query planner.
- Indexes let the database avoid full table scans, turning O(n) lookups into roughly O(log n) with a B-tree.
- B-trees are the default index type, supporting equality, range queries, and ordered traversal.
- Hash indexes are faster for pure equality lookups but cannot serve range queries.
- Composite index column order matters: it must match the leftmost prefix of the query's filter columns to be used.
- Every index adds write overhead and storage cost, so indexes should be added deliberately based on actual query patterns.
- Covering indexes can satisfy a query entirely from the index, avoiding a second lookup into the base table.
Practice what you learned
1. Why do most relational databases default to B-tree indexes rather than hash indexes?
2. Given a composite index on (country, city), which query benefits from the index?
3. What is the main cost of adding an index to a frequently written table?
4. What is a covering index?
5. What is the practical limitation of a hash index?
Was this page helpful?
You May Also Like
SQL vs NoSQL Tradeoffs
Compares relational and non-relational databases across schema flexibility, consistency, scalability, and query capability to guide selection for a given workload.
Database Sharding
Explains how sharding partitions a dataset horizontally across multiple database nodes to scale beyond what a single machine can hold, and the tradeoffs of common sharding strategies.
Database Replication
Explains how copying data across multiple database nodes improves read throughput and fault tolerance, and the consistency tradeoffs of leader-follower and multi-leader setups.
Scalability Fundamentals
Core concepts behind building systems that handle growing load gracefully, including scaling dimensions, bottleneck identification, and the diminishing returns of naive scaling.
Related Reading
Related Study Notes in Software Engineering
Browse all study notesMicroservices Study Notes
Software Architecture · 30 topics
Software EngineeringTesting & TDD Study Notes
Software Testing · 30 topics
Software EngineeringDesign Patterns Study Notes
Software Design · 30 topics
Software EngineeringSoftware Engineering Study Notes
Python · 75 topics
Software EngineeringGit & Version Control Study Notes
Bash · 40 topics