Module 2 · Indexes

Episode 11 B+ Trees: Delete

10 min · SQL · Postgres

Title card of Episode 11: B+ Trees: Delete

▶ This video is coming to YouTube soon.

How does a B+ tree delete a key and stay balanced? This episode borrows keys between pages, merges them, cascades a merge up to the root and shrinks the tree, then shows on a real Postgres index that deleting 90% of the keys leaves all 276 pages in place, frees only empty pages, and needs REINDEX to compact.

Chapters

  1. 0:00Intro
  2. 0:14Delete 90%, keep every page
  3. 0:32Just take the key out?
  4. 1:24The textbook delete
  5. 1:56Underflow: borrow from a sibling
  6. 3:00No key to spare: merge
  7. 3:45Merges climb, the root shrinks
  8. 5:01The code: delete
  9. 5:38Postgres: free at empty
  10. 6:42Proof: deletes leave pages sparse
  11. 7:34Proof: only empty pages are freed
  12. 8:29Why Postgres doesn't merge
  13. 8:53Trade-offs
  14. 9:22Recap
  15. 9:49Next: B+ Trees in Practice