有一种查询效率特别高的有序的数据结构,跳跃表(SkipList),这种结构,在Redis和levelDB中,都有用到。
其实是在有序链表的基础上进行扩展,丰富了在链表中查找制定值,需要 O(N)的时间复杂度的问题,它在查
询时,能做到最快 O(1),平均 O(logN),最坏 O(N)的复杂度。

一般,要求查询效率高的结构,都会想到平衡树,但是树比跳跃表更复杂,但是效率,未必有跳跃表高。许多
时候可以用跳表来取代平衡树。

在 Redis 中,跳跃表作为 有序集合(ZSET)的底层实现之一和集群节点内部结构。源码在 src/server.h

typedef struct zskiplist {
    struct zskiplistNode *header, *tail;    // 头节点指针和尾节点指针
    unsigned long length;   // 节点数量(不包括头节点)
    int level;  // 所有节点,层数最高的节点的层数
} zskiplist;
/* ZSETs use a specialized version of Skiplists */
typedef struct zskiplistNode {
    sds ele;    // 数据值
    double score;   // 分值
    struct zskiplistNode *backward; // 后退指针
    struct zskiplistLevel { // 每个节点的层
        struct zskiplistNode *forward;  // 每层前进指针
        unsigned int span;  // 距离下个相同层的节点的跨度
    } level[];
} zskiplistNode;

作者 antirez 指出 Redis 跳跃表与一般跳跃表的不同

a) this implementation allows for repeated scores. // 允许分值重复
b) the comparison is not just by key (our ‘score’) but by satellite data. // 对比的时候不仅比较分值还比较对象的值
c) there is a back pointer, so it’s a doubly linked list with the back pointers being only at “level 1”. // 有一个后退指针,即在第一层实现了一个双向链表,允许后退遍历

跳跃表结构
跳跃表结构

表头节点是一个拥有32个level的 zskiplistNode 结构,正向遍历跳表,就是从表头
的某层开始,一般层的数量越多,查询的效率就会越高,每次插入一个新跳表节点时,会随机
生成一个 1 ~ 32 的层数(对应表头节点,最高32层),从索引位置 0 ~ 31。

跳跃表的查找

跳跃表查找
跳跃表查找

当我们要查找一个分值为46的节点时,普通的链表只能从头至尾循环查找,对于跳跃表,它每次
level 最高的层开始查找。

  1. 首先,从 zskiplist 的头结点找到最高 level 的节点,55 大于 要找的46,根据层的 backward 指针后退至 L3 节点;
  2. L3 节点的分值为 21 小于 46 ,则从 55 的下一层开始后退到 L2 节点;
  3. L2 节点的分值 37 小于 46, 则从 L2 节点的下一层前进至 L1 节点;
  4. L1 节点的分值为 46,查找成功

少量的数据,在做这种对比的时候,优势并不明显,如果数据量特别多,跳过的元素数量
将会非常可观,效率的提升也会非常明显。

当跳跃表的多个元素分值(score)相同时,会按照成员对象的字典顺序进行排序,成员
对象小的节点排在靠近表头的位置,成员对象大的节点排在靠近表尾的位置。

结语

跳跃表是特别高效的节点查找方式,在工作中,在自己的程序设计时,如果有对已排序
的数据做查找时,它是比树更简单的一种思路。