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

二叉搜索树最常用的实现是[红黑树](http://en.wikipedia.org/wiki/Red-

black_tree)。修改树时会出现并发问题，它通常需要重新平衡。重新平衡操作会影响树的大部分，这将需要在许多树节点上使用互斥锁。将节点插入跳过列表更加本地化，​​只有直接链接到受影响节点的节点需要被锁定。

Jon Harrops 评论的更新

我阅读了 Fraser 和 Harris 的最新论文Concurrent programming without
locks。如果您对无锁数据结构感兴趣，这真是个好东西。这篇论文的重点是事务性内存和一个理论操作多字比较和交换
MCAS。这两者都是在软件中模拟的，因为还没有硬件支持它们。我对他们能够在软件中构建 MCAS 印象深刻。

我没有发现事务内存的东西特别引人注目，因为它需要垃圾收集器。软件事务内存也受到性能问题的困扰。但是，如果硬件事务内存变得普遍，我会非常兴奋。最后，它仍在研究中，在未来十年左右不会用于生产代码。

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

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

更新
这里是关于无锁树的论文：Lock-Free Red-Black Trees Using
CAS。
我没有深入研究它，但从表面上看，它似乎很牢固。