SQL / INDEXES AND QUERY PERFORMANCE
How a B-tree index finds rows without scanning
Trace an index lookup from the root page down to a leaf entry and predict how many pages a query reads instead of assuming the table gets scanned.
What you will learn
- Trace a lookup root-to-leaf and count the pages it actually reads
- Estimate index depth as ceil(log_fanout(rows)) from page size and key size
- Explain a range query as one descent plus an ordered walk along the leaves
- Read a composite index's key order to see which predicates can start a descent
Understanding How a B-tree index finds rows without scanning
An index is not a lookup list bolted onto the table; it is a sorted copy of one or more columns, cut into fixed-size pages that point at each other. The bottom level, the leaves, holds every indexed value in key order together with a locator for the row it came from. Every level above holds only separator keys and child pointers: everything under this pointer is at least 40, everything under the next is at least 70. Sorted order is the whole mechanism, because one comparison against a separator key discards entire subtrees that are then never read.
A lookup starts at the root, searches the keys on that single page, follows the one pointer whose range covers the value, and repeats until it lands on a leaf. The number of pages touched is the depth of the tree, ceil(log_fanout(rows)), and with a few hundred keys per page that depth stays at three or four even for tables in the hundreds of millions of rows. The upper levels are read by every single lookup, so they sit in memory permanently; the marginal cost of one lookup is usually the leaf page plus the row fetch.
Because leaves are stored in key order and chained to their neighbours, a range predicate or a matching ORDER BY costs one descent plus a forward walk: find the first entry at or above the lower bound, then read forward until an entry exceeds the upper bound and stop. What the walk produces is keys and locators, not rows, so each hit normally costs another read to fetch the row, which is why a lookup matching a large slice of the table loses to a plain scan even though its descent is cheap. Page splits keep every leaf exactly the same distance from the root, so there is no such thing as an unlucky key that takes longer to find.
-- A miniature B-tree index on customer_id, written out page by page.
-- level 1 = root: separator key -> child page
-- level 0 = leaf: indexed key -> row locator
CREATE TABLE idx (page INTEGER, level INTEGER, keyval INTEGER, ptr INTEGER);
INSERT INTO idx VALUES
( 1, 1, 0, 10), ( 1, 1, 40, 11), ( 1, 1, 70, 12),
(10, 0, 5, 501), (10, 0, 18, 502), (10, 0, 31, 503),
(11, 0, 40, 504), (11, 0, 57, 505), (11, 0, 66, 506),
(12, 0, 70, 507), (12, 0, 84, 508), (12, 0, 99, 509);
-- Read 1: the root only. Which child page can possibly hold 57?
SELECT 'root: 57 belongs under page ' || ptr AS step
FROM idx
WHERE page = 1 AND keyval <= 57
ORDER BY keyval DESC
LIMIT 1;
-- Read 2: that one leaf page.
SELECT 'leaf ' || page || ': keyval ' || keyval || ' -> row locator ' || ptr AS step
FROM idx
WHERE page = (SELECT ptr FROM idx
WHERE page = 1 AND keyval <= 57
ORDER BY keyval DESC LIMIT 1)
AND keyval = 57;
-- What the descent cost.
SELECT 'pages read: 2 of ' || COUNT(DISTINCT page)
|| ', leaf entries examined: 3 of '
|| SUM(CASE WHEN level = 0 THEN 1 ELSE 0 END) AS step
FROM idx;An index lookup reads a path rather than a table: each page compared eliminates all but one subtree, so the cost tracks the tree's depth, not the row count.
Worked examples
A range is one contiguous run of leaves
Shows that a BETWEEN predicate lands on a single stretch of leaf entries that spans pages through sibling pointers.
CREATE TABLE leaf (page INTEGER, next_page INTEGER, keyval INTEGER, ptr INTEGER);
INSERT INTO leaf VALUES
(10, 11, 5, 501), (10, 11, 18, 502), (10, 11, 31, 503),
(11, 12, 40, 504), (11, 12, 57, 505), (11, 12, 66, 506),
(12, NULL, 70, 507), (12, NULL, 84, 508), (12, NULL, 99, 509);
SELECT page, keyval, ptr
FROM leaf
WHERE keyval BETWEEN 40 AND 84
ORDER BY keyval;Example explained
Line 1The five matches are adjacent, which is only true because leaf entries are stored in key order.
Line 2The run begins mid-page on page 11 and continues on page 12 via next_page, so the engine never climbs back to the root.
Line 3The engine stops at the first entry above 84 instead of reading pages 12's remaining key 99 or page 10 at all.
Line 4In the real index the entries emerge ascending by construction, which is why ORDER BY keyval needs no sort step.
Key order of a composite index
Shows why an index on (status, created_at) can start a descent for status but not for created_at alone.
CREATE TABLE ticket (id INTEGER, status TEXT, created_at TEXT);
INSERT INTO ticket VALUES
(1, 'open', '2026-01-04'),
(2, 'closed', '2026-01-02'),
(3, 'open', '2026-01-09'),
(4, 'closed', '2026-01-07'),
(5, 'open', '2026-01-11');
-- The leaf order of an index on (status, created_at):
SELECT status || ' / ' || created_at || ' -> row ' || id AS index_entry
FROM ticket
ORDER BY status, created_at;Example explained
Line 1ORDER BY status, created_at reproduces the leaf level: that ordering is what the index physically is.
Line 2status = 'open' is one descent plus a walk, because its three entries form a block, already in date order.
Line 3created_at >= '2026-01-07' alone has no block: 01-07 sits inside the closed run and 01-09 inside the open run, so there is no page to descend to.
Line 4Defining the index as (created_at, status) instead would make the date range one run and scatter the statuses.
Why depth stays tiny
Computes how many keys each additional level of a tree with fanout 400 can address.
-- Each level multiplies addressable keys by the fanout.
WITH RECURSIVE tree(level, max_keys) AS (
SELECT 1, CAST(400 AS BIGINT)
UNION ALL
SELECT level + 1, max_keys * 400 FROM tree WHERE level < 4
)
SELECT 'level ' || level || ': up to ' || max_keys || ' keys' AS capacity
FROM tree;Example explained
Line 1400 is a realistic fanout: an 8 KB page holds roughly 400 entries of about 20 bytes of key plus pointer.
Line 2Three levels already cover 64 million rows, so a single-row lookup there reads 3 index pages plus the row.
Line 3Growing from 64 million to 25 billion rows adds exactly one page read, which is the practical meaning of logarithmic depth.
Line 4Read the table backwards to get depth: it is the smallest power of the fanout that exceeds the row count.
Important notes
Duplicate keys still form one contiguous run, so equality on a low-cardinality column is still a single descent; the cost lives in the length of the walk, not in finding its start.
Ordering, not raw speed, is why B-trees are the default index type: a hash index answers equality in one probe but cannot serve ranges, prefixes, or ORDER BY at all.
Common mistakes
Assuming any predicate on an indexed column is fast: if it matches 40 percent of the rows, the walk is cheap but each of the millions of hits triggers a separate row fetch, so the planner abandons the index and scans, leaving you with write overhead and no gain.
Querying only the second column of a composite index, such as created_at on (status, created_at): those entries are spread through every status block, so there is no page to descend to and the query degrades to a full scan.
Believing a leaf entry is the row: a lookup that returns 5,000 entries can issue up to 5,000 additional scattered reads, which is why its runtime is far worse than the entry count suggests.
Try it yourself
Change, predict, then run
Rebuild the four-page idx table from the main example, then run the same two queries for keyval 4 and keyval 100 and confirm each search still reads exactly two pages while returning no leaf entry. Then insert (12, 0, 92, 510) and search for 92 to see that the root page needed no change.
Open the SQL workspaceCheck your understanding
A table grows from 2 million to 200 million rows. Its B-tree index on order_id fits about 500 entries per page. What happens to the pages read by a single-row lookup on order_id?
- It rises 100-fold, in proportion to the row count
- It stays exactly the same, because a B-tree lookup is constant time
- It rises by roughly one level, from about 3 page reads to about 4
- It doubles, because each new level doubles the comparisons at the root
Show answer
Depth is ceil(log_fanout(rows)): 500 squared is 250,000 and 500 cubed is 125 million, so 2 million rows needs three levels and 200 million needs four. Option 2 is tempting but describes a hash index; a B-tree must compare keys level by level, and it is exactly that ordered comparison that also lets it serve ranges and ORDER BY.