跳过列表 - 曾经使用过吗？

我想知道这里是否有人使用跳过列表.它看起来与平衡二叉树具有大致相同的优点,但实现起来更简单.如果你有,你是自己编写的,还是使用预先编写的库(如果有的话,它的名字是什么)？

我的理解是,它们不是二元树(例如红黑树)的有用替代品,因为它们用于B树以供数据库使用,因此您可以将级别#降低到可行的最小值并处理w/base-K日志而不是base-2日志以获得性能特征.概率跳过列表的算法(IMHO)比相应的B树算法更容易获得.此外,还有一些关于无锁跳过列表的文献.几个月前我看了它们使用它们,但后来放弃了发现HDF5库的努力.

关于这个主题的文献:

Bill Pugh的论文:

跳过列表食谱

跳过列表:平衡树的概率替代

同步维护跳过列表

非学术论文/教程:

Eternal Confuzzled(对几个数据结构进行了一些讨论)

Thomas A. Anastasio的"Skip Lists"

实际上,对于我的一个项目,我正在实现我自己的完整STL.我使用了一个跳过列表来实现我的std::map.我接受它的原因是它是一个简单的算法,它非常接近平衡树的性能,但具有更简单的迭代功能.

此外,Qt4的QMap也是一个跳过列表,这是我在我的使用它的原始灵感std::map.

几年前,我实现了自己的概率算法类.我不知道任何库实现,但它已经很长时间了.实现起来非常简单.我记得他们对大型数据集有一些非常好的属性,并避免了一些重新平衡的问题.我认为实现也比二进制尝试更简单.这里有一个很好的讨论和一些示例c ++代码:

http://www.ddj.us/cpp/184403579?pgno=1

还有一个带有运行演示的applet.这里可爱的90年代Java狡猾:

http://www.geocities.com/siliconvalley/network/1854/skiplist.html

Java 1.6(Java SE 6)将ConcurrentSkipListSet和ConcurrentSkipListMap引入了集合框架.所以,我推测那里的人确实在使用它们.

在多线程情况下,跳过者倾向于提供更少的锁定争用,并且(概率上)具有与树类似的性能特征.

参见William Pugh 的原始论文 [pdf].