Database Indexing for Interviews: B-Trees, Planner Traps, and the Write Tax

A database-indexing question is not asking whether indexes are good. It is asking whether you can connect one query shape to one access path, predict why the optimizer might reject that path, and price the extra work imposed on every write.

For a Backend Engineer, the most useful sequence is consistent: identify the rows the query needs, choose an index order that narrows to those rows, inspect the actual plan, then explain the read and write trade-off. This guide builds that sequence from B-tree mechanics through covering and partial indexes.

Match the index to the query shape

A B-tree stores keys in sorted leaf pages and uses internal pages to route a lookup toward the correct range. High fan-out keeps the tree shallow, so an equality lookup or the start of a range can reach a small part of a large table without reading every row. Once the first matching leaf entry is found, neighboring entries can be scanned in order.

Suppose an endpoint runs this query:

SELECT id, created_at, total_cents
FROM orders
WHERE customer_id = :customer_id
  AND created_at >= :start_date
ORDER BY created_at DESC
LIMIT 50;

In PostgreSQL, an index aligned with that access pattern is:

CREATE INDEX idx_orders_customer_created
ON orders (customer_id, created_at DESC)
INCLUDE (total_cents);

The reasoning matters more than the syntax:

1. customer_id is tested for equality, so it leads the key.
2. created_at defines both the range and output order, so it follows.
3. total_cents is returned but does not participate in navigation, so it can be payload rather than a key.
4. The row limit lets the scan stop after 50 qualifying entries.

A composite index is sorted from left to right. An index on (customer_id, created_at) can efficiently serve customer_id = ? and customer_id = ? AND created_at >= ?. It generally cannot jump directly to all rows for a date range when customer_id is unconstrained, because those dates are scattered across customer groups.

The index should be designed from stable access patterns, not from a list of columns that “might be useful.” The database-design interview guide shows how to derive those patterns before choosing a schema.

Why the optimizer may skip it

An existing index is only a candidate. The optimizer estimates the cost of using it and may decide that scanning the table is cheaper. That is often correct.

One common mistake is making a predicate non-sargable, meaning it cannot navigate the stored keys efficiently:

-- Harder to use with a plain index on created_at
WHERE DATE(created_at) = DATE '2026-08-15'

-- Expresses the same day as a range over the indexed column
WHERE created_at >= TIMESTAMP '2026-08-15 00:00:00'
  AND created_at <  TIMESTAMP '2026-08-16 00:00:00'

The second form leaves the column bare and defines a half-open range. An expression index can support the first form, but it should be added because the expression is a real, repeated access pattern, not because one query happened to be written that way.

Use EXPLAIN (ANALYZE, BUFFERS) in a safe test environment when you need actual execution evidence. Compare estimated rows with actual rows and locate the node doing most of the reads or time. Do not disable sequential scans to “fix” a production plan; forcing a plan can hide the real issue.

Covering reads without ignoring the write tax

An index-only or covering access path can answer a query from index entries without retrieving every base row. It is useful when a frequent query reads a small, stable set of columns. It is not a free upgrade.

Every additional index has costs:

• An insert adds an entry to every maintained index.
• An update may create new entries when indexed values or row versions change.
• Deletes leave cleanup work and can contribute to bloat until maintenance catches up.
• Wider indexes consume more memory and storage, making caches less effective.
• Replication and recovery must carry the additional write volume.

A partial index can reduce this cost when a small subset drives the query:

CREATE INDEX idx_orders_pending_created
ON orders (created_at)
WHERE status = 'pending';

This is a strong fit when pending rows are rare and an operational worker repeatedly fetches them. It is a weak fit when the predicate includes most of the table or changes so often that rows churn in and out of the index.

The storage engine changes the final cost model:

These differences explain why an index can cover a query differently across engines and why a compact primary key matters especially in clustered storage. The underlying structure trade-off is explored further in B+ tree versus LSM tree.

This video gives a visual explanation of B-tree fan-out and page-oriented lookup:

A reliable interview walkthrough

When you receive a slow query and a schema, resist the urge to name an index immediately. Walk through the evidence in this order:

1. Restate the access pattern. Which rows are needed, how many are expected, which columns are returned, and is ordered output required?
2. Read the existing plan. Identify the expensive node and compare estimated rows with actual rows.
3. Check the predicate. Look for wrapped columns, implicit casts, broad filters, and join-key type mismatches.
4. Propose the smallest matching index. Put equality keys first, then range or ordering keys. Add payload only when it meaningfully avoids row reads.
5. Price the write path. State the effect on inserts, updates, storage, cache, and replication.
6. Name the validation. Re-run the plan with representative data and compare latency, buffers, and write overhead.

That answer is stronger than “add an index on created_at” because it is falsifiable. It tells the interviewer when the index should help and what evidence would make you reject it.

Indexing is usually an early scaling step, not the final one. If a well-indexed workload still exceeds one node’s storage or write capacity, sharding and partitioning becomes relevant. Do not jump there while a query still scans avoidable data.

FAQ

Why not create an index for every frequently filtered column?

Because filters interact. Several single-column indexes may still be worse than one composite index that matches the full access pattern, and every index increases write and storage cost. Start from the query shapes you must support.

Should the most selective column always come first in a composite index?

No. Key order must match the predicates and ordering. Equality columns usually precede range or sort columns. Selectivity helps, but it is not a replacement for the left-to-right access pattern.

Does a covering index guarantee an index-only scan?

No. The optimizer still compares costs, and some engines must consult base storage for visibility or other metadata. Verify with the actual execution plan.

Is a sequential scan always bad?

No. It is often optimal for a small table or a query that needs a large percentage of rows. The goal is the cheapest correct access path, not an index-shaped plan.

When should I consider a different database model?

When access patterns, consistency needs, scale, or data shape no longer fit the relational design, not because one query is slow. The SQL versus NoSQL guide provides a broader decision framework.