背景

在线性的数据数据结构中我们经常可以想到数组和链表，数组是插入慢查询快，而链表是插入快，查询要稍微慢一些，而跳表主要是针对链表查询速度进行优化的一种数据结构，多层级的跳表实际上是对底层链表的索引，非常典型的空间换时间，把链表的查询时间尽量控制在O(logN)。

实现

由于使用了类似索引点数据维护方式，所以新增和删除需要同时维护跳表结构，跳表利用概率平衡的方式简化新增和删除操作，和树操作利用左旋和右旋等操作维持数据平衡不同，跳表利用了类似猜硬币的方式抉择出在哪一层插入或者删除节点和更新索引。

从下面的abcde图中，我们可以看一下跳表的演进：

首先a是一个典型的链表结构，对于查询来说需要O(n)的时间，链表长度越长查询越慢。

b在a的基础上，每次隔2个节点加一个额外的指针，通过这样的操作，每次查询时间就减少了【n/2】+次数。

c、d、e继续按照这样的思路继续加额外指针，最终只留下从头到尾的一层指针结束。

但是可以看到如果按照统一的思路每一层这样加节点对于维护整个节点的效率十分低，我们将拥有额外指针的节点看作一个K层节点，按照图中整理可以看到对于1层的节点占了50%，2层为25%，3层为12.5%......如果插入新节点能按照这样的规律进行插入删除，那么效率提升就不会出现很大的性能影响。

维护辅助指针会带来更大的复杂度，索引在每一层的节点中都会指向当前层所在的下一个节点，也就是说每一层都是一个链表。

时间复杂度如何计算的？

推导公式如下：

n/2^k => n / 2^k = 2 => h = log2n -1 => O(logn)

k代表节点层数，h表示最高级

原始的链表有n个元素，则一级索引有n/2 个元素、二级索引有 n/4 个元素、k级索引就有 n/(2^k)个元素。最高级索引一般有2个元素（头指向尾），最高级索引指向2 = n/(2^h)，即 h =(log2)n-1，最高级的索引h为索引层高度+原数据高度，最终跳表高度为 h = (log2) n。

经过索引的优化之后，整个查询的时间复杂度可以近似看作O(logn) ，和 二分查找的效率类似。

空间复杂度如何计算？

随着层数的增加，建立索引的空间开销是越来越小的，一层索引为 n/2，二层索引为 n/4，三层为 n/8 .....最后 n/2 + n/4 + n/8 +.... + 2（最高层一般为2个节点）最后因为分母相加可以认为是近似 O(n) 的空间复杂度。

查询

下面是跳表的增删改查的处理流程，由于删除和插入都依赖查询，我们先从查询开始介绍：

查询的操作方式可以看下面的绘图，比如如果需要查找存在于中间的节点17，则会根据线条顺序查找，这里简述查询顺序：

1. 从索引的最高层进行查找，直接找到下一个节点。
2. 如果当前内容大于节点内容，则直接找下一个节点比较。
3. 如果当前节点等于查找节点则直接返回。
4. 如果当前节点大于节点，并且下一个节点大于当前节点，并且层高不为0，则继续往层高更低的一个层级节点查找同时回到更低层级前一个节点，如果层高为0，则返回当前节点，当前节点的key要大于查找的key。

查找比较好理解，就是用索引快速跨越多个链表节点减少搜索次数，然后层数下探找到相关的节点，注意拥有索引的节点，通常在上层节点会有指向下层的指针。

插入

插入操作比较关键，因为这里涉及到非常影响跳表性能的索引节点选举动作。按照之前的查找操作步骤，插入操作需要每次记录每一层的前任节点。

关键点：插入的关键点在于选举那个节点增加层高来维持二分查找的效率，在找到位置之后，通常使用随机抛硬币的方式随机为节点增加层高，层级越高被选中的概率通常会指数倍的降低，之后根据三个参数：种子（用于实现概率随机）以及当前节点的层数和概率值P或者其他的随机值算法进行计算，但是为了防止单节点层高过高，通常会限制最终层高防止单一节点的层高超过上限。

根据墨菲定律，无论单一节点层高过高可能性再低，都需要做限制。

这里挑了LevelDB跳表数据结构的一段代码进行介绍：

func (p *DB) randHeight() (h int) {
  // 限制跳表扩展的最高层级
    const branching = 4
    h = 1
    for h < tMaxHeight && p.rnd.Int()%branching == 0 {
        h++
    }
    return
}

插入节点之后，会根据记录的前任节点在每一层的位置按照跳表规则建立新节点的索引。

跳表插入新节点本身的更新十分非常简单，只需要把当前节点下一个节点指向插入节点的下一个节点的下一个节点，插入节点的下一个节点指向当前节点 即可。

插入操作时间复杂度

如果是单链表，那么一次遍历就可以完成，结果永远都是O(1)，对于跳表的插入，最坏的情况也就是需要在所有层都更新索引，这种情况是O(logN)。

删除

删除也是依赖查询完成的，根据查询找到待删除节点之后在每一层按照查询的规则把当前节点删除即可。

删除的时间复杂度快慢取决于于查询的层数，假设需要删除N个元素，而每一层其实都是一个单向的链表，单链表的查询是O(1)，同时是因为跳表最优是近似二分查找的效率，索引层数为logn，删除的层数也是logN，N取决于层级。

最终删除元素的总时间包含：

查找元素的时间 + _删除 logn个元素的时间 = O(logn) + O(logn) = 2O(logn)，忽略常数部分最终结果为 O(logn)。

使用场景

其实多数和Key-Value有关的LST-Tree 数据结构都有类似的跳表实现，因为链表在业务方面使用可能比较少，但是在数据结构和数据库设计上面却是至关重要的地位：

• HBase
• Redis
• LevelDB

小结

• 跳表让链表也能够完成二分查找的操作
• 元素的插入会根据抛硬币和权重分配随机选举Level
• 最底层永远是原始链表，而上层则是索引数据
• 索引节点通常会多一个指针指向下层节点，但是不是所有的程序设计都是按照这种方式，有其他的处理方式间接实现此功能（具体可以看redis 的 zset源代码）
• 跳表查询、插入、删除的时间复杂度为O(log n)，与平衡二叉树接近