B-Tree Indexes and How They Help

When an interviewer says 'this query is slow, what do you do?', the answer they are listening for almost always involves an index. Indexes are the single biggest lever on read performance, so they separate candidates who memorized syntax from those who understand how a database actually finds rows.

In this lesson you will build a precise mental model of the B-Tree index: what it stores, which operations it speeds up, and how to talk about it the way a senior engineer would.

Without an index, finding rows that match a condition forces the database to read every row in the table. This is a sequential scan (or full table scan). On a million-row table, that means a million row checks even if only one row matches.

An index is a separate, sorted data structure that lets the engine jump straight to matching rows, the same way a book index lets you find a topic without reading every page.

The default index in PostgreSQL, MySQL, SQL Server and most engines is a B-Tree (balanced tree). It stores the indexed column values in sorted order, organized into a shallow tree of pages.

• Each leaf node holds index keys plus a pointer to the actual table row.
• The tree stays balanced, so any lookup touches only a few pages, regardless of table size.

A lookup walks from the root down to a leaf in roughly log(N) steps instead of scanning all N rows.

You create a B-Tree index with CREATE INDEX. Name it clearly so a reviewer knows the table and columns at a glance.

Once this index exists, a query filtering on email can use it to find the matching row in a handful of page reads instead of a full scan.

Because a B-Tree keeps values sorted, it speeds up far more than exact matches. Interviewers love when you list these precisely:

• Equality: WHERE email = ?
• Range: WHERE age > 30, BETWEEN, <, >=
• Prefix matching: WHERE name LIKE 'Ada%' (but NOT '%da')
• ORDER BY on the indexed column, avoiding a sort
• MIN/MAX, since they sit at the ends of the sorted structure

Consider an orders table with millions of rows. A reporting query asks for recent orders. With an index on created_at, the engine seeks to the start of the range in the sorted index and walks forward only as far as needed.

The index turns a full-table scan into a bounded range scan, reading just the qualifying slice.

A frequently missed point: because the index is already sorted, the engine can return rows in index order and skip a separate sort step. This matters for ORDER BY and especially for top-N pagination.

If you sort by a column that has a matching index, the optimizer can read the index in order and stop early once it has enough rows.

A normal B-Tree index stores only the indexed column plus a row pointer. So after finding matching entries, the engine still has to go to the table (the heap) to read the other columns you selected.

That second hop is the heap fetch. It is cheap for a few rows but expensive when a query matches many rows, which is one reason a low-selectivity index is sometimes ignored. (You will see covering indexes solve this later.)

Never claim an index is used, prove it with EXPLAIN. In an interview, narrating the plan shows real understanding.

• Seq Scan means the index was NOT used.
• Index Scan or Index Seek means it was.

If you added an index but still see a sequential scan, the planner judged the scan cheaper, often because the query matches too large a fraction of the table.

A common interview gotcha: declaring a PRIMARY KEY or UNIQUE constraint automatically creates a supporting B-Tree index. You do not, and should not, add a second index on the same column.

This is why joins and lookups on primary keys are already fast, and why the question 'should I index the id column?' is usually a trap, it is already done for you.

Tie it together with a clean one-liner an interviewer can nod along to:

'A B-Tree index is a sorted, balanced structure that lets the engine find rows in log(N) page reads instead of scanning the whole table. It accelerates equality, range, prefix, and ORDER BY operations on the indexed columns, but each match still costs a heap fetch for non-indexed columns.'

Then back it with EXPLAIN. That combination of model plus evidence is what scores points.

Test your mental model of what a B-Tree index accelerates.

Key takeaways to carry into the next lesson:

• A B-Tree stores indexed values sorted in a balanced tree, giving log(N) lookups.
• It accelerates equality, range, prefix (leading) LIKE, ORDER BY, and MIN/MAX.
• Each match still needs a heap fetch for columns not in the index.
• Wrapping a column in a function or using a leading wildcard disables the index.
• Always verify with EXPLAIN; PRIMARY KEY and UNIQUE constraints index automatically.

Next: how to order columns when one index covers several at once.