B-Tree Indexing

Intermediate

How B-tree indexes organize data, how insertions cause node splits, how queries traverse the tree, and why indexes have a write amplification cost.

Step 1 of 5

Empty B-Tree Structure

A B-tree index starts as a single root node. In PostgreSQL, each B-tree page holds up to several hundred keys depending on key size. The tree height is O(log n): a table of 1 billion rows needs at most 5-6 page reads to locate any row.

Root

empty

Key Takeaways

→B-tree height determines how many I/O operations a lookup requires
→PostgreSQL default page size is 8KB: each page holds ~100-400 keys

1 / 5