An Introduction to B-trees and LSM-trees for DEVs and DevOps
summary
Benchmarks use PGbench comparisons between vanilla Postgres and Postgres-compatible LSM engines (PG Rocks, Cockroach, Yugabyte) at scale factors up to millions of rows, showing B-tree primary lookups stay at ~4 disk reads until an extra index level appears (~5 reads at ~5.1M rows). LSM engines deliver much higher ingest but suffer write-optimized, read-amplified behavior: bloom-filter false positives, no cheap range scans, heavy compaction that makes truncate is expensive and background updates or long transactions collapse throughput.
AI-written summary · about
chapters (22)
- 0:00Introduction and speaker intro
- 0:47Traditional vs ordered storage
- 3:57Binary trees to B-trees
- 8:14B+ trees and range scans
- 8:35LSM trees overview
- 10:23LSM tree structure and writes
- 11:52LSM trees in distributed systems
- 13:18Reading data in LSM trees
- 15:50Historical context and old vs new
- 16:55Google and NoSQL evolution
- 17:59Postgres-compatible LSM solutions
- 18:41Apache Flink and update strategies
- 19:23Synchronous replication pain points
- 20:28Dev and DevOps training approach
- 21:10Postgres topologies at Adion
- 23:16Surprising LSM tree behaviors
- 25:44Postgres compatibility challenges
- 26:05Monitoring and observability issues
- 27:07Compaction and vacuum comparison
- 27:49Workload suitability and tests
- 28:09Resources and further reading
- 29:34Q&A session
related talks
45mThe Database: A Sophisticated and Special Data Structure
13mClosing the B+-tree vs. LSM-tree Write Amplification Gap on Modern Storage Hardware...
27mDropping Into B-Trees
52mHow shit works: Databases
18mPreview: KV-Stores and Databases
35mQuestioning Database Claims: Design Patterns of Storage Engine
01h 16mDeep Dive into On-Disk Data Structures
34mWhat We Talk About When We Talk About Disk IO