COMPUTATION RESEARCH in BOSTON and BEYOND (CRiBB)

DateNov. 4, 2011
Speaker Bradley C. Kuszmaul (Massachusetts Institute of Technology)
TopicHow Fractal Trees Work
Abstract: Most storage systems employ B-trees to achieve a good tradeoff between the ability to update data quickly and to search it quickly. It turns out that B-trees are far from the optimimum in this tradeoff space. I'll talk about Fractal Tree indexes, which were developed in a collaboration between MIT, Stony Brook, and Rutgers. I'll talk about how they work, and what their performance bounds are. My startup, Tokutek, is commercializing fractal tree indexes as part of a MySQL storage engine.



back