Dissecting the Humble LSM Tree and SSTable
summary
Practical walkthrough of an LSM implementation shows a Python memtable that flushes at 5 items into immutable SSTable files, uses commit logs for durability, encodes deletions as tombstones with timestamps (last-timestamp wins), and reads by merging file results; the demo uses a naive line‑by‑line scan (no binary search) so it’s slow but illustrative. Real systems load Bloom filters in RAM to avoid disk hits and run background compaction (size‑tiered, leveled or time-window compaction) to drop obsolete versions; SQLite4 is a production C option.
AI-written summary · about
chapters (11)
- 0:00Introduction
- 6:22Data Structures
- 8:10Hard Drives
- 11:16SSD
- 15:44Data Structure
- 16:46Python Implementation
- 24:11Database Implementation
- 27:33Bloom Filters
- 30:57Compaction
- 34:23Compaction Strategies
- 36:43Summary
related talks
04h 05mHands-on workshop going from zero to a working LSM Tree
18mPreview: KV-Stores and Databases
45mThe Database: A Sophisticated and Special Data Structure
34mWhat We Talk About When We Talk About Disk IO
39mAn Introduction to B-trees and LSM-trees for DEVs and DevOps
13mClosing the B+-tree vs. LSM-tree Write Amplification Gap on Modern Storage Hardware...
40mInsights into Your Cloud Database: How Storage Engines Actually Work
29mSLM-DB: Single-Level Key-Value Store with Persistent Memory