Home β€ΊPostgreSQL β€ΊB-Tree Indexes

🌳 B-Tree Index Internals

How PostgreSQL Finds Your Row Without Scanning Every Page

The B-Tree is PostgreSQL's default index. It keeps keys sorted in a balanced tree of 8KB pages, where leaf pages are linked for efficient range scans. A lookup descends from root β†’ internal β†’ leaf in O(log n) I/O operations. For a table with 10 million rows, that's typically 3-4 page reads vs. a full sequential scan of ~100,000 pages.

πŸ” Interactive B-Tree

Insert keys and watch the tree grow. Click a node to see its page contents.

Insert keys to build the tree. Order (max keys per node): 4
Keys: 0 Height: 0 Nodes: 0 Page reads for lookup: 0

πŸ“– Scan Types

How PostgreSQL uses the B-Tree for different query patterns.

🎯

Index Scan

Traverse B-Tree β†’ find leaf β†’ follow TID to heap page β†’ return row. Best for selective queries (<5% of rows).

B-Tree β†’ Leaf β†’ Heap β†’ Row
WHERE id = 42
⚑

Index-Only Scan

All needed columns are in the index (covering index). Skips heap entirely if visibility map says page is all-visible.

B-Tree β†’ Leaf β†’ Skip Heap! β†’ Done
SELECT id FROM t WHERE id > 100
πŸ—ΊοΈ

Bitmap Index Scan

Build bitmap of matching heap pages β†’ sort by page β†’ fetch pages sequentially. Best for medium selectivity (5-25%).

B-Tree β†’ Bitmap β†’ Sort β†’ Sequential I/O
WHERE age BETWEEN 20 AND 30

βœ‚οΈ Page Splits

When a leaf page is full, it splits. Watch how keys redistribute.

Before (full page)