3 ms·
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
by jdefarge 9y ago
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/paper.pdf 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 https://www.percona.com/doc/percona-tokudb/ft-index.html
- kdkeyser 9y agoI 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.