0
Challenge · 32Correct & Fast

How a B-tree index works

Perfused in ~85% of apps

DevLog's comments table is small in a demo and will not stay that way. At 50,000 rows, `select * from comments where post_id = 42` has to read every single row to find the one it wants -- and that cost grows with every comment anyone ever posts. This is the exact Seq Scan the capstone gate asks you to eliminate, and an index is not a magic switch: it's a second, sorted data structure that turns that search into a handful of comparisons instead of fifty thousand.

Core idea. A B-tree index is a separate, sorted copy of one column's values, organized as a shallow tree of pages: a root page, a layer of branch pages, and leaf pages holding the actual (value, row-location) pairs in order. Because it's sorted and shallow, Postgres can find any value in only a handful of page reads -- a root comparison, one branch, one leaf, then one jump to fetch the real row -- no matter how large the table grows. That speed on reads is paid for with extra work the index must do on every INSERT, UPDATE, and DELETE to stay sorted.
Playground, this isn't a screenshot
Find comments.post_id = 42 among 12 rows
no index — Seq Scan
23
3
42
15
35
7
27
19
47
11
39
31
rows examined: 0 / 12
checks rows in physical (insertion) order, one at a time, until it finds a match — or reaches the end.
with a B-tree index — Index Scan
root: [19 | 35]
[3,7,11,15]
[19,23,27,31]
[35,39,42,47]
leaf entry: post_id=42 → ctid
heap fetch → the actual row
pages touched: 0 (root, one branch, one leaf, one heap page)
the tree is sorted, so each level rules out everything except one child — a handful of comparisons, regardless of table size.
The gap only widens as the table grows. At 12 rows a Seq Scan checking every row barely matters. At 200,000 rows it is 200,000 comparisons; the B-tree is still 3 or 4 hops, because each extra level multiplies how many rows it can rule out. That is the whole reason indexes exist: they trade a little extra work on write (keeping the tree sorted) for a logarithmic instead of linear cost on read.
↑ play a little first, then dig in