跳过列表与二进制搜索树 [英] 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.
二进制搜索树最常用的实现是红黑树 .修改树时，经常会出现并发问题，因此通常需要重新平衡.重新平衡操作可能会影响树的大部分，这将需要在许多树节点上使用互斥锁.将节点插入跳过列表的位置更加本地化，只有直接链接到受影响节点的节点才需要锁定.
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
我阅读了弗雷泽和哈里斯的最新论文没有锁的并发编程.如果您对无锁数据结构感兴趣，那真是好东西.本文着重于交易内存和理论上的多字比对交换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 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屋！
