A Deep Dive on On-Disk Data Structures, B-Trees, LSM-Trees and Fractal Trees

After a long reign as the dominant on-disk data structure for databases and filesystems, B-trees are slowly being replaced by write-optimized data structures, to handle ever-growing volumes of data. Some write optimization techniques, like LSM-trees, give up some of the query performance of B-trees in order to achieve this.

A Fractal Tree is a write-optimized data structure that matches the insertion performance of an LSM-tree while maintaining the optimal query performance of a B-tree. It's inspired by many data structures (Buffered Repository Trees, B^ε trees, ...) but the real definition is just what we've implemented at Tokutek.

I'll provide background on B-trees and LSM-trees, an overview of how Fractal Trees work, where they differ from B-trees and LSM-trees, and how we use their performance advantages in some obvious and some surprising ways to power new MySQL and MongoDB features in TokuDB and TokuMX.