Thanks for acknowledging the problem with the graph. We'll have to disagree over "correct in spirit" versus "stupid." I suggested building a LSM out of cache-o

Thanks for acknowledging the problem with the graph. We'll have to disagree over "correct in spirit" versus "stupid." I suggested building a LSM out of cache-oblivious b-trees because of the claim that they were better than b-trees in all cases, including (ostensibly) read performance. I didn't realize that it was another name for fractal trees. (It's been a while since I read the fractal tree papers.) I'm not convinced that LSM-trees are suboptimal. The lower levels have shorter trees, so the price of redundant lookups is small, and you should get better write performance because you can do compaction without touching other levels. Conversely, SQLite4 has designed an LSM-tree with forward pointers between the levels. However I think that actually sacrifices some write performance for read performance, which probably makes it closer to a fractal tree. (SQLite4 is also vaporware, unfortunately.) I don't think there is a free lunch here. If you want to claim theoretically better read performance, you have to admit theoretically worse write performance. Tricks like compression or bloom filters (for LSM-trees) help in practice but don't change the theory.