How does a B-tree index actually speed up a query, and when does it stop helping?
A B-tree index stores column values in a sorted, balanced tree structure, so instead of scanning every row (a full table scan) to find matches, the database can walk down the tree in roughly O(log n) comparisons to jump straight to the matching rows. It works well for equality lookups and range queries because the sorted structure lets the database skip entire branches that can’t contain a match.
Why it doesn’t always get used
The query planner estimates the cost of using the index versus a full table scan, and if a query would match a large fraction of the table anyway (low selectivity, like a boolean column that’s 90% true), reading the index and then jumping around the table to fetch each matching row can actually be slower than just scanning the table sequentially. The planner picks whichever is cheaper, not whichever exists.
Best practice
Index columns with high selectivity (many distinct values) that are actually used in `WHERE`, `JOIN`, or `ORDER BY` clauses, and design composite indexes with the most selective or most-filtered column first so the tree can narrow down quickly before considering the rest.
Edge case interviewers probe for
Why doesn’t a function applied to an indexed column, like `WHERE LOWER(email) = ‘x’`, use the index? Because the index is built on the raw column values, not the function’s output, so the planner can’t use the sorted structure to look up a transformed value, it has to fall back to scanning and computing the function on every row, unless a functional index is created specifically on that expression.
Common mistake
Adding an index to every column that appears in a `WHERE` clause without checking selectivity or actual query patterns. Excess indexes slow down every write (insert/update/delete has to update every index on the table too), so unused or low-selectivity indexes are pure cost with no benefit.
What the interviewer is checking
Whether you understand indexing as a cost tradeoff the planner actively reasons about, not a guaranteed speedup, and whether you know concrete cases (low selectivity, functions on columns) where an index silently gets skipped.
Think of a phone book sorted alphabetically by last name, that’s a B-tree index. Looking up “Smith” is fast because you can jump straight to the S section instead of reading every single entry from the start. But if you wanted everyone whose last name starts with any letter from A to Z except one, the “index” (the alphabetical sorting) barely helps, since you’d end up flipping through almost the whole book anyway, at that point it’s not meaningfully faster than just reading straight through.
That’s exactly why databases sometimes skip an index even though one exists: if a query is going to match most of the table anyway, jumping around a sorted structure to find each match one at a time can be slower than just reading straight through in order. The index only pays off when it lets you skip most of the data.
Why interviewers ask this
Query performance issues are one of the most common real-world DBA responsibilities, and this question separates “I added an index” from actually understanding when and why it helps.
What a strong answer signals
That you reason about selectivity and planner cost estimates, not just “indexes make things faster,” and that you know indexes have a write-side cost too.
Common follow-ups
- What’s the difference between a B-tree and a hash index?
- How do you design a composite (multi-column) index’s column order?
- How would you check whether the planner is actually using an index?
Advanced variation
“When would a hash index outperform a B-tree?” expects knowing hash indexes are O(1) for pure equality lookups but can’t support range queries or sorting at all, unlike a B-tree’s ordered structure.
A reporting query filtering on a `status` column (with only two possible values, and one of them covering 95% of rows) had an index on `status` that the planner simply ignored, running a full table scan instead. This looked like a bug until the team realized the planner’s decision was correct: with such low selectivity, the sequential scan really was cheaper. Replacing the query’s approach with a composite index on `(status, created_at)`, matching the actual filter plus sort pattern, gave the planner something genuinely selective to use and cut the query time significantly.
-- Low selectivity: planner will likely ignore this index
CREATE INDEX idx_orders_status ON orders (status);
-- Better: composite index matching the real filter + sort pattern
CREATE INDEX idx_orders_status_created
ON orders (status, created_at);
-- Confirm whether the planner actually uses it
EXPLAIN ANALYZE
SELECT * FROM orders
WHERE status = 'pending'
ORDER BY created_at DESC;- 1A B-tree index lets the database jump to matching rows in roughly O(log n) instead of scanning every row.
- 2The query planner uses an index only when its estimated cost beats a full table scan.
- 3Low-selectivity columns (few distinct values) often make the index not worth using at all.
- 4A function applied to an indexed column usually prevents the index from being used unless a functional index exists.
- 5Every index adds write-time cost, so unused or low-selectivity indexes are pure overhead.