Tokutek

®Fractal Tree Technology Overview The Art of Indexing Martín Farach-Colton Co-founder & Chief Technology Officer Not all indexing is the same B-tree is the basis for almost all DB systems • Data structure invented in 1972 • Has not kept up with hardware trends Works poorly on modern rotational disks‣ Works poorly on SSD‣ Fractal Tree Indexes is the basis of TokuDB • Scales with hardware • Fast Indexing ➔ More Indexing ➔ Faster Queries • Great Compression • No Fragmentation • Reduced wear on SSDs The Art of Indexing ® How do Fractal Tree Indexes outperform B-trees? How do Fractal Tree Indexes outperform B-trees? First, some facts about storage systems Storage is quirky Hard disks are slow for random I/O but fast for sequential I/O Difference causes problems like fragmentation, ... The Art of Indexing ® Storage is quirky Hard disks are slow for random I/O but fast for sequential I/O SSDs are fast for Difference causes problems random I/O but expensive for like fragmentation, ... sequential. Garbage collection causes artefacts: increased wear, write cliffs...