我最近遇到了一种称为跳过列表。它似乎与二叉搜索树具有非常相似的行为。
为什么要在二叉搜索树上使用跳跃列表？
跳过列表更适合并发访问/修改。赫伯·萨特写了一篇article关于并发环境中的数据结构。它有更深入的信息。
二叉搜索树最常用的实现是红黑树。当树被修改时，并发问题就会出现，它通常需要重新平衡。重新平衡操作可能会影响树的大部分，这需要在许多树节点上使用互斥锁。将节点插入到跳跃列表中的操作更加本地化，只有直接链接到受影响节点的节点才需要锁定。
乔恩·哈罗普斯评论更新
我读了弗雷泽和哈里斯的最新论文无锁并发编程。如果您对无锁数据结构感兴趣，这确实是个好东西。该论文重点关注事务内存以及理论操作多字比较和交换 MCAS。这两者都是在软件中模拟的，因为尚无硬件支持它们。他们能够用软件构建 MCAS，这给我留下了深刻的印象。
我没有发现事务内存的东西特别引人注目，因为它需要垃圾收集器。还软件事务内存受到性能问题的困扰。然而，如果硬件事务内存变得普遍，我会非常兴奋。最终它仍处于研究阶段，并且在接下来的十年左右的时间内不会用于生产代码。
在第 8.2 节中，他们比较了几种并发树实现的性能。我将总结他们的发现。下载 pdf 版本是值得的，因为它在第 50、53 和 54 页上有一些信息非常丰富的图表。
-
锁定跳过列表速度快得惊人。它们随着并发访问的数量而扩展得非常好。这就是跳跃列表的特殊之处，其他基于锁的数据结构在压力下往往会崩溃。
-
无锁跳过列表始终比锁定跳过列表快，但也只是勉强快。
-
事务性跳过列表始终比锁定和非锁定版本慢 2-3 倍。
-
锁定红黑树并发访问下发出嘎嘎声。它们的性能随着每个新并发用户的增加而线性下降。在两种已知的锁定红黑树实现中，一种本质上在树重新平衡期间具有全局锁定。另一种使用奇特（且复杂）的锁升级，但仍然没有明显优于全局锁版本。
-
无锁红黑树不存在（不再正确，请参阅更新）。
-
事务性红黑树与事务性跳过列表相当。这是非常令人惊讶和非常有希望的。事务性内存，虽然更容易编写，但速度较慢。在非并发版本上可以像快速搜索和替换一样简单。
Update
这是关于无锁树的论文：使用 CAS 的无锁红黑树.
我没有深入研究过，但表面上看起来很可靠。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
