我想知道这里是否有人使用过 Improve this question 。它看起来具有与平衡二叉树大致相同的优点，但实现起来更简单。如果有，您是自己编写的，还是使用预先编写的库(如果是，它的名称是什么)？
最佳答案
我的理解是，与其说它们是二叉树(例如红黑树)的有用替代品，不如说它们是用于数据库使用的 B 树的有用替代品，这样您就可以将级别数保持在可行的最小值，并处理基于 K 的日志而不是基于 2 的日志以获得性能特征。概率跳跃列表的算法(恕我直言)比相应的 B 树算法更容易正确。另外还有一些关于无锁跳过列表的文献。几个月前我考虑过使用它们，但后来放弃了发现 HDF5 的努力。图书馆。
有关该主题的文献:
比尔·皮尤 (Bill Pugh) 的论文:
- A skip list cookbook
- Skip lists: A probabilistic alternative to balanced trees
- Concurrent Maintenance of Skip Lists
非学术论文/教程:
- Eternally Confuzzled (对几种数据结构进行了一些讨论)
- "Skip Lists"作者:托马斯·A·阿纳斯塔西奥
关于data-structures - 跳过列表——用过它们吗？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/234560/