skiplists 有什么用？

A while back, I joined Phil Eaton’s book club on The Art of Multiprocessor Programming, and the topic of skiplists came up.

不久前，我加入了 Phil Eaton 的 book club，主题是 The Art of Multiprocessor Programming，当时提到了 skiplists 的话题。

For most of my career, skiplists had always seemed like a niche data structure, with a rabid cult following but not a whole ton of applicability to my life. Then six or so years ago, we encountered a problem at Antithesis that seemed intractable until it turned out that a generalization of skiplists was exactly what we needed.

在我的大部分职业生涯中，skiplists 一直看起来像是一种小众的数据结构，有狂热的追随者但对我生活适用性并不大。大约六年前，我们在 Antithesis 遇到了一个看似棘手的问题，直到发现 skiplists 的一个泛化形式正是我们需要的。

Before I tell you about that, though, let me explain what skiplists are (feel free to skip ahead if you already know them well).

不过，在我讲述那个之前，让我先解释一下 skiplists 是什么（如果您已经很了解它们，可以随意 skip 向前跳）。

What are skiplists?

什么是 skiplists？

A skiplist is a randomized data structure that’s basically a drop-in replacement for a binary search tree with the same interface and the same asymptotic complexity on each of its operations. Some people like them because you can produce relatively simple and understandable lock-free concurrent implementations, and others like them as a matter of taste, or because they enjoy listening to bands that you’ve totally never heard of.

skiplist 是一种随机化数据结构，基本上是 binary search tree 的即插即用替代品，具有相同的接口和每个操作的相同渐近复杂度。有些人喜欢它们，因为你可以产生相对简单且易懂的无锁并发实现，其他人则出于个人喜好，或者因为他们喜欢听你完全没听说过的乐队。

In implementation terms, you can think of them roughly as linked lists plus “express lanes”:

在实现方面，你可以大致将它们想象成链表加上“快速通道”：

You start with a basic linked list, and then add a hierarchy of linked lists with progressively fewer nodes in them. In the example above, the nodes in the higher-level lists are chosen probabilistically, with each node having a 50% chance of being promoted to the next level.¹

你从一个基本的链表开始，然后添加一个由逐渐减少节点组成的链表层次结构。在上面的例子中，更高级别列表中的节点是概率性地选择的，每个节点有 50% 的几率被提升到下一级。¹

This helps with search, because you can use the higher-level lists to skip more quickly to the node ...