That is good but not quite "beat B-trees pretty handily across the board" :-)
Let me be clear: in the worst case with a unique index, Fractal Tree indexes are the same speed as B-tree indexes. In most cases, they're far better. When you add in compression and agility, it really is "beat B-trees across the board."
[Random aside: I greatly dislike block (i.e. InnoDB-style) compression, which is what Tokutek seems to use. Decompressing the entire block just to retrieve one column of one row is crazily expensive, especially as the decompression cost goes up as the block size goes up. There is also the problem of deciding whether to store compressed blocks in the buffer cache (slow), decompressed blocks in the buffer cache (wastes ram) or to have a cache of uncompressed blocks (the InnoDB approach, which kind of combines both problems). I think that format-aware page or column compression (like Oracle, SQL Server or ESENT) is far more effective.]
I guess that this has gotten way off topic but I am glad there are people out there doing exciting new things in the B-tree space. I will keep a closer eye on Tokutek in the future.
Our compression technique is naive, you're right (but we don't decompress the whole 4MB for one single point query, as you may be thinking, we're a bit more sophisticated). We have some more ideas in the pipeline if we need them (basically a bunch of tricks you can play when you know the schema), but the fact remains that what we have right now is extremely effective and there isn't much incentive yet to finish off our smarter prototypes.
Yes, unique checks are bad. They make it perform as badly as a B-tree for unique inserts. There are sometimes ways around that but at some level if you aren't reading in the leaf node, you're going to be at a loss for some information. B-trees seem to have spoiled users into thinking uniqueness checks don't make inserts any more expensive, when in fact that's just because B-tree inserts are already that slow.