Looking at that post on Leif's drawing, I think I agree that the B-tree is placed incorrectly. It turns out that B-trees are on the optimal read/write tradeoff curve, but they are in a very bad corner.

B-trees cost O(log_B N) to read or write.

Fractal trees cost O(log_B N) to read, and O((log_B N)/sqrt(N)) to write (for the case where epsilon=2).

The hidden constants inside the big-Oh are small; they seem to be less than 2 in practice. In fact, in the benchmarks that I've seen, the constants are in favor of the fractal tree. I suspect that this is because the block size in practical B-trees is too small, so the seek time is large compared to the transfer time on magnetic disk. Furthermore small block sizes hurt compression, small block sizes make the tree deeper. Furthermore, dynamic B-trees (ones that can be written) typically fill their blocks only about 3/4 full on average, making the effective block size even smaller. In most dynamic B-trees, the block size is 4KB or 16KB. In a few it's 32KB or even 64KB. For read-only databases I've seen people use 1MB blocks for B-trees. In the fractal tree, the effective block size is 4MB, and I suspect that's where we're winning on the constants.

So for a constant slowdown in read performance (a quite small constant slowdown, or possibly a small speedup) you can get dramatic speedups on write performance.

LSM trees are not on the optimal tradeoff curve. They suffer worse read perforamance that B-trees or Fractal trees, and their write performance is theoretically comparable to that of fractal trees.

So there's an error in that drawing, but the drawing is conceptual anyway, since there's no scale. The point of the drawing is that fractal trees dominate LSM trees, and for about the same cost as a B-tree on reads, you can get much better write performance. So the drawing is correct in spirit.

It makes no sense to build an LSM tree out of fractal trees. The resulting data structure would still be slower than a fractal tree. It's also unlikely to be faster than a B-tree-based LSM, since the B-trees used in LSM trees are static, not dynamic. You never have to insert into one of those B-trees, which means you can apply a bunch of tricks, such as using huge blocks. That probably shifts the constant inside the big-Oh back in favor of the B-tree for read operations, which are the only B-tree operations inside an LSM.

I don't think Tokutek is conflating the theoretical performance with the practical performance. Both the theoretical and practical performance appear to be better than the alternatives. In practice fractal trees appear to be slightly faster than B-trees at reads (assuming that the B-tree is actually a writeable data structure) in real workloads, and much faster at writes. In theory, the asymptotic read performance is the same, and the asymptotic write performance is much better for Fractal Trees.

It's true that the LSM implementations could all be bad, leading to the wrong conclusion when doing benchmarking. I'd find that surprising because the fractal tree seems to be better than any of the many LSM implementations in practice, and I'd hope that at least one of them would get it right. And the practical performance matches what the theory says it should, so it's not surprising that the fractal trees are faster.

I'm not sure why you object to comparing the data structures. We can compare them both theoretically using big-Oh notation. We can also do an analysis for specific database sizes and memory sizes of how the data structures compare, assuming a good implementation. That's what my paper tried to do. We could also compare the implementations, which my paper didn't do, but which others have done. For example, Tim Callaghan has done a lot of benchmarking which seems to be done right.