Explain B-tree Indexes in Databases

1 / 66

indexing

B-tree Indexes

Speed up lookups, range scans, and ordered reads on a column by maintaining a balanced tree of sorted values.

Without an index, finding matching rows means reading every row in the table and checking it. Fine for a hundred rows. Ruinous for a hundred million.

A book's alphabetical index — jump straight to "Photosynthesis" instead of reading every page.

Key Concepts

A B-tree index is the structure that avoids that, and it is the default index type in every relational database.

Why it is so shallow. A B-tree keeps the indexed values sorted. It is not a binary tree — each node holds hundreds of values, because a node is one disk page.

Say each node holds 200 children:

    1 level   ->            200 rows
    2 levels  ->         40,000 rows
    3 levels  ->      8,000,000 rows
    4 levels  ->  1,600,000,000 rows

A billion-row table is four levels deep. Finding any value reads four pages instead of a billion. That is what O(log n) means in practice, and it is why the tree stays balanced — every value is the same distance from the top.

O(log n)

One structure, many query shapes. Because the values are sorted, the same index answers more than just "equals":

  - `WHERE email = ?` — walk down to the value
  - `WHERE age BETWEEN 20 AND 30` — find 20, then read forward until 30
  - `WHERE name LIKE 'Sh%'` — a known prefix is just a range
  - `ORDER BY created_at` — the index is already in that order, so no sort step
  - `MIN(id)` / `MAX(id)` — read one end of the tree

WHERE email = ?WHERE age BETWEEN 20 AND 30WHERE name LIKE 'Sh%'ORDER BY created_atMIN(id)

A covering index skips the table entirely. The index stores the indexed columns plus a pointer to the row. If the query only needs columns the index already holds, the database never follows the pointer.

An index on (customer_id, status) fully answers SELECT status FROM orders WHERE customer_id = 42. Add total to the query and it must now fetch every matching row from the table.

(customer_id, status)total

What indexes cost. Every INSERT, UPDATE and DELETE must also update each affected index. Five indexes on a table means a write does roughly six pieces of work rather than one.

INSERTUPDATEDELETE

So an index is a trade: faster reads, slower writes, more storage. An index nothing queries is pure loss, and most databases record how often each one is used so you can find those.

When the database ignores your index on purpose. An index is worth using only when it eliminates most of the table. If a query returns 60% of the rows, jumping to the table once per row is slower than reading the table straight through, so the optimiser scans — correctly.

This surprises people who assume an unused index means a broken index.

What a B-tree cannot do. LIKE '%son' has an unknown prefix, so sorted order gives no place to start and the whole index must be read. That is what full-text and trigram indexes are for.

LIKE '%son'

What the interviewer is probing.1. "Why is a B-tree the structure of choice for an index?" Probing: the fit with disk. Stalls: "It is fast." Moves up: it is shallow and balanced, so a lookup is a handful of page reads, and it supports range scans in order, which a hash index cannot.

2. "When does an index make things worse?" Probing: the cost side. Stalls: "Never." *Moves up:* every write must update it, so a heavily written table with many indexes slows down — and a low-selectivity index may be ignored anyway.

3. "What is a covering index?" Probing: the optimisation. Stalls: "A big index." Moves up: one containing every column the query needs, so the engine answers from the index alone without touching the table.

4. "Why might the planner ignore your index?" Probing: selectivity. Stalls: "A bug." *Moves up:* if it estimates a large fraction of rows match, a sequential scan is cheaper than random lookups plus table fetches.