跳表的定义
跳表是由 William Pugh(音译为威廉·普) 发明的，最早出现于他在 1990 年发表的论文《Skip Lists: A Probabilistic Alternative to Balanced Trees》。跳表全称为跳跃列表，它允许快速查询、插入和删除一个有序连续元素的数据链表。
跳表的演化过程
对于单链表来说，即使数据是已经排好序的，想要查询其中的一个数据，只能从头开始遍历链表，这样效率很低，时间复杂度很高，是 O(n)。
为了提高查询的效率，我们可以为链表建立一个'索引'。在原始链表的基础上，每两个结点提取一个结点建立索引，我们把抽取出来的结点叫作索引层或者索引，down 表示指向原始链表节点的指针。
例如查找 15，首先在索引层遍历，当遍历到值为 14 的结点时，发现下一个结点的值为 17，则目标值在这两个结点之间。通过 14 结点的 down 指针回到原始链表继续遍历，只需再遍历两个结点即可找到数据。整个过程比原始链表少遍历了节点。
如果给索引层再加一层索引，效率会更高。这种通过对链表加多级索引的结构，就是跳表。
跳表的优化思路
按照上述生成链表的方式，每一层链表的节点个数是下面一层的节点个数的一半，查找过程类似二分查找，时间复杂度可降低到 O(log n)。但在插入或删除数据时，会打乱上下相邻两层链表上节点个数的严格对应关系。如果要维持这种关系，必须重新调整后续所有节点，导致时间复杂度蜕化成 O(n)。
Skiplist 的设计为了避免这种问题，不再严格要求对应比例关系，而是插入一个节点的时候随机出一个层数。每次插入和删除都不需要考虑其他节点的层数。
跳表如何保证效率
Skiplist 插入节点时随机出层数，一般跳表会设计一个最大层数 maxLevel 的限制，其次会设置多增加一层的概率 p。计算随机层数的逻辑如下：
