algorithm - 跳过列表与二进制搜索树

我最近遇到了称为skip list的数据结构。它的行为似乎与二叉搜索树非常相似。

您为什么要在二进制搜索树上使用跳过列表？

最佳答案

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

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

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

我读了弗雷泽和哈里斯的最新论文Concurrent programming without locks。如果您对无锁数据结构感兴趣，那真是好东西。本文着重介绍Transactional Memory和理论上的多字比较交换MCAS。由于没有硬件支持它们，因此两者都在软件中进行了仿真。我对他们完全能够在软件中构建MCAS印象深刻。

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

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

锁定跳过列表的速度非常快。与并发访问的数量相比，它们的扩展性非常好。这就是使跳过列表变得特别的原因，其他基于锁的数据结构在压力下容易崩溃。

无锁定跳过列表始终比锁定跳过列表更快，但仅勉强。

事务性跳过列表始终比锁定和非锁定版本慢2-3倍。

在并发访问下锁定红黑树 croak。每个新的并发用户的性能都会线性下降。在两种已知的锁定红黑树实现中，一种在树重新平衡期间本质上具有全局锁定。另一个使用花哨的(复杂的)锁升级，但是仍然没有显着超出执行全局锁的版本。

无锁红黑树不存在(不再适用，请参阅更新)。

事务性红黑树与事务性跳过列表相当。这是非常令人惊讶和非常有希望的。事务性内存，尽管速度较慢，但​​更容易编写。它可以像快速搜索和替换非并行版本一样容易。

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