How Do You Choose an Indexing Strategy at Scale?
Learn how to choose B-tree, hash, composite, and covering indexes at scale by balancing read speed against write cost.
Expected Interview Answer
Choosing an indexing strategy at scale means matching the index structure to the query pattern — B-tree indexes for range scans and ordered access, hash indexes for pure equality lookups, composite and covering indexes to serve common multi-column queries without a table lookup, and specialized structures like inverted, geospatial, or LSM-based secondary indexes when the workload demands it — while always weighing write amplification and storage cost against read speed.
Every index trades write cost for read speed: each additional index must be updated on every insert/update/delete, so over-indexing a write-heavy table can dominate latency and disk I/O. B-tree indexes remain the default because they support equality, range, and ordered scans efficiently with logarithmic lookup; hash indexes beat them only for pure equality lookups and cannot support ranges. Composite indexes should be ordered by selectivity and query pattern (most selective or most commonly filtered column first, matching the leftmost-prefix rule), and covering indexes that include all columns a query needs avoid an extra lookup into the primary table entirely. At large scale, indexes are also sharded or partitioned alongside data, secondary indexes may live on separate nodes requiring scatter-gather queries, and specialized structures — inverted indexes for full-text search, R-trees or geohashes for spatial queries, bitmap indexes for low-cardinality columns — replace generic B-trees when the access pattern demands it. The right strategy always starts from the actual query patterns (via query plans and slow-query logs), not from indexing every column defensively.
- Matches index structure to real query patterns instead of indexing defensively
- Covering and composite indexes cut read latency by avoiding extra lookups
- Balances read speed against write amplification and storage overhead
- Specialized indexes (inverted, spatial, bitmap) unlock queries a generic B-tree cannot serve efficiently
AI Mentor Explanation
Indexing strategy is like deciding how a cricket almanac organizes decades of match data: a chronological index (like a B-tree) lets you quickly find every match in a date range, while a player-name index (like a hash index) instantly finds one player’s exact record but is useless for “matches between 2010 and 2015.” Adding a combined player-and-season index speeds up common lookups but means every new match recorded must update multiple indexes, slowing down data entry. Choosing the right combination of indexes depends entirely on which questions readers actually ask most often, not indexing every possible column defensively.
Step-by-Step Explanation
Step 1
Profile real query patterns
Use slow-query logs and query plans to find which columns are actually filtered, sorted, or joined on frequently.
Step 2
Match structure to access pattern
Pick B-tree for ranges/ordering, hash for pure equality, and specialized structures (inverted, spatial, bitmap) when needed.
Step 3
Design composite and covering indexes
Order composite index columns by selectivity/leftmost-prefix rule; add covering columns to avoid extra table lookups.
Step 4
Weigh write amplification
Measure the write-latency cost of each index and drop ones that are rarely used by real queries.
What Interviewer Expects
- Explains the read/write trade-off of adding an index, not just the read benefit
- Distinguishes B-tree (range-capable) from hash (equality-only) indexes correctly
- Discusses composite index column ordering and the leftmost-prefix rule
- Mentions specialized indexes (inverted, spatial, bitmap) for non-generic access patterns
Common Mistakes
- Recommending indexing every column “to be safe” without considering write cost
- Confusing hash indexes with B-tree indexes and claiming hash indexes support ranges
- Ignoring composite index column order and the leftmost-prefix matching rule
- Designing indexes from intuition instead of actual query plans or slow-query logs
Best Answer (HR Friendly)
“Choosing indexes at scale is about matching the index to how the data is actually queried — range scans need a different structure than exact lookups — while remembering that every index you add makes writes a little slower because it has to be kept up to date. The best approach is to look at real, frequent queries first and index for those, rather than indexing every column just in case.”
Code Example
queries:
- pattern: "WHERE user_id = ? ORDER BY created_at DESC"
index: composite
columns: [user_id, created_at]
type: btree
note: "leftmost prefix matches equality filter, then range/sort"
- pattern: "WHERE session_token = ?"
index: single-column
columns: [session_token]
type: hash
note: "pure equality lookup, no ranges needed"
- pattern: "WHERE status = ? AND region = ? RETURN id, name"
index: covering
columns: [status, region, id, name]
type: btree
note: "covering index avoids extra lookup into primary table"
- pattern: "full text search over product description"
index: inverted
type: inverted-index
note: "generic B-tree cannot efficiently serve tokenized text search"
writeAmplificationBudget:
maxIndexesPerHighWriteTable: 3
reviewCadence: quarterlyFollow-up Questions
- What is the leftmost-prefix rule for composite indexes, and why does column order matter?
- When would a covering index eliminate the need for a lookup into the primary table?
- How do secondary indexes work in a sharded database, and what is a scatter-gather query?
- When is a bitmap index preferable to a B-tree for low-cardinality columns?
MCQ Practice
1. What is the main trade-off of adding an index to a table?
Every index speeds up matching reads but must be maintained on every write, adding write latency and storage overhead.
2. Which index type generally cannot efficiently support range queries?
Hash indexes are optimized for exact-match equality lookups and do not support ordered range scans.
3. In a composite index on (a, b, c), which query can use the index via the leftmost-prefix rule?
Composite indexes are usable left-to-right; a query filtering on a (and optionally a+b) can use the index, but skipping the leading column cannot.
Flash Cards
Main trade-off of an index? — Faster matching reads versus slower writes since the index must be kept up to date.
B-tree vs hash index? — B-tree supports ranges and ordering; hash only supports exact equality lookups.
Leftmost-prefix rule? — A composite index is usable only when the query filters on a left-to-right prefix of its columns.
What is a covering index? — An index that includes all columns a query needs, avoiding an extra lookup into the primary table.