Module 2 · Indexes

Episode 10 B+ Trees: Search and Insert

9 min · SQL · Postgres

Title card of Episode 10: B+ Trees: Search and Insert

▶ This video is coming to YouTube soon.

How does Postgres find one row out of 10,000 by reading just 3 pages? This episode builds a B+ tree from nothing, splits its leaves, grows a new root, and then checks every claim against a real Postgres index with pageinspect.

Chapters

  1. 0:00Intro
  2. 0:14Three pages out of 84
  3. 0:35Why not just keep the file sorted?
  4. 1:35The B+ tree in five rules
  5. 2:16Search: one page per level
  6. 3:14Insert: fill, overflow, split
  7. 4:18When the split reaches the root
  8. 5:08Why the tree stays short
  9. 5:35The code: insert
  10. 6:05The code: the split climbs
  11. 6:39Proof: a real B+ tree in Postgres
  12. 7:39Trade-offs
  13. 8:09Recap
  14. 8:39Next: B+ Tree: Delete