BytewizeJoin the waitlist

How B-tree indexes find rows

Sorted pages, a short descent from root to leaf, and why a function on the column breaks it.

6 minute lesson

An index is a sorted copy you can search.

The last lesson showed what an index buys. Without one, WHERE email = 'alex@example.com' reads every row: a sequential scan. A B-tree index keeps the column's values sorted in a shallow tree of pages, each entry pointing at its row. Finding one value takes a handful of page reads, even with millions of rows.

Key terms

B-tree
A balanced tree of sorted pages. Every lookup walks from the root to a leaf, and the depth stays small even for huge tables.
sequential scan
Reading every page of a table in order and filtering each row.
selectivity
The fraction of rows a condition matches. Indexes pay off when it is small.

Root to leaf in four reads

Follow alex@example.com down a 10M-row index. Each page holds a few hundred keys, so three levels cover all 10M.

  1. Level 1 · root

    The root holds separator keys. alex@… sorts before g, so follow the first child.

    • < gfollow
    • g – n
    • n – t
    • ≥ t
    1. root
    2. internal
    3. leaf
    4. heap
  2. Level 2 · internal

    Same move on a narrower range: alex@… sits between ada@… and amir@….

    • < ada@
    • ada@ – amir@follow
    • ≥ amir@
    1. root
    2. internal
    3. leaf
    4. heap

    visited

  3. Level 3 · leaf

    The leaf holds the entry itself: the key plus a TID pointing at the row in the table.

    • Keyalex@…found
    • TID(4821, 7)page, item
    1. root
    2. internal
    3. leaf
    4. heap

    visited

  4. Heap

    One more read fetches the row from table page 4821. Four page reads in total, instead of 10M rows.

    • Rowid 9134Alex Rivera
    • Pages read4vs ~125k for a seq scan
    1. root
    2. internal
    3. leaf
    4. heap

    visited

Check yourself

users has a B-tree index on email. The table has 10M rows.

Which WHERE clause can't use that index as written?

  • email = 'alex@example.com'
  • email BETWEEN 'a' AND 'b'
  • lower(email) = 'alex@example.com'
  • email IN ('a@x.io', 'b@x.io')
Show the answer
  1. lower(email) = 'alex@example.com'

The index stores email values, not lower(email). Wrapping the column in a function hides it from the index, so Postgres falls back to scanning. Add an expression index on lower(email), or store emails already normalized.

A function on an indexed column hides it from the index. Index the expression or normalize the data.

Ask Postgres what it did

query.sql
EXPLAIN (ANALYZE, BUFFERS)
SELECT id, name FROM users
WHERE email = 'alex@example.com';
plan.txt
Index Scan using users_email_idx on users
    (cost=0.43..8.45 rows=1 width=40)
    (actual time=0.031..0.033 rows=1 loops=1)
  Index Cond: (email = 'alex@example.com'::text)
  Buffers: shared hit=4
Planning Time: 0.112 ms
Execution Time: 0.051 ms
  1. Line 1: The access path. The planner chose the index. Seq Scan on users here would mean it read the whole table.
  2. Line 4: Where the condition ran. Index Cond means the filter drove the descent. A Filter: line would mean rows were fetched first and checked afterwards.
  3. Line 5: Pages touched. Four buffers: root, internal, leaf and one heap page. The descent from the last card, measured.
  4. Lines 2 to 3: Estimate vs actual. rows=1 estimated, rows=1 actual. Big gaps between the two mean stale statistics; run ANALYZE.

Three ways to read a table

Seq scan

read all

Reads
Every page, in order
Wins when
You need a big share of the rows
Cost grows with
Table size

Index scan

descend + fetch

Reads
Index pages, then matching rows
Wins when
The filter is selective
Cost grows with
Rows matched

Index-only scan

index alone

Reads
Index pages; heap only for recently changed pages
Wins when
Every selected column is in the index
Cost grows with
Rows matched
Check yourself

Why does finding one row among 10 million take only about four page reads with a B-tree?

  • Each page holds hundreds of keys, so the tree is wide and only a few levels deep
  • The whole index is always in memory
  • The index hashes the value straight to its row
  • Postgres remembers the result of earlier lookups
Show the answer
  1. Each page holds hundreds of keys, so the tree is wide and only a few levels deep

A page of 8 KB holds hundreds of keys, so each level multiplies the reach by hundreds: three or four levels cover millions of rows. The descent reads one page per level, then the row.

Hundreds of keys per page make a B-tree shallow: millions of rows in three or four levels.

Recall

Why can a B-tree on email answer WHERE email > 'm' but not WHERE lower(email) = 'm'?

Show the answer

Its entries are sorted by email, so a range is one descent plus a walk along the leaves. lower(email) isn't what the index stores; it needs its own expression index.

Recap

  • A B-tree keeps values sorted in a shallow tree: a few page reads find any key.
  • Equality, ranges, IN and sorted reads can use it; a function wrapped around the column cannot.
  • Check with EXPLAIN (ANALYZE, BUFFERS), and trust a seq scan when the query matches most of the table.

Start with one byte

Join the waitlist and get the beta invite when it opens.

  1. Bit1U
  2. Nibble2U
  3. Byte4U
  4. Kilobyte8U
One unit more at every level