Publications Related to Fractal Tree Indexing

Posted On May 22, 2009 | By Bradley C. Kuszmaul | 5 comments

The TokuDB storage engine for MySQL employs Fractal Tree technology. We’ve been planning to write a white paper explaining how fractal tree indexing works, but haven’t gotten to it yet. In the mean time, here are links to some academic papers that relate to our technology.

  • Cache-Oblivious B-Trees by Michael A. Bender, Erik D. Demaine and Martin Farach-Colton in SICOMP 35:2, pp. 341-358, 2005. An early version of this paper appeared in FOCS in 2000.
  • The Cost of Cache-Oblivious Searching by Michael A. Bender, Gerth Stlting Brodal, Rolf Fagerberg, Dongdong Ge, Simai He, Haodong Hu, John Iacono, and Alejandro López-Ortiz in FOCS 2003 p. 271.
  • A Locality-Preserving Cache-Oblivious Dictionary by Michael A. Bender, Ziyang Duan, John Iacono, and Jing Wu in Journal of Algorithms 53:2 pp. 115-136, November 2004.
  • An Adaptive Packed-Memory Array by Michael A. Bender and Haodong Hu, in TODS 32:4, November 2007.
  • Cache-Oblivious Streaming B-trees by Michael A. Bender, Martin Farach-Colton, Jeremy T. Fineman, Yonatan Fogel, Bradley Kuszmaul, and Jelani Nelson, in the Proceedings of the Nineteenth ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), June 9–11, 2007, San Diego, California, pp. 81-92
  • Concurrent Cache-Oblivious B-Trees by Michael A. Bender, Jeremy T. Fineman, Seth Gilbert, and Bradley C. Kuszmaul, in the Proceedings of the Seventeenth ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), July 17–20, 2005, Las Vegas, Nevada, pp. 228-237.
  • Cache-Oblivious String B-Trees by Michael A. Bender, Martin Farach-Colton, and Bradley C. Kuszmaul, in the Proceedings of the Twenty-Fifth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, June, 2006, Chicago, IL, pp. 223–242
  • Cache-Oblivious Dynamic Search Trees by Zardosht Kasheff, Master’s Thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, June, 2004.
  • Cache-Oblivious Algorithms by Harald Prokop, Master’s Thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, June, 1999.

The research groups’ web pages can be found at

Incidentally, there’s another data structure in the literature called a `Fractal Tree’ (see e.g. http://www.pdl.cmu.edu/ftp/Database/fpbtree.ps), which is unrelated to our work.

5 thoughts

  1. Robert Collins says:

    The link for Cache-Oblivious Dynamic Search Trees points to prokop99.pdf; any chance you could update it to the real paper?

  2. Robert Collins says:

    The cache-oblivious string b-trees link is also broken.

  3. Several of the links are broken or misdirected, any chance anyone is paying attention here and can fix these?

  4. Sorry for the broken links – we’ll be fixing them shortly and post another comment when it’s done.

  5. The links should all work now.

Leave a Reply

Your email address will not be published. Required fields are marked *