Module 2 · Indexes

Episode 12 B+ Trees in Practice

10 min · SQL · Postgres

Title card of Episode 12: B+ Trees in Practice

▶ This video is coming to YouTube soon.

What do real B+ trees do that the textbook one doesn't? Heap tables vs clustered tables, covering indexes and the visibility map (Heap Fetches 0), composite keys, suffix truncation, deduplication (292 pages down to 87), and bulk loading vs random inserts, all proved on a real Postgres.

Chapters

  1. 0:00Intro
  2. 0:16Same keys, a third of the pages
  3. 0:37Where the rows live
  4. 1:54Proof: an index entry is an address
  5. 2:21Covering indexes and the visibility map
  6. 3:46Proof: Heap Fetches
  7. 4:24Composite keys, shorter separators
  8. 5:25Deduplication: one key, many rows
  9. 5:59Proof: truncation and deduplication
  10. 6:40Bulk loading vs random inserts
  11. 7:39Proof: the same keys, two densities
  12. 8:14The toolbox
  13. 9:03Recap
  14. 9:30Next: Concurrent B+ Trees