An interviewer drops a query on the table: SELECT * FROM orders WHERE customer_id = 4211 AND status = 'shipped' runs in 900ms against a 50-million-row table, and asks you to make it fast. The weak answer is “add an index on status.” The answer that gets you to the next round explains why an index on (customer_id, status) helps, why the reverse order might not, and when the planner will ignore whatever you build no matter how you build it.
Indexing rounds look like they reward memorizing data structures. They mostly reward knowing how the query planner thinks, because that is what predicts whether the index you propose does anything at all.
What a B-tree actually buys you
Nearly every default index you create in Postgres, MySQL/InnoDB, SQL Server, or Oracle is a B-tree, technically a B+tree, where all the data lives in the leaf nodes and the leaves form a linked list. The structure keeps keys in sorted order and stays balanced as rows come and go, so a lookup on a billion-row table touches four or five pages instead of scanning the whole thing. That sorted order is why one structure covers so many query shapes: exact match (WHERE id = 5), ranges (WHERE created_at > '2026-01-01'), sorting (ORDER BY created_at), and prefix matches on text (WHERE name LIKE 'Sam%'). A hash index is faster for pure equality, but it does none of the range or ordering work, which is why almost nobody reaches for one.
The leftmost prefix rule, where most people fumble
Build an index on (customer_id, status, created_at) and picture a phone book sorted by last name, then first name, then middle name. You can find everyone named Chen instantly. You can find every Chen, Wei quickly. But if all you know is the first name Wei, the book is useless, because the Weis are scattered under every last name. A composite B-tree behaves the same way: it can serve a query that constrains a contiguous prefix starting from the leading column, and not much else.
-- index: (customer_id, status, created_at)
WHERE customer_id = 4211 -- uses the index
WHERE customer_id = 4211 AND status = 'shipped' -- uses the index
WHERE status = 'shipped' -- historically cannot: no leading customer_id
This is the single most common thing candidates get wrong. They see three columns in the WHERE clause, build a three-column index in whatever order feels natural, and assume any subset of those columns benefits.
Equality before range
Column order inside the index is a real design decision, not a formality. The rule that carries most of the weight: put columns you test with = or IN ahead of columns you test with >, <, BETWEEN, or a trailing LIKE. Once a B-tree hits a range predicate, it seeks to the start of the range and walks the leaves from there, but it can’t use any column that comes after the range column to narrow that seek.
WHERE status = 'shipped' AND created_at >= '2026-06-01'
-- good: (status, created_at) -> seek straight to shipped, walk the date range
-- bad: (created_at, status) -> status can't ride the index; it filters after the fact
Same three columns, opposite performance, and the reason is entirely about which predicate is an equality and which is a range.
Picking the right structure
B-tree is the default for good reasons, but interviewers like to hear that you know the rest of the family. Each of these answers a different question well and a different question badly.
| Index type | Structure | Best for | Weak at |
|---|---|---|---|
| B-tree (B+tree) | balanced sorted tree, linked leaves | equality, ranges, ORDER BY, prefix LIKE | very high write rates |
| Hash | hash table | exact equality only | ranges and ordering |
| GIN / inverted | posting lists per token | full-text, JSONB, array membership | plain scalar lookups |
| BRIN | per-block min/max summaries | huge append-only tables with natural ordering | randomly ordered data |
| LSM tree | layered immutable sorted files | write-heavy ingestion (logs, telemetry) | random-read latency, wide range scans |
Covering indexes and skipping the table entirely
There’s a second lookup hiding in most index scans. The index finds the matching rows and hands back pointers, then the engine visits the heap (the actual table) to fetch the columns you selected. A covering index carries those columns too, so the query gets answered from the index alone. Postgres calls the result an index-only scan and lets you attach payload columns with INCLUDE:
CREATE INDEX idx_orders_lookup
ON orders (customer_id, status) INCLUDE (total_amount, created_at);
-- answered without touching the table at all:
SELECT total_amount, created_at
FROM orders
WHERE customer_id = 4211 AND status = 'shipped';
The INCLUDE columns live only in the leaf pages, not in the part of the tree used for seeking, so they carry the payload without bloating the search path. One caveat that marks a senior answer: in Postgres an index-only scan still consults the visibility map, and on a table with heavy recent updates it can fall back to heap fetches until autovacuum catches up. So the covering index pays off most on read-mostly hot paths, which is usually exactly where you want it.
Every index is a tax on writes
The reason you don’t index every column is that each index is a separate structure the database keeps in sync. Insert one row into a table with five indexes and you’ve done six writes, not one. Update the status column and every index containing status gets rewritten. On a write-heavy table this shows up as insert latency and as write amplification, and it’s the tradeoff an interviewer wants you to name out loud instead of waving at “indexes make things faster.” The right framing is that you’re buying read speed with write speed and storage, and you should be able to say which side of that trade the workload sits on.
When writes dominate, B-trees give way to LSM trees
This is where the “and beyond” part of the question usually points. A B-tree updates in place, which means random writes scattered across the disk. Log-structured merge trees, the engines behind Cassandra, ScyllaDB, RocksDB, and LevelDB, take the opposite bet: buffer writes in an in-memory memtable, flush them to immutable sorted files sequentially, and merge those files in the background through compaction. Sequential writes are cheap, so LSM engines absorb far more write throughput, commonly several times what a comparable B-tree handles on the same hardware, which is why they anchor event logging, time-series stores, and telemetry pipelines.
The cost lands on reads. A given key might sit in the memtable or in any of several on-disk levels, so a single read may have to check multiple places. LSM engines soften this with bloom filters, a fast probabilistic check that says a file definitely does not hold your key, and by keeping every file internally sorted. But a range scan that spans many files still costs more than the equivalent walk down a B+tree’s linked leaves. Naming that read-versus-write asymmetry, and pinning a concrete workload to each side, is what a strong answer sounds like.
The Postgres 18 wrinkle interviewers started using
If your interviewer keeps current, expect a curveball on the leftmost rule. Postgres 18 shipped skip scan, which lets the planner use an index like (status, created_at) even when the query only constrains created_at, provided the leading column has few distinct values. The planner loops over each distinct status and does a bounded range seek inside it. It doesn’t repeal the leftmost rule so much as automate the workaround for low-cardinality leading columns. The thing to say when asked: skip scan helps when the leading column has a handful of values and does nothing useful when it has millions, so you still design composite indexes with the common predicate in the leading position and treat skip scan as a safety net, not a license to stop thinking about column order.
When no index will save you
The most senior-sounding answer in an indexing round is often “I wouldn’t add one here.” A B-tree on a boolean or a two-value status column barely narrows anything, so the planner reads the table instead, and it’s right to. Wrap a column in a function and a plain index goes dead: WHERE lower(email) = '[email protected]' won’t touch an index on email; you need an index on the expression lower(email) itself. A leading wildcard like LIKE '%son' can’t ride a B-tree at all, because the sort order starts from the left of the string. And when a query returns most of the table, a sequential scan genuinely beats bouncing between the index and the heap, which is why planners flip to it once selectivity passes roughly the five-to-ten-percent mark. Knowing when the planner is right to ignore you is the part that’s hard to fake.
Keep sharpening your system design:
