Tokutek's company blog on its fractal tree indexes and the TokuDB and TokuMX storage engines for MySQL and MongoDB.
HN links it for TokuMX and fractal tree write performance claims; commenters who used TokuMX report roughly 2x faster response times and recommend it.
Although it is true that MongoDB uses a lot of disk compared to your average RDMS there are reasons for that.
1) MongoDB (and various other NoSQL solution) are schemaless and thus have to store document fields along with the values for each document. This alone usually results in roughly twice as much actual disk space being used compared to an RDBMS.
2) MongoDB preallocates fairly large chunks of disk for their mmap based storage (2Gb per database files by default). This means there will be up to 2Gb * N where N is the number of logical databases in "wasted" (more accurately, unused) space. This can be addressed somewhat through the --smallfiles option.
3) The biggest issue that I actually consider an design flaw is the ineffective reuse of disk space previously occupied by deleted or, more commonly, moved documents. MongoDB reserves a bit of padding for each document but since a lot of documents can grow over time these documents will be moved around on disk leaving holes in the data files. These holes are not adequately re-used and a compaction is required to make that space available again. Compaction is NOT a background process at the moment and blocks writes. The "usePowerOf2Sizes" option will help with this issue at the expense of always using a power of 2 size in bytes per document.
The above are factual reasons why MongoDB uses a lot of disk space. It's certainly a relatively young database and some issues do need to be addressed but this whole polarizing "it's…
I read the presentation here: http://tokutek.com/downloads/mysqluc-2010-fractal-trees.pdf
The math looks a bit hand-wavy to me but I get the basic data structure, you basically have sorted arrays whose lengths are each a power of two, so 1, 2, 4, 8, etc...
When you insert a set of values, you can either fill an entire array or leave it empty. So for example if you have 5 values, you'd have an array of 1 element, an empty array with 2 spaces and a full array of 4 elements.
Each array is sorted by itself but the smaller arrays do not necessarily contain all values that are lesser than all values of bigger arrays.
To do an efficient lookup you have forward pointers from each node to the next-bigger node in the next array, so you can basically start your binary search at a given index in a bigger array and move faster.
The problem is when you are inserting lots of values because you have to merge arrays multiple times and overwrite a bunch of data, but the point is that you are getting better disk IO doing that than rebalancing a B-Tree because you're not making the disk head skip around all the time, thus achieving greater speed.
I'm curious about the details of this benchmark though, what kind of values are we talking about? Are they all the same size rows or do you have variable sized values (like strings?) in the benchmark?
This looks promising but I'd love more explanations from the authors...
Why do you care about the high demand? We can put that aside for now--if you are a competent coder, you are in high demand...
If you want to have more math, then some subfield in CS theory is the way to go.
CS theory have lot of elegant math. complexity, data structure, algorithms, combinatorial optimization, computational geometry. All of them have nice set of mathematical tools you can use. There are also unexpected ones that uses more traditional mathematics, like universal algebra for CSP, functional analysis in graph embedding with little distortion, and topology for computational topology(well that seems obvious, there are certain uses for computational topology, read up on persistent topology, which I guess is part of machine learning now).
Of course, the demands are low for pure theory students. However you can do some practical work. For example http://www.tokutek.com/ , founded by professors who specialize in cache oblivious data structures. Some more practical ones include cache oblivious data structures, sublinear time algorithms, string related algorithms. In Google, there are researchers working on how to optimize ads.
Also, I just don't see how you are going to write non-boilerplate code anywhere. everything eventually become repetitive(unless you use Haskell, anything new become a paper.)
Lexington, MA - Tokutek (http://www.tokutek.com/)
Full-time testing/QA engineer. Use whatever you like to break our software in interesting ways. We want someone who can build out and own testing for the long term. MySQL and/or MongoDB experience would be great. C/C++ even better but definitely not necessary.
You'll be responsible for designing and implementing new test infrastructure for both correctness and performance, you'll be in direct contact with our VP of Engineering, Tim Callaghan, as well as most of us engineers.
We're a highly technical storage systems company, with two flagship products that share a highly-tuned core: TokuDB, a storage engine for MySQL, and TokuMX, a fork of MongoDB. We currently have 6 core engineers, plus Tim.
Email us at {leif,tim} at tokutek dot com.
Tell your friends!
...tell me how to make something just like a b-tree, but faster
If you wanted to do that on modern multilayer-memory architecture, you would use a "cache-obvious" structure like cache-oblivious b-tree, cache-oblivious Lookahead Array and similar structures. Because these kinds of structures allow large and small scale locality of data, meaning that a disk-read will pull several pieces of data at once, a jump between nodes produces fewer cache misses (at each level) and so-forth.
Michael A. Bender wrote of the original papers on cache oblivious structures and not coincidentally is TokuTek founder.
http://www.tokutek.com/company/team/
http://en.wikipedia.org/wiki/Cache-oblivious_algorithm
http://supertech.csail.mit.edu/cacheObliviousBTree.html
Fractal trees are not "LSM-trees, but better." Fractal trees are more read-optimized, whereas LSM-trees are more write-optimized.
A fully compacted LSM-tree should be equivalent to a b-tree in terms of read performance. However I don't think any existing implementations are anywhere near that.
I appreciate TokuTek's work in this area but their marketing should be taken with a grain of salt. They've published some stupid stuff before (look at the graph here[1] and tell me how to make something just like a b-tree, but faster).
[1] http://www.tokutek.com/2011/10/write-optimization-myths-comparison-clarifications-part-2/