Indexing: Interview Gold or Just Jargon?

You're in a tech interview. The interviewer drops a systems design prompt: build a Twitter-like feed, an e-commerce catalog, or a ride-sharing service. You've sketched out your microservices, picked a database—PostgreSQL, MySQL, maybe Cassandra—and then it hits you. Performance. Suddenly, the question of database indexing isn't some academic detail; it's the difference between a system that scales to millions of users and one that chokes on its first thousand. Knowing when and how to wield indexing properly in these scenarios is pure interview gold.

The Mental Model: Why Indexes Exist

Forget the fancy terms for a second. Think about a library. You want a specific book. Do you walk shelf by shelf, scanning every title? No, you go to the card catalog—or, these days, the computer terminal. That's your index. It's an auxiliary data structure that makes searching for data faster. Without it, your database would perform a full table scan for every query that doesn't hit the primary key, which is inherently indexed. Imagine fetching all orders for a specific customer from a table with billions of rows. You’re not going to scan them all. You're just not.

The core trade-off is simple: read speed versus write cost. Indexes speed up reads significantly, often by orders of magnitude, but they slow down writes (inserts, updates, deletes). Every time you modify a row in the main table, the corresponding indexes also need updating. This isn't free. This is a critical point to hit in an interview. Don't just say "indexes make reads faster." Elaborate on the overhead.

B-Trees: Your Workhorse

When someone says "database index" in an interview, they're almost certainly talking about a B-tree (or B+tree, which is a variation optimized for disk I/O). These are the default for good reason. They keep data sorted and balanced, providing logarithmic time complexity for searches, insertions, and deletions. That means O(log N) for looking up a single record, O(log N + K) for a range of K records. This is a fundamental concept. If you can't explain why a B-tree is good for range queries—because leaf nodes form a linked list, allowing efficient traversal once the start of the range is found—you're missing a trick.

Consider a users table with id, name, email, created_at. SELECT * FROM users WHERE email = 'alice@example.com'; Without an index on email, this is a full table scan. With one, it's a quick B-tree traversal.

SELECT * FROM users WHERE created_at BETWEEN '2023-01-01' AND '2023-01-31' ORDER BY created_at DESC; An index on created_at makes both the range scan and the sorting incredibly efficient. You’re not just speeding up the WHERE clause; you're often speeding up the ORDER BY clause too. This is a common optimization overlooked by junior engineers.

When to Suggest an Index (and When Not To)

This is where the rubber meets the road. In an interview, don't just blindly suggest indexes for every column. You need to demonstrate judgment.

Suggest an index when:

1. High Read-to-Write Ratio: Your table is read far more often than it's written to. Think user profiles, product catalogs, historical transaction data. If it's a log table where you're constantly inserting millions of records per minute and rarely querying specific ones, you might choose not to index every column, or use specialized append-only storage.
2. Frequent Filtering (WHERE Clauses): Any column you frequently use in WHERE clauses, especially equality checks (=) or range queries (>, < BETWEEN), is a prime candidate. Example: WHERE user_id = 123.
3. Frequent Sorting (ORDER BY): If you often sort results by a specific column, an index on that column can eliminate the need for an expensive in-memory sort. ORDER BY created_at DESC.
4. Joins: Columns used in JOIN conditions are excellent candidates. The database engine needs to efficiently find matching rows in the joined table. JOIN orders ON users.id = orders.user_id. An index on orders.user_id is crucial here.
5. Uniqueness Constraints: A unique index enforces uniqueness on a column or set of columns (like an email or username) and simultaneously provides fast lookups. You get two birds with one stone.
6. Cardinality: The column has high cardinality—meaning many unique values. Indexing a gender column (typically 'M', 'F', 'Other') is usually pointless because a query for 'M' will still return a large percentage of the table, making a full table scan competitive or even faster due to index overhead. Good candidates have many distinct values, like email or user_id.

Avoid or be cautious with indexes when:

1. Low Read-to-Write Ratio: Tables with very frequent inserts, updates, or deletes. Every write operation means updating the index, which adds overhead. If you're ingesting millions of metrics per second into a table that's mostly consumed by aggregates, an index on every column is a bad idea.
2. Low Cardinality: As mentioned with gender, indexing columns with few unique values doesn't typically provide much benefit. The optimizer might even ignore the index.
3. Very Wide Rows / Few Queries: If your table has hundreds of columns and you rarely query most of them except for a full dump, don't index everything. Be selective.
4. Small Tables: For tables with only a few hundred or a few thousand rows, the overhead of maintaining an index often outweighs the benefits. A full table scan is incredibly fast on small datasets. Don't be that person who suggests an index on settings.key when there are 10 global settings.

Types of Indexes Beyond B-Trees (Briefly)

While B-trees are dominant, mentioning other types shows breadth. Don't go deep unless prompted, but know their niches:

• Hash Indexes: Excellent for equality lookups (=) but terrible for range queries or sorting because they don't store data in order. Less common in relational databases as a primary general-purpose index because B-trees handle equality well and ranges. MySQL's MEMORY engine uses them. PostgreSQL has them for specific use cases.
• Full-Text Indexes: For searching text documents efficiently. Think LIKE '%keyword%' but much, much faster. Elasticsearch builds on these concepts.
• Geospatial Indexes (R-trees): For spatial data, like "find all restaurants within 5 miles of this longitude/latitude." PostGIS uses these.
• Bitmap Indexes: Often found in data warehouses (OLAP systems) for columns with low cardinality. They can be very space-efficient and fast for OR and AND operations but are awful for OLTP systems due to write contention.

In a general systems design interview, stick to B-trees unless the problem explicitly involves text search or geospatial queries. If it's a data warehousing scenario, then bring up bitmap indexes.

Multi-Column (Composite) Indexes: The Power Play

This is an area where many candidates falter. A composite index is an index on multiple columns, in a specific order. The order matters. A lot.

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

This index can be used for queries like: WHERE user_id = 123 AND status = 'pending' WHERE user_id = 123 AND status = 'pending' AND created_at > '2023-01-01' WHERE user_id = 123 ORDER BY status (if status comes immediately after user_id) WHERE user_id = 123 ORDER BY created_at (if created_at comes after user_id, even if status isn't used in the WHERE clause, as long as status is in the index and the order matches or is a prefix)

It cannot efficiently be used for: WHERE status = 'pending' (because user_id is the leading column) WHERE created_at > '2023-01-01'

The database uses the index from left to right. It's like a phone book sorted by last name, then first name. You can find "Smith, John" easily. You can find all "Smiths." But you can't easily find all "Johns" without knowing their last name. This "leftmost prefix" rule is crucial. Understand it. Live it. Explain it.

When to use composite indexes:

• Queries with multiple WHERE clauses on specific columns.
• Queries that filter and then sort by other columns. An index on (user_id, created_at) can satisfy WHERE user_id = 123 ORDER BY created_at. The database finds rows for user_id = 123 and then they're already sorted by created_at. No extra sort step. This is a huge win.
• Covering Indexes: A special type of composite index where all columns needed by the query are present within the index itself. This means the database doesn't even need to touch the main table (heap) to fetch the data. This is incredibly fast because it avoids a "table lookup" or "bookmark lookup." CREATE INDEX idx_user_email_name ON users (id, email, name); SELECT email, name FROM users WHERE id = 50; This query can be entirely satisfied by scanning the index idx_user_email_name for id = 50 and then reading email and name directly from the index entries. This is a common optimization in high-performance systems.

The "Indexing Strategy" Question

Interviewers might ask you to design an indexing strategy for a given system. Here's how to approach it:

1. Identify Critical Query Patterns: Ask about the most frequent and performance-sensitive queries. Is it user login (by email)? Fetching a user's recent posts (by user ID, ordered by timestamp)? Searching products by name?
2. Analyze WHERE, ORDER BY, JOIN Clauses: For each critical query, look at the columns used in these clauses. These are your primary candidates.
3. Consider Cardinality: High cardinality columns are generally better index candidates.
4. Composite Indexes: Look for combinations of columns frequently queried together. Think about the leftmost prefix rule.
5. Covering Indexes (for hot queries): If you have a few queries that are extremely performance-critical and only need a few columns, consider a covering index.
6. Trade-offs: Discuss the write overhead. If it's a heavily written-to table, you might opt for fewer indexes or more specialized ones. Mention storage costs—indexes aren't free in terms of disk space.
7. EXPLAIN Plan: Bring up the EXPLAIN (or EXPLAIN ANALYZE) command. This is how you actually verify that your indexes are being used and if they're effective. You'd use this to see if the optimizer is choosing your index or doing a full table scan, and if it's performing an expensive sort. This shows you're not just guessing.

Real-World Scenarios and Gotchas

Let's say you're building a social media feed.

Scenario 1: Fetching a user's posts. SELECT * FROM posts WHERE user_id = 123 ORDER BY created_at DESC LIMIT 20; An index on (user_id, created_at DESC) would be perfect. It finds user_id = 123 quickly and then walks the created_at in descending order, only needing to read 20 rows.

Scenario 2: Searching posts by keywords. SELECT * FROM posts WHERE content LIKE '%foo%'; A standard B-tree index on content won't help here because the % wildcard is at the beginning. The index needs to know the starting characters to traverse efficiently. You'd need a full-text index for this, or potentially a trigram index in PostgreSQL. This is a great example of knowing when generic B-trees aren't enough.

Scenario 3: Pagination with OFFSET is slow. SELECT * FROM posts ORDER BY created_at DESC OFFSET 100000 LIMIT 20; While ORDER BY created_at DESC benefits from an index, OFFSET can be brutal on large datasets. The database still has to retrieve and then discard 100,000 rows before returning the 20 you want. A better approach for deep pagination is "keyset pagination" (or "cursor pagination"): SELECT * FROM posts WHERE created_at < 'last_post_created_at' AND id < 'last_post_id' ORDER BY created_at DESC, id DESC LIMIT 20; This uses the index efficiently because it directly seeks to the next page's starting point. You'd typically pass created_at and id of the last item from the previous page. This is a common interview trick question for "how do you scale pagination?"

A Word on Database-Specific Features

While general principles apply, specific databases offer nuanced features.

• PostgreSQL: Supports partial indexes (CREATE INDEX ON posts (user_id) WHERE status = 'active'). This is great for filtering on a common predicate and reduces index size. Also supports expression indexes (CREATE INDEX ON users (LOWER(email))) for case-insensitive searches without changing the column data.
• MySQL: InnoDB uses a clustered index where the primary key physically orders the data. All secondary indexes store the primary key as part of their entry, which is how they locate the full row. This means querying by primary key is super fast, but secondary indexes sometimes require an extra hop if they're not covering.

Don't dive deep into these unless the interviewer explicitly asks or the problem warrants it. It's better to show a solid understanding of the fundamentals first. You can always say, "If this were PostgreSQL, I might consider a partial index for active posts..."

The Honest Caveat: It Depends

Look, no amount of theoretical knowledge replaces actually running EXPLAIN and benchmarking. You can draw all the diagrams and suggest all the indexes you want, but the database optimizer often has surprises in store. Disk I/O patterns, cache hit rates, CPU contention, and the exact distribution of your data—these all play a huge role. An index that looks good on paper might perform poorly in production due to data skew or other factors. Always approach indexing as an iterative process: hypothesize, implement, measure, optimize. In an interview, acknowledging this practical reality and the need for data-driven decisions will make you stand out. You're not just reciting facts; you're thinking like an engineer.

Ready to Ace Your Next Interview?

Practice with AI-powered mock interviews tailored to your target role and company. Start Practicing for Free | Explore Interview Prep