无锁双向链接跳过列表

Question

关于无锁双向链表已经有了大量的研究。同样，在无锁跳过列表上也有大量的研究。不过，据我所知，还没有人能实现一个无锁的双向链接跳过列表。有没有人知道任何相反的研究，或者为什么是这样的原因？

编辑:特定场景用于构建快速分位数(50%、75%等)累加器。样本在O(log )时间内被插入到跳表中。通过维护当前分位数的迭代器，我们可以在O(1)时间内将插入值与当前分位数进行比较，并且可以很容易地确定插入值是在分位数的左侧还是右侧，以及分位数因此需要移动多少。它是向左移动的，需要前一个指针。

据我所知，任何困难都来自于在面对多个线程同时插入和删除的情况下保持先前指针的一致性。我认为解决方案几乎肯定会涉及到指针标记的巧妙使用。

Answer 1

但是你为什么要这样做呢？我实际上并没有坐下来研究跳跃列表是如何工作的，但从我模糊的理解来看，你永远不会使用前面的指针。那么为什么要有维护它们的开销呢？

但如果你想，我不明白你为什么不能。只需用双向链表替换单链表即可。双向链表在逻辑上是一致的，所以它们都是一样的。

Answer 2

我有个主意给你。我们使用“光标”在跳过列表中查找项目。光标还会保留用于到达该项目的轨迹。我们使用这个跟踪来删除和插入-它避免了执行这些操作的第二次搜索，并且它嵌入了遍历时看到的列表的版本号。我想知道您是否可以使用光标更快地找到上一项。

您必须在光标上向上移动一级，然后搜索仅比您的项目小一点的项目。或者，如果搜索到达链表的最低级别，则只需在遍历时保存上一个ptr。最低的级别可能有50%的时间用于查找您的商品，因此性能会很好。

嗯..。现在想想看，似乎光标有50%的时间是上一级的ptr，25%的时间需要从1级以上再次搜索，12.%的2级以上，等等。所以在不常见的情况下，你必须几乎完全重新进行搜索。

我认为这样做的好处是，你不必弄清楚如何“自由锁定”维护一个双向链接的跳跃列表，而且在大多数情况下，你可以极大地降低定位前一项的成本。

Answer 3

作为维护反向链接的另一种选择，当需要更新分位数时，您可以执行另一次搜索，以查找其关键字小于当前节点的节点。正如我在对johnnycrash的评论中所提到的，可以构建在每个级别找到的最右侧节点的数组，并由此可以加速第二次搜索。(Fomitchev的论文提到这是一种可能的优化。)