Re:Masstree: A cache-friendly mashup of tries and B-trees
by leiroigh on Friday October 12, 2018 @01:31PM
(#18203083)
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
by HenryR on Friday October 12, 2018 @01:48PM
(#18203228)
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.
https://news.ycombinator.com/item?id=18132730