Comment by foota

Funny timing, I've been looking at this recently. Some other well performing concurrent ordered data structures are ART (adaptive radix trees) and masstree. Skiplists are common since they're easier to implement lock free, but they don't seem to perform well relative to these alternatives.