Hacker News Reader

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 pretty vacuous/hype-laden since any well-balanced tree is fractal.

View on HN

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-comp... http://www.tokutek.com/2011/10/write-optimization-myths-comp...

"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‎

Of course what's not described in the paper include: transactions, mvcc, logging/recovery, parallelism, etc. Those are really interesting topics as well.

Reply on news.ycombinator.com