跳过列表更适合并发访问/修改。Herb Sutter写了一篇关于并发环境中数据结构的文章。它具有更深入的信息。

二进制搜索树最常用的实现是红黑树。修改树时，并发问题常常需要重新平衡。重新平衡操作可能会影响树的大部分，这将需要在许多树节点上使用互斥锁。将节点插入跳过列表的位置更加本地化，​​只有直接链接到受影响节点的节点才需要锁定。

乔恩·哈罗普斯的最新评论

我读了弗雷泽和哈里斯的最新论文《并发编程无锁》。如果您对无锁数据结构感兴趣，那真是好东西。本文重点讨论事务性存储和理论上的多字比较交换MCAS。由于没有硬件支持它们，因此这两个都是在软件中模拟的。我对他们完全能够在软件中构建MCAS印象深刻。

我没有发现事务性内存特别吸引人，因为它需要垃圾收集器。另外，软件事务存储器还受到性能问题的困扰。但是，如果硬件事务存储器变得很普遍，我将感到非常兴奋。最后，它仍在研究中，并且将在未来十年左右的时间内不再用于生产代码。

在8.2节中，他们比较了几种并发树实现的性能。我将总结他们的发现。值得下载pdf，因为它在第50、53和54页上有一些非常有用的图形。

• 锁定跳过列表 非常快。随着并发访问的数量，它们的扩展性非常好。这就是使跳过列表变得特别的原因，其他基于锁的数据结构在压力下容易崩溃。
• 无锁定跳过列表 始终比锁定跳过列表更快，但仅勉强。
• 事务性跳过列表 始终比锁定和非锁定版本慢2-3倍。
• *在并发访问下 *锁定红黑树的 嘶哑声。每个新的并发用户的性能都会线性下降。在两种已知的锁定红黑树实现中，一种在树重新平衡期间本质上具有全局锁定。另一个使用花哨的（复杂的）锁升级，但仍然没有显着超出执行全局锁的版本。
• 无锁的红黑树 不存在（不再适用，请参阅更新）。
• 事务性红黑树 与事务性跳过列表具有可比性。这是非常令人惊讶和非常有希望的。事务性内存，尽管速度较慢，但​​更容易编写。它可以像快速搜索和替换非并行版本一样容易。

更新
这里是有关无锁树的论文：使用CAS的无锁红黑树。
我没有深入研究它，但从表面上看似乎很牢固。