How does a database index actually work?

The Answer

Say this in the room. 45 seconds.

• An index is a separate structure, usually a B+tree, holding the indexed values in sorted order with a pointer to the row.
• Sorted is the entire mechanism. Finding a value is a descent through a few levels, not a walk through the table.
• Because it is sorted, the same index also serves range queries, ORDER BY and MIN/MAX — not just equality. That is the half most people miss.
• A clustered index is the table's physical order, so a table can have only one. A non-clustered index is separate, and using it usually costs a second read to fetch the row.
• If the index contains every column the query needs, that second read never happens — a covering index.
• Every index is maintained on every insert, update and delete of its columns. Indexes are not free; they are a trade of write cost for read speed.

Understand It

The runnable blocks on this page are a model, not a database. No SQL runs here. What they demonstrate is the one property a B-tree index has and a heap table does not — the keys are kept sorted — because every claim below follows from that alone. A real B+tree has a fanout in the hundreds, so its depth is three or four rather than twenty; the counts here are pessimistic and the shape of the argument is the same.

A lookup stops being a search

A table without an index is a heap: rows in whatever order they were written. Finding a value means reading all of them, because nothing rules any row out.

An index holds the same values sorted, so most of them can be discarded with each comparison:

int target = 12_345;

int scanned = 0, scanHits = 0;
for (int row = 0; row < ROWS; row++) {
    scanned++;
    if (customerOf(row) == target) scanHits++;
}

int[] hit = seek(target);
int cursor = hit[0], indexHits = 0;
while (cursor < ROWS && keyAt(cursor) == target) { cursor++; indexHits++; }

System.out.println("  rows in the table         : " + ROWS);
System.out.println("  full scan, rows examined  : " + scanned + ", matched " + scanHits);
System.out.println("  index, key comparisons    : " + hit[1] + ", matched " + indexHits);
System.out.println("  rows the index never read : " + (ROWS - indexHits));

  rows in the table         : 1000000
  full scan, rows examined  : 1000000, matched 4
  index, key comparisons    : 20, matched 4
  rows the index never read : 999996

Twenty comparisons against a million row reads, for the same four rows. And the ratio gets better as the table grows: doubling the rows adds exactly one comparison, while the scan doubles. That is what people mean when they say a scan is O(n) and an index lookup is O(log n) — the difference is not a constant factor you can optimise away, it is a different curve.

A real B+tree does better still. Its nodes are pages holding hundreds of keys, so a million-row index is three or four levels deep, and the database reads three or four pages rather than twenty individual keys.

Range and ORDER BY come free, and this is the part people miss

Most explanations stop at equality lookups, which makes an index sound like a hash map. It is not — a hash index would handle = and nothing else. A B-tree keeps entries in order, so once you have found where a range starts you simply read forward:

int from = 100_000, to = 100_004;

int scanned = 0, scanMatches = 0;
for (int row = 0; row < ROWS; row++) {
    scanned++;
    int c = customerOf(row);
    if (c >= from && c <= to) scanMatches++;
}

int[] start = seek(from);
List<Integer> ordered = new ArrayList<>();
int cursor = start[0];
while (cursor < ROWS && keyAt(cursor) <= to) { ordered.add(keyAt(cursor)); cursor++; }

System.out.println("  range " + from + ".." + to);
System.out.println("    scan  : examined " + scanned + ", matched " + scanMatches
    + ", still needs a sort");
System.out.println("    index : " + start[1] + " comparisons, then " + ordered.size()
    + " sequential reads");
System.out.println("    index output already ordered? "
    + ordered.equals(ordered.stream().sorted().toList()));

  range 100000..100004
    scan  : examined 1000000, matched 20, still needs a sort
    index : 20 comparisons, then 20 sequential reads
    index output already ordered? true

The scan examined everything and then still had work to do, because the matching rows came out in table order. The index found the start and walked forward, and the output was already sorted — no sort step at all.

That single property explains a family of things one index can do:

The last two rows are one interview question. A leading wildcard cannot use the index because the sorted order is by prefix, and there is no place in a sorted list where all the strings ending in abc are together.

Clustered, non-clustered, and the second read

A clustered index determines the physical order of the rows themselves — the table is the index, with the row data in its leaves. There can be only one, and in InnoDB it is the primary key whether you asked for one or not.

A non-clustered index is a separate structure whose leaves hold the key and a pointer. Using it takes two steps: find the entry, then fetch the row it points at. That second step is a random read per row, which is why the planner sometimes decides a full scan is cheaper — a scan is sequential, and thousands of random fetches are not.

Which gives the most useful index-tuning idea there is: if the index already contains every column the query touches, the second step never happens.

CREATE INDEX idx_orders_customer ON orders (customer_id, status, total);

SELECT status, total FROM orders WHERE customer_id = 42;   -- covered
SELECT * FROM orders WHERE customer_id = 42;               -- not covered

The first query is answered entirely from the index. The second has to visit the table for every matching row. Plans call this an index-only scan, and it is often the difference between a query that is fast and one that is fast enough.

What every index costs

Nothing about an index is free, and this is where "just add an index" stops being a good answer:

int depth = (int) Math.ceil(Math.log(ROWS) / Math.log(2));
for (int n : new int[] { 0, 1, 3 }) {
    System.out.println("  one INSERT with " + n + " index(es) : 1 row write, "
        + n + " index write(s), ~" + (n * depth) + " comparisons to place them");
}
System.out.println("  index depth for " + ROWS + " rows : ~" + depth + " levels");

  one INSERT with 0 index(es) : 1 row write, 0 index write(s), ~0 comparisons to place them
  one INSERT with 1 index(es) : 1 row write, 1 index write(s), ~20 comparisons to place them
  one INSERT with 3 index(es) : 1 row write, 3 index write(s), ~60 comparisons to place them
  index depth for 1000000 rows : ~20 levels

Every index on a table is another structure to locate a slot in and write to, on every insert, on every delete, and on every update that touches its columns. Add disk space, and page splits when a node fills.

So the real trade is: a table with eight indexes has fast reads on eight access paths and writes that cost roughly nine times a bare insert. On a write-heavy table that is the wrong side of the bargain, and unused indexes are pure loss — every database can report which indexes have never been used, and that report is usually surprising.

Why the index you added did nothing

An index only helps if the planner can use it, and four things stop it:

• A function on the column. WHERE UPPER(name) = 'ANA' cannot use an index on name, because the index stores name, not UPPER(name). Index the expression instead, or store it normalised.
• A type mismatch. Comparing a VARCHAR column to a number makes the database cast the column, which is a function on the column, which is the previous case.
• A leading wildcard. LIKE '%abc' — no contiguous range exists.
• Low selectivity. If a value matches a third of the table, using the index means a third of the rows fetched one random read at a time. A sequential scan is genuinely cheaper, and the planner is right to choose it. This is why an index on a boolean or a status column with three values is usually pointless — and why the same index can be used for a rare value and ignored for a common one, in the same table, on the same day.

That last point is worth stating plainly in an interview: the planner ignoring your index is usually the planner being correct. The interesting question is whether its row estimates are accurate, which is what EXPLAIN ANALYZE answers.

Reference

The statements, the diagnostics, and the numbers to look at. Copy from here.

Creating them

-- Plain B-tree. Works for =, ranges, ORDER BY, MIN/MAX, prefix LIKE.
CREATE INDEX idx_orders_customer ON orders (customer_id);

-- Composite: leftmost prefix rule applies. Equality columns first, range last.
CREATE INDEX idx_orders_lookup ON orders (tenant_id, status, created_at);

-- Covering: the extra columns answer the query without touching the row.
CREATE INDEX idx_orders_covering ON orders (customer_id) INCLUDE (status, total);  -- Postgres, SQL Server
CREATE INDEX idx_orders_covering ON orders (customer_id, status, total);           -- MySQL: just append

-- Partial: index only the rows anyone queries. Small, and skips the rest.
CREATE INDEX idx_orders_open ON orders (created_at) WHERE status = 'OPEN';         -- Postgres

-- Expression: for a predicate that wraps the column.
CREATE INDEX idx_users_lower_email ON users (LOWER(email));

-- Without locking writes out for the duration. Slower, and what you use in production.
CREATE INDEX CONCURRENTLY idx_orders_customer ON orders (customer_id);             -- Postgres

CREATE INDEX takes a write lock on the table for the whole build. On a large busy table that is an outage, and CONCURRENTLY is not optional — note it cannot run inside a transaction block, and a failed run leaves an invalid index you must drop.

Finding out what is happening

EXPLAIN ANALYZE SELECT * FROM orders WHERE customer_id = 42;

What to read, in order:

Which indexes are earning their keep

-- Postgres: never-used indexes, largest first
SELECT relname AS table, indexrelname AS index,
       pg_size_pretty(pg_relation_size(indexrelid)) AS size, idx_scan AS scans
FROM pg_stat_user_indexes
WHERE idx_scan = 0 AND indexrelid NOT IN (SELECT conindid FROM pg_constraint)
ORDER BY pg_relation_size(indexrelid) DESC;

-- MySQL 8
SELECT * FROM sys.schema_unused_indexes;

Run it before adding anything. On a table that has accumulated indexes for years, this query usually pays for itself immediately.

Rules of thumb worth keeping

Scenarios

Real situations, with the decision and the argument.

1. A query takes eight seconds. You add the obvious index and it still takes eight seconds.

Get the plan before doing anything else. Three likely readings.

Seq Scan still: the index is unusable — a function or an implicit cast on the column, or a leading wildcard. The SQL text will show it.

Index Scan with a large Rows Removed by Filter: the index is being used and narrowing almost nothing, which usually means a composite index with its columns in the wrong order.

Index Scan and genuinely fast, total time still eight seconds: the time is somewhere else — a join, a sort spilling to disk, or the application making this query four hundred times, which is an N+1 and not an index problem at all.

2. Adding an index to a 400-million-row table in production.

CREATE INDEX locks the table against writes for the whole build. On that size it is an outage measured in tens of minutes.

Use CREATE INDEX CONCURRENTLY on Postgres — slower, two passes, cannot run inside a transaction, and leaves an INVALID index if it fails, which you must drop before retrying. On MySQL 8 most index builds are online by default, but verify for your version and storage engine rather than assuming.

Then have a way back. Building an index is reversible; the load it puts on the primary while building is not, so do it in a low-traffic window even with the concurrent variant.

3. Reads are fast, inserts have doubled in six months, and nothing changed in the write path.

Count the indexes. If it went from three to eight, that is your answer — each insert now writes nine structures, and each of those may split a page.

Start with the never-used ones from the query above, then the redundant ones — anything whose columns are a leading prefix of another index. That is usually most of the growth, and dropping an unused index is one of the few database changes that is both safe and immediately measurable.

4. Your ORM generates the query and you cannot change the SQL.

You can still change the index, and usually should. Look at what Hibernate actually emitted — turn on show_sql or read the plan — because the column order in the generated WHERE clause is not the order you wrote in the entity, and it is the generated shape the index must match.

Where the ORM emits something genuinely unindexable, the options are a native query for that one path, a database view, or a computed column that is indexable. Fighting the ORM to produce different SQL is usually the most expensive of the four.

5. Someone proposes indexing every column "so any query is fast".

It makes writes cost one operation per index, roughly doubles or triples the table's storage, and most of those indexes will never be used because real queries filter on combinations rather than single columns — and a single-column index rarely serves a two-column predicate well.

The honest counter-proposal: index from the workload, not from the schema. Take the ten slowest queries by total time — not by individual duration, since a fast query run a million times matters more — and index for those. Then re-measure.

Interviewer's Next Move

The question after the question. This is what the round is actually testing.

1. "How does an index work?" It is a separate structure — normally a B+tree — holding the indexed values sorted, each with a pointer to its row. Sorted order means a lookup descends a few levels instead of reading every row, and a million-row index is three or four pages deep.

2. "So it is like a hash map?" No, and the difference matters. A hash index handles equality only. A B-tree keeps order, so the same index also serves ranges, ORDER BY, MIN, MAX and prefix LIKE.

3. "Why can't it help with LIKE '%abc'?" The entries are sorted by prefix, so everything starting with abc is contiguous, but everything ending in it is scattered. There is no range to descend to.

4. "What is a clustered index?" The one that determines the physical order of the rows — the table itself is the index, with row data in its leaves. There can be only one, and in InnoDB it is the primary key. Everything else is a separate structure holding a pointer.

5. "What is a covering index?" One that contains every column the query needs, so the row is never fetched. It removes the second random read per row, which is often where the time actually goes.

6. "What does an index cost?" Space, and a write to every affected index on every insert, delete, and update of its columns — plus page splits. A table with eight indexes has writes costing roughly nine times a bare insert, so an unused index is pure loss.

7. "You added an index and the query is still slow. Why?" Most likely the planner is not using it: a function or a cast on the column, a leading wildcard, or low selectivity where a scan is genuinely cheaper. EXPLAIN ANALYZE will say — and a large gap between estimated and actual rows points at stale statistics instead.

8. "Would you index a boolean column?" Usually not. Two values means any lookup matches about half the table, and fetching half the rows one random read at a time is slower than scanning. It can pay off if the distribution is very skewed, and then a partial index on the rare value is the better tool.

Code traps

Trap A — predict before you run:

CREATE INDEX idx_users_email ON users (email);

SELECT * FROM users WHERE LOWER(email) = 'ana@example.com';

Trap B:

-- account_number is VARCHAR(20), indexed
SELECT * FROM accounts WHERE account_number = 12345;

Trap C:

CREATE INDEX idx_a ON orders (customer_id);
CREATE INDEX idx_b ON orders (status);
CREATE INDEX idx_c ON orders (created_at);
CREATE INDEX idx_d ON orders (customer_id, status);

Common wrong answers

Check Yourself

Q1. Why does an index help ORDER BY created_at and not just WHERE created_at = ?

Q2. A query on an indexed column is doing a full scan. Give three plausible reasons.

Q3. What does a covering index remove, and how would you recognise the opportunity?

Practice