跳过列表与二叉搜索树 [英] Skip List vs. Binary Search Tree

问题描述

我最近遇到了称为跳过列表.它似乎与二叉搜索树具有非常相似的行为.

I recently came across the data structure known as a skip list. It seems to have very similar behavior to a binary search tree.

你为什么要在二叉搜索树上使用跳过列表?

Why would you ever want to use a skip list over a binary search tree?

推荐答案

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

Skip lists are more amenable to concurrent access/modification. Herb Sutter wrote an article about data structure in concurrent environments. It has more indepth information.

来自 Jon Harrops 评论的更新

Update from Jon Harrops comments

我阅读了 Fraser 和 Harris 的最新论文 无锁并发编程.如果您对无锁数据结构感兴趣，那真是个好东西.论文重点介绍了Transactional Memory和多字比较和交换MCAS的理论操作.这两者都是在软件中模拟的，因为尚无硬件支持它们.他们能够在软件中构建 MCAS 给我留下了深刻的印象.

I read Fraser and Harris's latest paper Concurrent programming without locks. Really good stuff if you're interested in lock-free data structures. The paper focuses on Transactional Memory and a theoretical operation multiword-compare-and-swap MCAS. Both of these are simulated in software as no hardware supports them yet. I'm fairly impressed that they were able to build MCAS in software at all.

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

I didn't find the transactional memory stuff particularly compelling as it requires a garbage collector. Also software transactional memory is plagued with performance issues. However, I'd be very excited if hardware transactional memory ever becomes common. In the end it's still research and won't be of use for production code for another decade or so.

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

In section 8.2 they compare the performance of several concurrent tree implementations. I'll summarize their findings. It's worth it to download the pdf as it has some very informative graphs on pages 50, 53, and 54.

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

• 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 的无锁红黑树.
我没有深入研究过，但表面上看起来很扎实.

Update
Here is paper about lock-free trees: Lock-Free Red-Black Trees Using CAS.
I haven't looked into it deeply, but on the surface it seems solid.

这篇关于跳过列表与二叉搜索树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！