Author here - if you like this you might also like another paper summary of mine in the same vein:
Masstree: A cache-friendly mashup of tries and B-trees
11–20 of 24 posts
Re: Masstree: A cache-friendly mashup of tries and B-trees
#12Author here - if you like this you might also like another paper summary of mine in the same vein: https://news.ycombinator.com/item?id=18132730
So I was wondering... are there sensible structures that combine hashmap and tree by having a double index?
Reason: Ordered access or range queries need a (radix-)tree.
So insertion and removal need to pay for the comparatively slow tree search and rebalancing.
Lookups or mutations could use a hash table that references the same data, especially if no key compression is used for storage.
Re: Masstree: A cache-friendly mashup of tries and B-trees
#13Author here - if you like this you might also like another paper summary of mine in the same vein: https://news.ycombinator.com/item?id=18132730
So I was wondering... are there sensible structures that combine hashmap and tree by having a double index? Reason: Ordered access or range queries need a (radix-)tree. So insertion and removal need to pay for the comparatively slow tree search and rebalancing. Lookups or mutations could use a hash table that references the same data, especially if no key compression is used for storage.
I don't know of one, but it's such a natural idea that I'd guess it's been studied. There are standard implementations of LRU caches that use e.g. a hash map and a linked list to get both fast lookup and ordering, but for real performance I think you'd want to try and minimise the number of data structures to avoid having competing cache behaviours.
Re: Masstree: A cache-friendly mashup of tries and B-trees
#14Earlier quoted context omitted.
Here's a recent comparison of Masstree to ART: https://twitter.com/andy_pavlo/status/986647389820747776?s=2... ART looks to be better in most cases. It's on my list of K-V stores to review: https://www.the-paper-trail.org/page/reading-list/
Cool, looking forward. Please put Judy in as well :) Seriously, the 17 year old judy is still pretty good, despite it's lack of use of cool vector load / compare / etc instructions for quickly traversing tree nodes that are too small for a full radix search (ART does "simultaneous search", i.e. compares to all stored keys in a single instruction, while judy afaik runs a linear search). It would be pretty cool if some…
I could either figure out how Judy works, or review another three papers :)
Re: Masstree: A cache-friendly mashup of tries and B-trees
#15Masstree is one of the DBs Berkeley used when comparing the performance of Anna [1] (now Fluent [2]): [1] https://rise.cs.berkeley.edu/blog/anna-kvs/ [2] https://github.com/fluent-project/fluent
Yeah, Masstree has settled into the standard set of comparator systems for most research since it was published - and not as a strawman "this system was crap, so let's pretend we've done good work by beating it!" but as a real challenge to do better than.
Anna is on my list of systems to include in this review (see https://www.the-paper-trail.org/reading-list/). Looking forward to it!
Re: Masstree: A cache-friendly mashup of tries and B-trees
#16Why do I get a gross yellow block covering the image when I mouse over it?
edit: oh, it's because it's a link and they have some background coloring or something on links.
Re: Masstree: A cache-friendly mashup of tries and B-trees
#17Why do I get a gross yellow block covering the image when I mouse over it? edit: oh, it's because it's a link and they have some background coloring or something on links.
Oh yeah that's no good. I'll fix that when I'm back at my computer. Thanks for pointing that out!
Re: Masstree: A cache-friendly mashup of tries and B-trees
#18So what are the advantages over adaptive radix trees or good old judy-dict/array? 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 eve…
Here's a recent comparison of Masstree to ART: https://twitter.com/andy_pavlo/status/986647389820747776?s=2... ART looks to be better in most cases. It's on my list of K-V stores to review: https://www.the-paper-trail.org/page/reading-list/
tangential , Andy's DB lectures are rocking my world
Re: Masstree: A cache-friendly mashup of tries and B-trees
#19I'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.
Running index-microbenchmarks now to see which is faster :)
Re: Masstree: A cache-friendly mashup of tries and B-trees
#20Why do I get a gross yellow block covering the image when I mouse over it? edit: oh, it's because it's a link and they have some background coloring or something on links.
Should be fixed now! (But I've been wrong with css before)