[jdefarge]

You are absolutely right. Just an addendum: there are modern B-Trees that are optimised to leverage the cache lines, part of the so called cache oblivious data structures ( http://erikdemaine.org/papers/CacheObliviousBTrees_SICOMP/pa... ). A cache oblivious B-Tree is the basis of Percona's TokuDB storage engine: https://www.percona.com/doc/percona-tokudb/ft-index.html

[kdkeyser]

I believe TokuDB is using a flavor of B epsilon trees, i.e. a B tree with, per node, an associated staging area for writes to that node or its child nodes. Keeps inserts localised at the top of the tree, until the staging areas fill up. Then these staged inserts are propagated in batches down the tree.

In my opinion, a nice middle ground between the B tree and LSM approaches.