TokuDB's Index Structure: Fractal Tree Implementation
This article analyzes TokuDB’s index structure—the fractal tree—from an engineering implementation perspective. It describes the on-disk storage layout of ft-index in detail, how ft-index implements point queries, range queries, and insert/delete/update operations, and throughout the discussion attempts a detailed comparison with InnoDB’s B+ tree from multiple angles. Introduction to the Fractal Tree The fractal tree is a write-optimized on-disk index data structure. In general, fractal trees offer good write performance (insert/update/delete) while still providing read performance close to that of a B+ tree....