Pointer Walk

Indexes and B-Trees

A million rows found in three hops. How a B-tree index turns a full scan into a short walk from root to leaf.

DatabasesIntermediate11 min read

Finding one row in a million

A table is, at its simplest, a long list of rows. Ask for the row with id = 43 and a database with no other information has only one option: read the rows one after another until it finds it.

Without an index: full scanInteractive

The table: 64 rows

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364

Start. Find the row with id 43. There is no index, so the database has no idea where it is. It starts at the first row.

Index pages read
0
Rows read
0

That is a full table scan. With 64 rows nobody notices. With a hundred million rows it is the difference between an instant page and a timeout.

An index is a second structure, kept next to the table, whose only job is to answer "where is the row with this value?" without reading everything. It is the same idea as the index at the back of a book.

The shape of an index: a B-tree

Most database indexes are B-trees. A B-tree is built from pages. Each page holds a sorted list of entries, and each entry says: values in this range are on that page below.

  1. Start at the root page

    There is exactly one. It splits the whole range of values into a few broad slices.

  2. Find the slice containing your value and follow it down

    You arrive at a page that splits that slice more finely. Every other slice is skipped, along with everything beneath it.

  3. Repeat until you reach a leaf page

    Leaf pages point at the actual rows.

With an index: three hopsInteractive
root
1–1617–3233–4849–64
branch
33–3637–4041–4445–48
leaf
row 41row 42row 43row 44

The table: 64 rows

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364

Start. Find the row with id 43, using the index. Every lookup starts at the root page of the tree.

Index pages read
0
Rows read
0

Three pages read instead of 43 rows. And the gap widens fast as the table grows.

Why it stays shallow

The demo's pages hold 4 entries each so that they fit on screen. Real pages hold hundreds. Each level of the tree multiplies the number of rows it can reach by that amount.

Example

100 entries per page

One level reaches 100 rows. Two levels reach 10,000. Three levels reach 1,000,000. Four levels reach 100,000,000.

A hundred times more rows costs one more hop.

That is why a lookup by an indexed column feels instant whether the table has a thousand rows or a billion. The work grows with the number of levels, not the number of rows.

Because the entries are sorted, the same tree also answers range questions. To find every order between two dates, walk down to the first date and then read along the leaf pages until the last.

Same query, different plan

The striking thing about adding an index is what does not change: your query.

sql
SELECT * FROM orders WHERE customer_id = 43;   -- reads every row

CREATE INDEX orders_customer_id ON orders (customer_id);

SELECT * FROM orders WHERE customer_id = 43;   -- three hops

The database decides for itself whether to use an index. To see what it chose, put EXPLAIN in front of the query.

With an index: three hopsInteractive
Lookup
root
1–1617–3233–4849–64
branch
33–3637–4041–4445–48
leaf
row 41row 42row 43row 44

The table: 64 rows

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364

Start. Find the row with id 43, using the index. Every lookup starts at the root page of the tree.

Index pages read
0
Rows read
0

What an index costs

Good at

  • Lookups and range queries on the indexed column become fast at any table size
  • Can also speed up sorting and joining on that column

Where it bites

  • Every insert, update and delete must also update each index, so writes get slower
  • Each index takes disk space and memory
  • An index nobody uses still costs on every write

So the rule is not "index everything". Index the columns you actually search, join or sort by.

When an index is ignored

An index is sorted by the stored value. Anything that hides that order makes it useless for the query.

QueryUses the index on the column?Why
WHERE email = 'a@b.com'YesExact value: walk straight to it
WHERE name LIKE 'Ada%'YesAll names starting with Ada sit together
WHERE name LIKE '%son'NoNames ending in "son" are scattered everywhere
WHERE LOWER(email) = 'a@b.com'NoThe index stores email, not LOWER(email)
WHERE active = true when most rows are activeUsually notReading most of the table is quicker with a scan

Key takeaways

  • Without an index, finding a row means reading the table from the start.
  • A B-tree index is a tree of sorted pages. Each page narrows the search to one slice.
  • With hundreds of entries per page, three or four hops reach millions of rows.
  • Adding an index changes how a query runs without changing the query.
  • Indexes speed up reads and slow down writes, so add them where queries need them.

Your progress

Check your progress

0%

  1. Read the page50% of this page

    When you have gone through the page and its animations, tick it off.

  2. Take the quiz50% of this page

    9 questions, from easy to hard. Take it as often as you like: the questions change, and only your best score counts.

Saved on this device only. See all your progress