I've been staring to write a paper on bcache/bcachefs's b-tree design, which is also a sort of combination b-tree/trie (it uses binary trees in eytzinger layout). Pretty cool to see the same idea coming up in multiple places.<p>Running index-microbenchmarks now to see which is faster :)
Masstree is one of the DBs Berkeley used when comparing the performance of Anna [1] (now Fluent [2]):<p>[1] <a href="https://rise.cs.berkeley.edu/blog/anna-kvs/" rel="nofollow">https://rise.cs.berkeley.edu/blog/anna-kvs/</a><p>[2] <a href="https://github.com/fluent-project/fluent" rel="nofollow">https://github.com/fluent-project/fluent</a>
So what are the advantages over adaptive radix trees or good old judy-dict/array?<p>Apart from judy being too damn complicated, and too old to be optimized for vector-compare instructions (I think the fancy hand-coded x86 vector-comparisons are the main reason for ART being competitive with judy, considering that it misses at least key compression and the clever allocator, and that ART is not as optimized for using every byte out of every fetched cache-line).
Author here - if you like this you might also like another paper summary of mine in the same vein:<p><a href="https://news.ycombinator.com/item?id=18132730" rel="nofollow">https://news.ycombinator.com/item?id=18132730</a>
Why do I get a gross yellow block covering the image when I mouse over it?<p>edit: oh, it's because it's a link and they have some background coloring or something on links.