Add support for fractal tress (or fractional cascading) to speedup JDBM even further
romix opened this issue · 3 comments
Hi,
Recently Tokutek produced a MySQL backend using "fractal trees" instead of the usual B+-trees. They report much better insert performance (one or two orders of magnitude) and big improvements for search times.
The algorithms are based on "Cache Oblivious B-trees", which seem to use the fractional cascading approach. fractional cascading is extending the usual B+-tree algorithms with forward links from level (n) to level (n+1), which makes searches much faster. I haven't found any open-source implementation of these algorithms yet, but judging from the papers, it shouldn't be too hard.
It would be cool to integrate such a technology into JDBM as well, as it may bring great speed benefits.
Some related links:
http://en.wikipedia.org/wiki/TokuDB (what is TokuDB and fractal tree algorithms behind it)
http://en.wikipedia.org/wiki/Fractional_cascading (this is the idea behind fractal trees)
Currently my main priority is to make JDBM3 rock solid.
But I will put this into 'nice to have' list for future improvements.
Sure! I absolutely second your approach.
This feature was meant as a mid-term improvement, not as something for the next release.
After all, it may turn out as a major change and would require a lot of work and testing.
Closing, as it is not going to be implemented.