跳转列表与二叉树 [英] 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?
推荐答案
跳转列表是更适合并发访问/修改。香草萨特写在并发环境中的数据结构的文章。它有更多深入的信息。
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.
这是乔恩Harrops评论更新
Update from Jon Harrops comments
我看了弗雷泽和哈里斯的最新论文并发编程无锁的。如果你有兴趣在无锁数据结构，真正的好东西。本文侧重于事务内存和理论操作多字，比较和交换MCAS。上述这些问题都在模拟软件没有硬件支持他们呢。我相当IM pressed，他们能够在软件都建立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.
我没有找到事务内存的东西特别引人注目，因为它需要一个垃圾收集器。此外软件事务内存存在着严重的性能问题。不过，我会很高兴，如果硬件事务内存以往任何时候都变得普遍。最后它仍然研究并不会用于生产$ C $下一个十年左右。
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.
- 锁定跳表是出奇的快。他们规模令人难以置信的并发访问数量。这是什么使跳表特殊，其他锁基于数据结构往往在pressure来发牢骚。
- 无锁跳跃列表一贯的速度比锁定跳表，但只能勉强。
- 事务跳跃列表一贯2-3倍的锁定和非锁定版要慢。 在并发访问
- 锁定红黑树的蛙鸣。他们的表现线性下降，每个新的并发用户。众所周知锁定红黑树的实现在这两个，一个基本上有树的再平衡过程中的全局锁。其他使用花哨的（复杂）锁升级，但仍然没有显著出执行全局锁版本。
- 无锁红黑树不存在（不再是真实的，见更新）。
- 事务红黑树与事务跳跃-列表相媲美。这是非常令人惊讶和非常有前途的。事务内存，但如果更慢更容易编写。它可以作为快速搜索一样方便，更换上的非同步版本。
- 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屋！
