Skip lists can be a good candidate for an ordered concurrent map implementation, outperforming an ordered map based on a bst/btree for instance.