带有等级操作的无锁定跳过列表

Question

是否有人知道支持排序操作（即找到第k个元素）的任何无锁定跳过列表实现和/或研究论文？或者，是否有人知道这种手术无法奏效的根本原因？

加分点：

不承担垃圾收集的执行力度。我的经验已经有不少研究论文忽略了内存管理。

支持：

有关如何军衔操作可以在常规skiplist进行了描述：“一个跳跃列表食谱”由威廉·皮尤

为了更好的无锁skiplist之一描述：“实用锁定自由”的凯尔·弗雷泽

一个更好的无锁skiplist implimentations的：http://www.1024cores.net/home/parallel-computing/concurrent-skip-list

Answer 1

不像键，值和水平，这是一个元件的局部特性在skiplist和不受与其它元件的操作，秩的元素的，即其在列表中的位置，是发生改变的属性插入和删除排名较低的元素。因此，对于并发跳过列表，元素的排名非常短暂，因为它可能会在任何时刻被插入或删除较低排名元素的并发运行操作所改变。

例如，假设您通过级别1列表进行线性搜索，其中第012个元素为k。在目前您已经执行了步骤的情况下，并发修改可能会添加或删除任何数量的先前元素，因此您刚发现的元素的当前等级实际上是未知的。此外，当线程正在执行前向迭代时，可以在其当前位置与开始搜索时的元素之间进行并发更改。因此，搜索结果不是当前排名为k的元素，也不是搜索开始时排名为k的元素。这只是一些随机元素！

简而言之，对于并发列表，元素的排名是一个不明确的概念，而按排名搜索是一个不明确的操作。这是它永远无法工作的根本原因，为什么实施者不应该为提供这种操作而烦恼。