Module 2 · Indexes

Episode 15 LSM Trees

9 min · SQL · Postgres

Title card of Episode 15: LSM Trees

▶ This video is coming to YouTube soon.

Why do RocksDB, Cassandra and LevelDB never update a page in place? This episode animates an LSM tree with a 4-entry memtable: the WAL, flushes to immutable SSTables, reads from newest to oldest and deletes as tombstones, then finds the same trick inside Postgres's GIN index: a pending list of 1,000 rows merged in bulk.

Chapters

  1. 0:00Intro
  2. 0:13Never write in place
  3. 0:36In place, every write is a random write
  4. 1:18Writes: log it, sort it in memory, flush it
  5. 2:44Reads: memtable first, then newest to oldest
  6. 3:46Deletes are writes: tombstones
  7. 4:37The LSM tree in six rules
  8. 5:21The code: put, delete, get
  9. 5:51The code: flush
  10. 6:19Proof: the same trick inside Postgres
  11. 7:47Same idea, not an LSM tree
  12. 8:14Trade-offs
  13. 8:53Recap
  14. 9:18Next: Compaction