Database Indexing Strategies: A Deep Dive

An index is a data structure that speeds up data retrieval at the cost of extra storage and slower writes. Without indexes, every query is a full table scan — O(n) for n rows. With the right index, the same query runs in O(log n) or even O(1). In system design interviews, knowing which index to use and when is as important as knowing the high-level architecture.

B-Tree Indexes

The B-tree (and its variant B+tree) is the default index type in PostgreSQL, MySQL, and most relational databases. It stores keys in a balanced tree where each node has many children, keeping the tree shallow.

[30 | 60]              ← root
/    |    

[10|20] [40|50] [70|80]       ← internal nodes
/ | \   / | \   / | 

[leaves with actual row pointers]

How lookups work: start at the root, follow the correct child pointer at each level. With a branching factor of ~500 (typical for 8KB pages), a tree of depth 3 indexes 125 million rows. That’s 3 disk reads for any lookup.

What B-trees support:

• Exact match: WHERE id = 42
• Range queries: WHERE price BETWEEN 10 AND 50
• Sorting: ORDER BY created_at DESC
• Prefix matching: WHERE name LIKE 'John%'

What B-trees don’t help:

• Suffix matching: WHERE name LIKE '%son' (can’t traverse the tree backwards)
• Functions on columns: WHERE YEAR(created_at) = 2026 (unless you create a functional index)

Hash Indexes

A hash index maps keys through a hash function directly to row locations — O(1) lookups.

PostgreSQL supports hash indexes. MySQL/InnoDB uses hash indexes for its adaptive hash index internally but doesn’t expose them to users. Use hash indexes when you only ever query by exact key and never need ordering.

Composite Indexes

A composite index covers multiple columns in a specified order:

CREATE INDEX idx_user_status_date ON orders(user_id, status, created_at);

The leftmost prefix rule: this index can serve queries that filter on:

• user_id alone
• user_id AND status
• user_id AND status AND created_at

It cannot efficiently serve:

• status alone (skips the first column)
• created_at alone
• status AND created_at (skips user_id)

Column order matters. Put the most selective (highest cardinality) column first, unless your most common query filters on a different column.

Covering Indexes

A covering index includes all columns that a query needs. The database reads only the index, never touching the table — this is called an “index-only scan.”

-- Query
SELECT user_id, status FROM orders WHERE user_id = 42;

-- Covering index
CREATE INDEX idx_covering ON orders(user_id, status);

Since both user_id and status are in the index, the database doesn’t need to look up the actual row. This eliminates random I/O to the table heap.

PostgreSQL supports INCLUDE for non-key columns:

CREATE INDEX idx_cover ON orders(user_id) INCLUDE (status, total);

Partial Indexes

A partial index only indexes rows that match a condition:

CREATE INDEX idx_active_users ON users(email) WHERE active = true;

If only 5% of users are active, this index is 20x smaller and faster to maintain. Use partial indexes when your queries always filter on a known condition.

Index Tradeoffs

Every index has a cost:

Write amplification: each INSERT/UPDATE/DELETE must update every index on the table. A table with 5 indexes makes writes 5x more expensive in terms of I/O.

Storage: indexes consume disk space. A B-tree index on a 10 million row table with an 8-byte key is roughly 150-200 MB.

Maintenance: indexes fragment over time and may need rebuilding. REINDEX or ALTER INDEX ... REBUILD reclaims space.

Rule of thumb: index columns that appear in WHERE, JOIN, and ORDER BY clauses of frequent queries. Don’t index columns with low selectivity (e.g., a boolean is_active column with 50/50 distribution — unless combined with other columns).

Reading EXPLAIN Plans

EXPLAIN ANALYZE SELECT * FROM orders WHERE user_id = 42 AND status = 'shipped';

Key things to look for:

• Index Scan or Index Only Scan — good, the index is being used.
• Seq Scan — bad for selective queries, means no useful index exists.
• Bitmap Index Scan — the database combines multiple indexes.
• Rows — estimated vs actual row count. Large discrepancies mean stale statistics (ANALYZE the table).

Index Strategies for System Design

Common Anti-Patterns

1. Indexing every column: kills write performance. Only index what queries actually use.
2. Missing composite indexes: three separate single-column indexes are far worse than one composite index for a multi-column WHERE clause.
3. Wrong column order: (status, user_id) vs (user_id, status) — the wrong order makes the index useless for your most common query.
4. Indexing low-cardinality columns alone: an index on gender with two values scans half the table regardless.
5. Ignoring EXPLAIN: assuming an index is used without verifying.

Interview Tips

• When designing any data-heavy system, mention indexes for hot query paths proactively.
• Explain the write amplification tradeoff — more indexes means faster reads but slower writes. This matters for write-heavy systems like logging or analytics.
• Know the difference between a B-tree (range queries, sorting) and a hash index (exact lookup only).
• Mention covering indexes when discussing query optimization — it’s a detail that impresses interviewers.
• For time-series data, suggest BRIN indexes or time-based partitioning rather than a massive B-tree.
• Always tie index decisions back to the query pattern: “We index (user_id, created_at) because the feed query filters by user and sorts by time.”