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 MIT Department of Mathematics, Student Chapter of SIAM, ORCD, and LLSC for their generous support of this series.

MIT Math CSAIL EAPS Lincoln Lab Harvard Astronomy

Accessibility