What a b-tree index actually is

From a name to a structure

SQL: where & operators closed with a lesson naming B-tree indexes and showing EXPLAIN ANALYZE output, enough to tell Index Scan from Seq Scan. This course starts from that name and builds the structure underneath it. The next lesson then watches an index change a real query's plan.

A phone book, not a pile of papers

An unindexed table is a pile of papers in the order they were dropped. Finding one paper means checking every page until it turns up, or until the pile runs out. A B-tree (balanced tree) index is closer to a phone book. The entries are sorted, so you jump to roughly the right spot and narrow down from there instead of checking every page.

flowchart TB
  M["m..."] --> D["d..."]
  M --> S["s..."]
  D --> AC["a-c<br/>rows"]
  D --> EL["e-l<br/>rows"]
  S --> NR["n-r<br/>rows"]
  S --> TZ["t-z<br/>rows"]

Structurally, this is a tree: a root node at the top, branching into child nodes, ending in leaf nodes that point at table rows. "Balanced" means something specific: every leaf sits at the same depth from the root. Whichever value you search for, reaching a leaf visits the same number of nodes. No value is buried three times deeper than the rest.

Why balance turns into speed

A search starts at the root. At each node it compares the target value, picks one branch, and discards everything on the other side without looking at it. Each step down eliminates a large fraction of the remaining rows, so the number of steps grows far slower than the number of rows. Going from 1,000 rows to 1,000,000, a thousand times more data, adds only a handful of steps. The next lesson measures this.

Sorted order is the whole trick

Every operation a B-tree supports well traces back to one fact: it stores values in sorted order. Equality (email = 'x') means walking straight to where 'x' would sit. A range (created_at >= '2025-01-01') means walking to the start of the range, then reading forward, since sorted neighbors sit next to each other in the index's leaf pages. IS NULL, BETWEEN and IN work the same way. So does LIKE 'prefix%', but only with an index built for pattern matching (text_pattern_ops), as SQL: where & operators showed.

What a B-tree can't do follows the same logic in reverse. LOWER(email) = 'x' needs the lowercased value's position, but the tree is sorted by the original value, so the order doesn't help. That's the sargability rule from SQL: where & operators: the same sorted-order fact, seen from the other side.

Key takeaways

• A B-tree index is a sorted, balanced tree with every leaf at the same depth, so a lookup takes about the same number of steps for any value.
• Balance is why steps grow far slower than rows: a thousand times more rows costs only a handful more steps.
• Every B-tree-friendly operation (equality, ranges, prefixes) reduces to "find a position in sorted order, then read nearby". Sargability is the same fact seen from what breaks it.