Redis之跳跃表

by: nestor 邵泰深 2020-04-08

保护私人版权，尊重他人版权。转载请注明出处并附带页面链接

跳跃表简介

跳跃表（skiplist）是一种随机化的数据，由 William Pugh 在论文《Skip lists: a probabilistic alternative to balanced trees》中提出，跳跃表以有序的方式在层次化的链表中保存元素，效率和平衡树媲美 —— 查找、删除、添加等操作都可以在对数期望时间下完成，并且比起平衡树来说，跳跃表的实现要简单直观得多。

它最大的优势是原理简单、容易实现、方便扩展、效率更高。因此在一些热门的项目里用来替代平衡树，如 redis, leveldb 等。

Redis 的五种基本结构中，有一个叫做 有序列表 zset 的数据结构，它类似于 Java 中的 SortedSet 和 HashMap 的结合体，一方面它是一个 set 保证了内部 value 的唯一性，另一方面又可以给每个 value 赋予一个排序的权重值 score，来达到排序的目的。它的内部实现就依赖了一种叫做 「跳跃列表」 的数据结构。

为什么使用跳跃表

性能考虑： 在高并发的情况下，树形结构需要执行一些类似于 rebalance 这样的可能涉及整棵树的操作，相对来说跳跃表的变化只涉及局部
实现考虑： 在复杂度与红黑树相同的情况下，跳跃表实现起来更简单，看起来也更加直观

跳跃表的基本思想

首先我们看一个普通的链表结构：

这个链表中，如果要搜索一个数，需要从头到尾比较每个元素是否匹配，直到找到匹配的数为止，即时间复杂度是 O(n)。同理，插入一个数并保持链表有序，需要先找到合适的插入位置，再执行插入，总计也是 O(n)的时间。

但假如我们每相邻两个节点之间就增加一个指针，让指针指向下一个节点，如下图：

如上图，我们新创建一个链表，它包含的元素为前一个链表的偶数个元素。这样在搜索一个元素时，我们先在上层链表进行搜索，当元素未找到时再到下层链表中搜索。例如搜索数字 19 时的路径如下图：

先在上层中搜索，到达节点 17 时发现下一个节点为 21，已经大于 19，于是转到下一层搜索，找到的目标数字 19。

利用同样的方式，我们可以在新产生的链表上，继续为每两个相邻的节点增加一个指针，从而产生第三层链表。同理，我们可以不断地增加层数，来减少搜索的时间：

在上面的 4 层链表中搜索 25，在最上层搜索时就可以直接跳过 21 之前的所有节点，因此十分高效。

更进一步的跳跃表

可以想象，当链表足够长，上面的多层链表结构可以帮助我们跳过很多下层节点，从而加快查找的效率。

但是，这种方法在插入数据的时候有很大的问题。新插入一个节点之后，就会打乱上下相邻两层链表上节点个数严格的 2:1 的对应关系。如果要维持这种对应关系，就必须把新插入的节点后面的所有节点重新进行调整，这会让时间复杂度重新蜕化成 _O(n)_。删除数据也有同样的问题。

因此跳表（skip list）表示，我们就不强制要求 1:2 了，一个节点要不要被索引，建几层的索引，都在节点插入时由抛硬币决定。当然，虽然索引的节点、索引的层数是随机的，为了保证搜索的效率，要大致保证每层的节点数目与上节的结构相当。下面是一个随机生成的跳跃表：

每一个节点的层数是随机出来的，而且新插入一个节点并不会影响到其他节点的层数，因此，插入操作只需要修改节点前后的指针，而不需要对多个节点都进行调整，这就降低了插入操作的复杂度。

关于随机层数

对于每一个新插入的节点，都需要调用一个随机算法给它分配一个合理的层数，源码在 t_zset.c/zslRandomLevel(void) 中被定义：

int zslRandomLevel(void) { 
    int level = 1; 
    while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF)) 
        level += 1; 
    return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL; 
}

直观上期望的目标是 50% 的概率被分配到 Level 1，25% 的概率被分配到 Level 2，12.5% 的概率被分配到 Level 3，每一层的晋升率都是 50%。

小结

各种搜索结构提高效率的方式都是通过空间换时间得到的。
跳跃表最终形成的结构和搜索树很相似。
跳跃表通过随机的方式来决定新插入节点来决定索引的层数。
跳跃表搜索的时间复杂度是 O(logn)，插入/删除也是。