Database Indexing in System Design Interviews: When to Use It and What to Say
When you design a system that stores user data, you often need to answer questions like “Give me the last 10 orders for a user” or “Find all posts with a given tag.” Scanning every row each time would be wasteful. A database index is a separate data structure that maps the indexed column values to the locations of the rows that contain them, allowing the engine to jump directly to the matching rows.
The Problem Indexes Solve
Imagine a simple order service that stores every order in a relational table with columns order_id, user_id, created_at, and status. If the service must return the most recent orders for a particular user, a naïve query would scan the entire table, compare each row’s user_id, sort by created_at, and then pick the top 10. With a million orders per day (roughly 12 inserts per second), a full scan would be costly and would grow linearly with data size. The bottleneck is the search operation, not the write path.
How an Index Works – Step by Step
- Create the index – The DB builds a B-Tree (or another structure) on the indexed column(s). For a composite index on
(user_id, created_at DESC), each leaf node stores a pointer to the row and is ordered first byuser_idthen by timestamp. - Insert – When a new order arrives, the DB inserts a new entry into the index. This is an O(log N) operation, where N is the number of rows.
- Query – A query that filters on
user_idand sorts bycreated_atcan now walk the index directly to the first matching leaf for that user and then read sequentially forward to fetch the next 10 rows. - Delete/Update – Any change to the indexed columns triggers an update to the index, again costing O(log N).
Small Worked Example
Suppose the table has five rows:
| order_id | user_id | created_at | status |
|---|---|---|---|
| 1 | 42 | 2026-01-01 10:00:00 | paid |
| 2 | 7 | 2026-01-01 10:05:00 | paid |
| 3 | 42 | 2026-01-01 10:10:00 | shipped |
| 4 | 42 | 2026-01-01 10:15:00 | paid |
| 5 | 7 | 2026-01-01 10:20:00 | cancelled |
Create an index on (user_id, created_at DESC). The B-Tree leaf order becomes:
(user_id=7, created_at=2026-01-01 10:20:00) → row 5(user_id=7, created_at=2026-01-01 10:05:00) → row 2(user_id=42, created_at=2026-01-01 10:15:00) → row 4(user_id=42, created_at=2026-01-01 10:10:00) → row 3(user_id=42, created_at=2026-01-01 10:00:00) → row 1
A query SELECT * FROM orders WHERE user_id = 42 ORDER BY created_at DESC LIMIT 2 now walks directly to entry 3 and reads the next two entries, returning rows 4 and 3 without touching rows 1, 2, or 5.
Where Indexes Appear in Classic Design Questions
| Design Question | Typical Component | Where the Index Is Mentioned |
|---|---|---|
| Twitter Timeline | Timeline storage (e.g., MySQL or Cassandra) | Index on user_id + tweet_id for fetching a user’s recent tweets. |
| E-commerce Order Service | Order table (RDBMS) | Composite index on (user_id, created_at) to support "last N orders" queries. |
| URL Shortener | Mapping table (key → URL) | Unique index on the short code column: lookups take O(log N) with a B-Tree, and no two URLs can share a code. |
In each case, the index lives at the data-access layer and is part of the request path that the interviewee should articulate.
Trade-offs and the Follow-up Question
| Aspect | Benefit of Index | Cost / Trade-off |
|---|---|---|
| Read latency | Faster point lookups, range scans, and ordered retrievals. | None for reads that use the index. |
| Write latency | None directly. | Extra work on inserts/updates, because each affected index has to be updated as well. The cost grows with each additional index and depends on the workload, so measure it. |
| Storage | Enables efficient queries. | Index consumes additional disk (roughly the size of the indexed columns plus pointers). For large tables, this can be on the order of 20-30 % of the base table size. |
| Complexity | Simple to add, often just one line of DDL. | Too many indexes create maintenance overhead and can cause lock contention during schema changes. |
Interviewers often follow the index suggestion with a question like “What happens if we start receiving 10 × the write traffic?” or “How would you handle a query that needs to filter on two non-indexed columns?” The expected answer is to discuss alternative strategies such as:
- Denormalization – Store a pre-computed view (e.g., a materialized timeline) to avoid expensive joins.
- Secondary indexes in NoSQL stores (e.g., DynamoDB GSI) with their own consistency trade-offs.
- Cache layer – Keep hot query results in Redis or Memcached to bypass the DB entirely.
30-Second Pitch
"An index is a sorted data structure that lets the DB jump directly to rows matching a predicate, turning a full table scan into a logarithmic lookup. In a typical order service, a composite index on user_id and created_at lets us fetch the latest N orders for a user in O(log N + K) time, where K is the result size. The trade-off is extra write latency and storage, so we add indexes only for high-frequency read paths and consider denormalization or caching for write-heavy scenarios."
Common Mistakes Candidates Make
- Assuming every column needs an index – Leads to unnecessary storage and slows writes.
- Mentioning the index without tying it to the request path – Interviewers want to hear where the index sits in the diagram and how it changes latency.
- Confusing primary key with secondary indexes – Primary keys guarantee uniqueness; secondary indexes are for other query patterns.
- Skipping the trade-off discussion – Forgetting to mention write overhead or storage cost makes the answer feel superficial.
- Over-optimizing – Proposing exotic index types (e.g., full-text, spatial) when the query is a simple equality/range filter.
How to Practice This
- Study the worked design for a relational database in the System Design AI library. Click the components on the board and read their notes, looking for where indexes come in.
- Draw your own diagram on the practice canvas: start with the client request, show the API layer, the DB, and place an index component on the path. Write a one-sentence description for each component.
- Record a 30-second pitch and play it back. Make sure you mention the definition, the concrete use case, and at least one trade-off.
Questions people ask
When should I add an index in a system design?
Add an index when a query filters or sorts on a column that would otherwise cause a full table scan, and the read frequency outweighs the write overhead.
Do primary keys count as indexes?
Yes. A primary key is automatically indexed and guarantees uniqueness. It is often the first index you consider.
How does a composite index differ from multiple single-column indexes?
A composite index orders rows by the first column, then the second, enabling efficient range scans that use both columns together. Separate single-column indexes cannot satisfy a query that needs both columns in order.
What alternative can I suggest if writes become a bottleneck?
You can propose denormalizing the data, using a cache for hot read patterns, or moving the write-heavy workload to a write-optimized store while keeping a read-optimized replica for queries.