Module 2 · Indexes

Episode 14 Hash Indexes

10 min · SQL · Postgres

Title card of Episode 14: Hash Indexes

▶ This video is coming to YouTube soon.

How does a hash index find a row in 2 page reads, and how does it grow without rehashing everything? This episode animates static, extendible and linear hashing, then reads a real Postgres hash index's metapage with pageinspect as it splits one bucket at a time, and shows why BETWEEN can't use it.

Chapters

  1. 0:00Intro
  2. 0:15Compute the page, don't search for it
  3. 0:38Static hashing: fast until the chains grow
  4. 1:57Extendible hashing: double the directory, not the data
  5. 3:34Linear hashing: split in order, not where it's full
  6. 5:24The code: which bucket?
  7. 5:52The code: split the next bucket
  8. 6:21Proof: Postgres splits one bucket at a time
  9. 7:18Proof: = uses the hash, BETWEEN can't
  10. 8:12Postgres's hash index, precisely
  11. 8:46Trade-offs
  12. 9:18Recap
  13. 9:47Next: LSM Trees