On-Disk Data Structures: B-Trees, LSM-Trees and Fractal Trees
summary
The talk explains disk-based data structures used in databases and file systems, contrasting traditional B-trees with write-optimized structures like LSM-trees that trade some read performance for faster writes. It presents the fractal tree (as implemented by Tokutek) as a write-optimized index that preserves near-B-tree query performance while delivering much faster insertions, and notes its roots in buffer trees and B^ε-trees.
AI-written summary · about
related talks
45mThe Database: A Sophisticated and Special Data Structure
13mClosing the B+-tree vs. LSM-tree Write Amplification Gap on Modern Storage Hardware...
52mHow shit works: Databases
34mWhat We Talk About When We Talk About Disk IO
01h 16mHow do to do research with Systems Researchers
39mAn Introduction to B-trees and LSM-trees for DEVs and DevOps
38mModern B-Tree techniques
42mTokuDB internals