Module 2 · Indexes

Episode 13 Concurrent B+ Trees

10 min · SQL · Postgres

Title card of Episode 13: Concurrent B+ Trees

▶ This video is coming to YouTube soon.

How do hundreds of queries share one B+ tree without corrupting it or missing keys? Locks vs latches, the race that loses a key, latch crabbing, optimistic descent, and Lehman and Yao's B-link tree, then proof from Postgres's own pages: high keys, right-links, and locks that never touch a page.

Chapters

  1. 0:00Intro
  2. 0:16A key that's there, not found
  3. 0:34Locks are not latches
  4. 1:13The race: a split under a reader
  5. 2:00Latch crabbing: readers
  6. 2:48Writers: hold until it's safe
  7. 3:49Optimistic: bet on no split
  8. 4:43The code: crabbing an insert
  9. 5:11B-link trees: move right
  10. 6:25The code: move right
  11. 6:51Proof: Postgres pages carry high keys
  12. 7:58Proof: locks last, latches don't
  13. 8:52Trade-offs
  14. 9:21Recap
  15. 9:50Next: Hash Indexes