Deep Dive on On-Disk Data Structures, B-Trees, LSM-Trees and Fractal Trees
Details
BigDataDC is excited to host Leif Walsh (@leifwalsh) at AddThis' headquarters to discuss on-disk data structures and how the reign of B-Trees as the dominant on-disk data structure is nearing an end.
The agenda will be:
6:30-7:00: meet, greet, & eat 7:00-7:15: welcome, announcements, & introductions
7:15-8:45: presentation sessions
8:45-9:15: networking, etc.
Abstract:
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.
Bio:
Leif Walsh (@leifwalsh) is a professional cat wrangler. In his free time, he works at Tokutek on Fractal Tree indexing algorithms and implementation, and building stronger distributed systems algorithms into TokuMX, the high performance distribution of MongoDB.