那么这个时候有个小问题就来了：怎么从 21 直接到 25 的呢？

看论文中的图片，稍微有一点不容易明白。

所以，我给大家重新画个示意图：

在 21 到 26 节点之间，往下了一层，逻辑也很简单。

21 节点有一个右指针指向 26，先判断右指针的值大于查询的值了。

于是下指针就起到作用了，往下一层，再继续进行右指针的判断。

其实每个节点的判断逻辑都是这样，只是前面的判断结果是进行走右指针。

按照这个往上抽节点的思想，假设我们抽到第四层，也就是论文中的这个示意图：

我们查询 25 的时候，只需要经过 2 次。

第一步就直接跳过了 21 之前的所有元素。

怎么样，爽不爽？

但是，它是有缺陷的。

火男的论文里面是这样说的

This data structure could be used for fast searching, but insertion and deletion would be impractical.

查询确实飞快。但是对于插入和删除 would be impractical。

impractical 是什么意思？

你看，又学一个四级单词。

对于插入和删除几乎是难以实现的。

你想啊，上面那个最底层的有序链表，我一开始就拿出来给你了。

然后我就说基于这个有序链表每隔一个节点抽离到上一层去，再构建一个链表。那么这样上下层节点比例应该是 2:1。巴拉巴拉的.....

但是实际情况应该是我们最开始的时候连这个有序链表都没有，需要自己去创建的。

就假设要在现有的这个跳表结构中插入一个节点，毋庸置疑，肯定是要插入到最底层的有序链表中的。

但是你破坏了上下层 1:2 的比例了呀？

怎么办，一层层的调整呗。

可以，但是请你考虑一下编码实现起来的难度和对应的时间复杂度？

要这样搞，直接就是一波劝退。

这就受不了了？

我还没说删除的事呢。

那怎么办？

看看论文里面怎么说到：

首先我们关注一下第一段划红线的地方。

火男写到：50% 的节点在第一层，25% 的节点在第二层， 12.5% 的节点在第三层。

你以为他在给你说什么？

他要表达的意思除了每一层节点的个数之外，还说明了层级：

没有第 0 层，至少论文里面没有说有第 0 层。

如果你非要说最下面那个有全部节点的有序链表叫做第 0 层，我觉得也可以。但是，我觉得叫它基础链表更加合适一点。

然后我再看第二段划线的地方。

火男提到了一个关键词：randomly，意思是随机。

说出来你可能不信，但是跳表是用随机的方式解决上面提出的插入（删除）之后调整结构的问题。

怎么随机呢？抛硬币。

是的，没有骗你，真的是“抛硬币”。

跳表中的“硬币”

当跳表中插入一个元素的时候，火男表示我们上下层之间可以不严格遵循 1:2 的节点关系。

如果插入的这个元素需要建立索引，那么把索引建立在第几层，都是由抛硬币决定的。

或者说：由抛硬币的概率决定的。

我问你，一个硬币抛出去之后，是正面的概率有多大？

是不是 50%？

如果我们把这个概率记为 p，那么 50%，即 p=1/2。

上面我们提到的概率，到底是怎么用的呢？

火男的论文中有一小节是这样的写的：

非常关键的一张图啊。

短短几行代码，描述的是如何选择层级的随机算法。

首先定义初始层级为 1（lvl := 1）。

然后有一行注释：random() that returns a random value in [0...1)

random() 返回一个 [0...1) 之间的随机值。

接下来一个 while...do 循环。

循环条件两个。

第一个：random() < p。由于 p = 1/2，那么该条件成立的概率也是 1/2。

如果每随机一次，满足 random() < p，那么层级加一。

那假设你运气爆棚，接连一百次随机出来的数都是小于 p 的怎么办？岂不是层级也到 100 层了？

第二个条件 lvl < MaxLevel，就是防止这种情况的。可以保证算出来的层级不会超过指定的 MaxLevel。

这样看来，虽然每次都是基于概率决定在那个层级，但是总体趋势是趋近于 1/2 的。

带来的好处是，每次插入都是独立的，只需要调整插入前后节点的指针即可。

一次插入就是一次查询加更新的操作，比如下面的这个示意图：

另外对于这个概率，其实火男在论文专门写了一个小标题，还给出了一个图表：