B-Tree Indexes

A balanced binary search tree with $n$ leaves has height $\log_2 n$. For 1 billion rows that's 30 levels — 30 disk reads per lookup. A B+ tree with fanout $f$ (keys per internal node) has height $\log_f n$. With $f = 200$ (realistic for 8 KB pages and 40-byte keys), the same 1 billion rows need only $\lceil \log_{200} 10^9 \rceil = 4$ levels.

High fanout is everything. One root page fits in RAM permanently. The second level (200 pages) likely stays warm in the buffer pool. For most lookups, only 1–2 disk reads actually touch storage. This is exactly why B+ trees dominate: the fan-out is tuned to the page size, not to pointer widths.

A B+ tree has two node types, both stored as fixed-size pages:

Internal nodes hold only keys and child pointers — no row data. A node with $k$ keys has $k+1$ children. On a 8 KB page with 8-byte keys and 6-byte pointers, you get fanout ~600.

Leaf nodes hold keys plus either row data (clustered index) or row pointers (secondary index). Leaves are linked in a doubly-linked list at the bottom of the tree — this is what makes range scans efficient: find the first key with a binary descent, then follow leaf pointers linearly.

Invariants: every non-root node is at least half full (prevents degenerate trees). Splits propagate upward; merges propagate downward on deletion. The tree height almost never changes in practice — inserts just fill existing pages.

Point lookup (WHERE id = 42): start at root, binary-search each internal node for the target key, follow the matching child pointer, repeat until leaf. $O(\log_f n)$ page reads — typically 3–4 for billion-row tables.

Range scan (WHERE id BETWEEN 100 AND 200): descend to the leaf containing key 100, then walk the linked leaf list until 200. I/O cost = depth + (number of qualifying leaf pages). This linear leaf scan is sequential on disk if the tree was built in key order — a very common case after a CLUSTER or bulk load.

-- Postgres: force index use and inspect cost
EXPLAIN (ANALYZE, BUFFERS)
SELECT * FROM orders WHERE order_id BETWEEN 100 AND 200;
-- Look for: Index Scan, Buffers: shared hit=N read=M

Clustered (primary) index: leaf nodes contain the actual row data. The table is stored sorted by the index key. InnoDB always clusters on the primary key. Postgres heap tables are not clustered by default (CLUSTER orders USING orders_pkey physically reorders, but it doesn't stay sorted on writes).

Secondary index: leaf nodes contain the index key plus a pointer to the row (a (page_id, slot_id) or the primary key, depending on the engine). A lookup hits the secondary index then does a second lookup — the table heap fetch or primary key lookup.

A covering index includes all columns a query needs — the query is satisfied entirely from the index without touching the table. This eliminates the heap fetch, which is the expensive part of a secondary index lookup (especially when rows are scattered randomly across pages).

-- Without covering index: index scan + heap fetch per row
CREATE INDEX idx_orders_customer ON orders (customer_id);
SELECT customer_id, total FROM orders WHERE customer_id = 7;
-- total requires a heap fetch for each matching row

-- With covering index: index-only scan
CREATE INDEX idx_orders_customer_total ON orders (customer_id, total);
SELECT customer_id, total FROM orders WHERE customer_id = 7;
-- EXPLAIN shows: Index Only Scan — zero heap fetches

In Postgres, an index-only scan still checks the visibility map to confirm whether the index tuple is visible to the current transaction — a small overhead, but far cheaper than a heap fetch.

Indexes are not free. Every INSERT, UPDATE, or DELETE must maintain all indexes on the table. A table with 5 indexes turns one logical write into at least 6 physical page updates — plus potential page splits that cascade up the tree.

Page splits are the worst case: when a leaf is full, it splits into two half-full leaves, and the parent needs a new separator key. If the parent is also full, the split propagates. Each split dirtifies 2–3 pages and writes WAL records for all of them.

Mitigation strategies:

• Monotonically increasing keys (UUIDs v7, sequences): inserts always go to the rightmost leaf — no splits in the middle of the tree, excellent sequential I/O.
• Random UUIDs (v4): inserts scatter across the tree, causing frequent mid-tree splits and fragmenting leaf pages. Write amplification can be 5–10x higher than sequential keys.
• Fill factor: CREATE INDEX ... WITH (fillfactor=70) leaves 30% of each page empty for in-place updates, deferring splits.

Internal nodes route lookups; leaf nodes store data and are linked for range scans:

A few opinionated rules that hold across Postgres, MySQL, and SQL Server:

• Index selectivity matters: an index on a boolean column (2 distinct values) is almost never used by the optimizer — it's cheaper to scan the table.
• Leading column rule: a composite index (a, b, c) supports filters on a, (a, b), or (a, b, c) — but not on b or c alone. Design the leading column for your most common filter.
• Avoid over-indexing: each index adds ~10–30% write overhead on inserts. Most tables need 3–5 indexes maximum.
• EXPLAIN ANALYZE is ground truth: the optimizer's cost estimates can be wrong; always verify with real execution plans and BUFFERS output before and after adding an index.

Indexes exist but the planner chooses a sequential scan in these common situations:

Fix: run ANALYZE, create functional indexes, or hint the planner with SET enable_seqscan = off (debugging only — never in production).