数据结构之跳表理解

介绍

跳表（SkipList）是由William Pugh提出的。他在论文《Skip lists: a probabilistic alternative to balanced trees》中详细地介绍了有关跳表结构、插入删除操作的细节。

背景

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

实现

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

从下面的abcde图中，我们可以看一下跳表的演进： 首先a是一个典型的链表结构，对于查询来说需要O(n)的时间，链表长度越长查询越慢。

然后b在a的基础上，每次隔2个节点加一个额外的指针，通过这样的操作，每次查询对时间就减少了【n/2】+次数。 cde继续按照这样的思路继续加额外指针，最终只留下从头到尾的一层指针结束。

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

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

时间复杂度如何计算的？

推导公式如下：

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

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

k代表节点层数，h表示最高级，进过索引的优化之后，最后结果可以近似看作**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。

查找比较好理解，就是用索引快速跨越多个链表节点减少搜索次数，然后层数下探找到相关的节点。

这有一个细节是拥有索引的节点通常在上层节点会有一个向下的指针。

插入

插入操作比较关键，但是实际上插入的操作和查询的操作比较类似：

按照之前的查找顺序，插入操作需要每次记录每一层的前任节点，比如下面红圈中的内容：

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

关键点：插入的关键点在于选举那个节点增加层高来维持二分查找的效率，在找到位置之后，通常使用随机抛硬币的方式随机为节点增加层高，根据三个参数种子（用于实现概率随机）以及当前节点的层数和概率值P或者其他的随机值算法进行计算，但是为了防止单节点层高过高，通常会在外围做一个限制，具体可以看下面的代码：

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) = 2 O(logn)，忽略常数部分最终结果为 O(logn)

链表实现

JAVA版本的链表可以看下面的代码：

algo/SkipList.java at master · wangzheng0822/algo · GitHub

小结

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

使用场景

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

• HBase
• Redis
• LevelDB