3 ms·
AVL (and other binary search) trees in general are just a poor choice for most situations given the realities of cache behavior.
by loeg 8y ago
AVL (and other binary search) trees in general are just a poor choice for most situations given the realities of cache behavior.
- MaxBarraclough 8y agoHence the development of the 'Judy array' - actually a high-arity tree optimised for good cache behaviour - right? See also the 'masstree' which has a similar premise - https://news.ycombinator.com/item?id=18199086 https://news.ycombinator.com/item?id=18199086
- loeg 8y agoI was thinking of classic B-trees, but yeah something with high arity is the right way to go.