跳过列表与二进制树 [英] Skip List vs. Binary Tree
问题描述
我最近遇到了被称为跳过列表的数据结构。他们似乎与二叉搜索树有非常相似的行为...我的问题是 - 你为什么要在二叉搜索树上使用跳过列表？
I recently came across the data structure known as a Skip list. They seem to have very similar behavior to a binary search tree... my question is - 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.
二进制搜索树中最常用的实现是一个红黑树。当树被修改时，并发问题就会出现，它往往需要重新平衡。重新平衡操作可以影响树的大部分，这将需要许多树节点上的互斥锁定。将节点插入跳过列表远远更为本地化，只有直接链接到受影响节点的节点需要被锁定。
The most frequently used implementation of a binary search tree is a red-black tree. The concurrent problems come in when the tree is modified it often needs to rebalance. The rebalance operation can affect large portions of the tree, which would require a mutex lock on many of the tree nodes. Inserting a node into a skip list is far more localized, only nodes directly linked to the affected node need to be locked.
从Jon Harrops评论的更新
Update from Jon Harrops comments
我阅读了Fraser和Harris的最新文章没有锁的并发编程。如果您对无锁数据结构感兴趣，那么真的很好。本文重点介绍事务性内存和理论操作多字比较和交换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倍。
- 锁定红黑树 croak并发访问。它们的性能随着每个新的并发用户线性下降。在两个已知的锁定红黑树实现中，一个基本上在树重新平衡期间具有全局锁。另一个使用花式（和复杂的）锁升级，但仍然没有显着地执行全局锁定版本。
- 无锁红黑树存在（不再是真的，请参阅更新）。
- 事务性红黑树与事务跳过列表相当。这是非常令人惊讶和非常有前途的。事务性内存，尽管写得更容易，但速度更慢。它可以像非并发版本一样快速搜索和替换。
- Locking skip lists are 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 out perform 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屋！
