The Database: A Sophisticated and Special Data Structure
summary
Compares B-tree–based databases (SQLite, Postgres, Oracle) and LSM-tree systems (Cassandra, RocksDB, LevelDB): B-trees map nodes to disk pages so range scans read whole pages and searches remain O(log N) with balanced, splitable nodes, while LSM trees buffer writes in memory, flush to SSTables and run compactions so writes are amortized near-constant but reads require multi-level lookups and pay compaction costs. Discusses tunable parameters (fillfactor/PCTFREE, compaction interval, SSTable size) and describes building a file manager and image cache on B-trees that achieves good local-disk performance.
AI-written summary · about
chapters (10)
- 0:00Database introduction
- 1:25Internal database operation
- 2:31Key data structures: B-Tree and LSM-Tree
- 14:47B-Tree discovery and performance
- 25:05B-Tree disk storage
- 34:13LSM-Tree introduction and advantages
- 36:48LSM-Tree compaction process
- 41:31B-Tree vs LSM-Tree comparison
- 42:57Advanced applications and optimizations
- 44:02Conclusion
related talks
01h 16mOn-Disk Data Structures: B-Trees, LSM-Trees and Fractal Trees
52mHow shit works: Databases
01h 16mDeep Dive into On-Disk Data Structures
39mAn Introduction to B-trees and LSM-trees for DEVs and DevOps
34mWhat We Talk About When We Talk About Disk IO
13mClosing the B+-tree vs. LSM-tree Write Amplification Gap on Modern Storage Hardware...
01h 16mHow do to do research with Systems Researchers
27mDropping Into B-Trees