COMPUTATIONAL RESEARCH in BOSTON and BEYOND (CRIBB)

Date Nov. 4, 2011
Speaker Bradley C. Kuszmaul (Massachusetts Institute of Technology)
Topic How 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.

Archives

Acknowledgements

We thank the generous support of MIT IS&T, CSAIL, and the Department of Mathematics for their support of this series.

MIT Math CSAIL EAPS Lincoln Lab Harvard Astronomy

Accessibility