在实践中，我发现在我的项目中，b -树的性能比跳过列表要好。跳跃表似乎更容易理解，但实现b -树并不难。

我所知道的一个优点是，一些聪明的人已经想出了如何实现只使用原子操作的无锁并发跳过列表。例如，Java 6包含ConcurrentSkipListMap类，如果您不喜欢的话，可以读取它的源代码。

但是写一个并发b树的变体也不是很难——我看到别人做过——如果你在沿着树向下走的时候先发制人地拆分和合并节点，“以防万一”，那么你就不必担心死锁，而且一次只需要在树的两个层次上持有一个锁。同步开销会稍微高一些，但是b树可能更快。

在实践中，我发现在我的项目中，b -树的性能比跳过列表要好。跳跃表似乎更容易理解，但实现b -树并不难。

我所知道的一个优点是，一些聪明的人已经想出了如何实现只使用原子操作的无锁并发跳过列表。例如，Java 6包含ConcurrentSkipListMap类，如果您不喜欢的话，可以读取它的源代码。

但是写一个并发b树的变体也不是很难——我看到别人做过——如果你在沿着树向下走的时候先发制人地拆分和合并节点，“以防万一”，那么你就不必担心死锁，而且一次只需要在树的两个层次上持有一个锁。同步开销会稍微高一些，但是b树可能更快。

跳过列表确实具有锁剥离的优势。但是，最短时间取决于新节点的级别如何确定。这通常是使用Random()完成的。在56000个单词的字典上，跳跃表比展开树花费更多的时间，而树比哈希表花费更多的时间。前两个不能匹配哈希表的运行时。此外，哈希表的数组也可以以并发的方式进行锁剥离。

当需要引用的局部性时，使用跳过列表和类似的有序列表。例如:在应用程序中查找日期前后的航班。

内存中二叉搜索展开树非常好，使用频率也更高。

跳过列表Vs展开树Vs哈希表运行时的字典查找op

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

二叉搜索树最常用的实现是红黑树。同时出现的问题是当树被修改时，它经常需要重新平衡。重新平衡操作可能会影响树的大部分，这将需要在许多树节点上使用互斥锁。在跳跃列表中插入一个节点要本地化得多，只有直接链接到受影响节点的节点才需要被锁定。

Jon Harrops的评论更新

我读了弗雷泽和哈里斯的最新论文《无锁并发编程》。如果你对无锁数据结构感兴趣，这是很好的东西。本文主要研究事务性内存和多字比较交换MCAS的理论操作。这两种方法都是在软件中模拟的，因为目前还没有硬件支持它们。他们能够在软件中构建MCAS，这让我印象深刻。

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

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

Locking skip lists is insanely fast. They scale incredibly well with the number of concurrent accesses. This is what makes skip lists special, other lock based data structures tend to croak under pressure. Lock-free skip lists are consistently faster than locking skip lists but only barely. transactional skip lists are consistently 2-3 times slower than the locking and non-locking versions. locking red-black trees croak under concurrent access. Their performance degrades linearly with each new concurrent user. Of the two known locking red-black tree implementations, one essentially has a global lock during tree rebalancing. The other uses fancy (and complicated) lock escalation but still doesn't significantly outperform the global lock version. lock-free red-black trees don't exist (no longer true, see Update). transactional red-black trees are comparable with transactional skip-lists. That was very surprising and very promising. Transactional memory, though slower if far easier to write. It can be as easy as quick search and replace on the non-concurrent version.

更新 这是一篇关于无锁树的论文:使用CAS的无锁红黑树。 我还没有深入研究，但从表面上看，它似乎是可靠的。

此外，除了给出的答案(易于实现，与平衡树的性能相结合)。我发现实现顺序遍历(向前和向后)要简单得多，因为跳过列表在其实现中实际上有一个链表。

跳过列表是使用列表实现的。

对于单链表和双链表存在无锁解决方案，但是对于任何O(logn)数据结构，没有直接只使用CAS的无锁解决方案。

但是，您可以使用基于CAS的列表来创建跳跃列表。

(请注意，使用CAS创建的MCAS允许任意数据结构，并且使用MCAS创建了概念证明红黑树)。

所以，尽管它们很奇怪，但它们却非常有用:-)