3 ms·

This data structure sounds as mythical as a unicorn. Are there any peer-reviewed publications about this data structure or is it a trade secret? The name seems

• esmet 13y ago
  "Fractal Tree" is indeed a marketing trademark. But the algorithms used are not necessarily secret. The implementation is similar to the cache oblivious streaming btree: http://supertech.csail.mit.edu/papers/sbtree.pdf‎ http://supertech.csail.mit.edu/papers/sbtree.pdf‎ Of course what's not described in the paper include: transactions, mvcc, logging/recovery, parallelism, etc. Those are really interesting topics as well.
• leif 13y ago
  The name is a marketing term, you're right. The structure is somewhere in the realm of buffer trees, LSM-trees, $B^\epsilon$ trees, and COLAs. It's hard to give it an academic name precisely because the implementation takes hints from many places, but we hope to publish more soon. B-trees are on the optimal tradeoff curve but there are many other points on that curve, and B-trees heavily favor reads so there's plenty of room to win on the write side. I have a couple of blogs about this actually: http://www.tokutek.com/2011/09/write-optimization-myths-comparison-clarifications/ http://www.tokutek.com/2011/09/write-optimization-myths-comp... http://www.tokutek.com/2011/10/write-optimization-myths-comparison-clarifications-part-2/ http://www.tokutek.com/2011/10/write-optimization-myths-comp...