2 ms·

You should check out Height-Oriented Tries as well. Their benchmarks shows that it outperforms both ART and masstree. EDIT: Oops, yes, I meant Height-Optimized

• foota 2y ago
  Will take a look, thanks! I think you meant height-optimized tries, since I had a tough time giving it at first :) Ideally I'd like to find a way to store a non overlapping ordered list of intervals while being able to atomically (wrt other insertions) avoid inserting overlaps. This is part of a data structure tracking locked ranges, so being able to update them in parallel would be nice, since it today takes a lock over the whole tree while inserting new locked ranges. Probably, this would require something with next value pointers. Maybe I could do some kind of scheme where to insert you have to first optimistically lock the predecessor with the to be inserted node, and then insert the new node where it belongs?
  • mad 2y ago
    You should also check out the Maple Tree (https://docs.kernel.org/core-api/maple_tree.html https://docs.kernel.org/core-api/maple_tree.html). It's the data structure used to track non-overlapping intervals in the Linux kernel's virtual memory subsystem. If you don't mind sharing, what's your use case for such a data structure?