B+Tree Index

What is it: A balanced M-ary search tree where all data resides in leaf nodes; internal nodes contain only routing keys. The default index type in PostgreSQL.

Why: A full table scan on a 100M-row table reads all rows sequentially — O(n). A B+Tree index traverses log_M(n) nodes to find any row — O(log n). With fan-out 300, height 4 covers 8 billion rows. After finding the start, range queries scan the leaf linked list without re-traversing the tree.

Node structure: internal nodes hold up to M-1 keys and M child pointers. Leaf nodes hold key-pointer pairs where the pointer is a heap tuple ID (TID: page number + offset). Fan-out M is determined by page size (8KB) divided by key + pointer size, typically 100–400.

graph TD root["Root: routing keys only<br/>[30 | 60]"] root --> n1["[10 | 20]"] root --> n2["[40 | 50]"] root --> n3["[70 | 90]"] n1 --> l1["Leaf: keys 1-9<br/>-> TID(page,offset)"] n1 --> l2["Leaf: keys 10-19"] n1 --> l3["Leaf: keys 20-29"] n2 --> l4["Leaf: keys 30-39"] n2 --> l5["Leaf: keys 40-49"] n3 --> l6["Leaf: keys 50-69"] l1 -.->|"linked list"| l2 -.->|"linked list"| l3 -.->|"linked list"| l4

A point lookup for key 25 walks root → n1 → l3 in 3 hops regardless of table size (that's the O(log n)). A range query BETWEEN 15 AND 35 finds 15 the same way, then follows the leaf linked list forward (l2 → l3 → l4) instead of re-descending the tree for every subsequent key — this is why range scans on an indexed column are cheap even for large ranges.

Leaf linked list: leaves are doubly linked in sorted key order. Range queries (BETWEEN, >, <) find the first matching leaf in O(log n) then scan forward in O(k) for k matching rows — far cheaper than traversing the tree for each result.

Index scan vs sequential scan: the planner estimates costs. Index scan = random I/O per matching row (expensive). Sequential scan = read all pages sequentially (cheaper per page). The crossover is ~5–10% of table rows — if more rows match, sequential scan wins. Bitmap heap scan is the middle ground: scan index to get all TIDs, sort by physical page order, then read pages sequentially.

Trade-offs:

  • Reads: O(log n) search, O(k) range scan — fast
  • Writes: every INSERT/UPDATE/DELETE must update the index — slower writes proportional to number of indexes
  • Storage: each index is a separate on-disk B+Tree, typically 20–30% of table size
  • Maintenance: index pages can become fragmented (half-empty after many deletions) — REINDEX or VACUUM reclaims space; fragmented indexes waste I/O

Real-world usage: Proxel's proxy_stats table had no index on (proxy_id, checked_at) — range queries for recent stats did full scans. Adding a composite index on (proxy_id, checked_at DESC) reduced query time from 400ms to 3ms.

Common pitfall

Adding an index and expecting it to always be used is the most common misunderstanding — the planner estimates the cost of an index scan vs a sequential scan and picks whichever is cheaper for the specific query and table statistics, not just whichever index technically applies. A query matching 15% of a table's rows may get a sequential scan even with a perfectly good index present, because random I/O for that many matching rows costs more than reading every page sequentially. See Query Optimization for reading EXPLAIN output to confirm which path the planner actually chose, rather than assuming from the schema alone.