Redis数据结构-跳跃表

原创林晓林晓编程

一、回顾

在学习跳跃表之前，可以先回忆一下什么是数组、什么是链表。学习过数据结构应该知道。

数组属于顺序存储，用一段连续的内存位置来存储元素。我们可以通过数组的索引，快速访问到具体某一个元素，它的查询时间复杂度为O(1)。由于各个元素之间是有顺序的。当我们在插入或删除一个元素时，在执行动作的那个位置之后的所有元素，都会依次被动的变动一次。所以插入和删除的执行时间复杂度为O(n)。下图是一个数组，删除元素的案例示意图。

链表属于链式存储，用一组任意的存储单元来存储，并不要求物理上相邻。它主要通过在各个节点上维护一个指针地址，来关联数据元素的前后关系。由于存储位置是无顺序的，所以链表的查询时间复杂度为O(n)。而插入和删除的时间复杂度，若是找到目标之后，它的执行时间复杂度是O(1)，如果算上查询目标位置的时间，它的时间复杂度是O(n)。下图是一个单链表，删除元素的案例示意图。

其实，数据结构之间并没有优劣之分。而是结合实际场景，合理的运用每一种数据结构才是最优的方案。

二、二分查找

举个例子，如下图是一个从小到大的有序集合列表。

若想要查询【 45、70 】两个元素。将会对有序集合进行二次轮询，第一次轮询到45时已经比较了4次，第二次轮询到70时比较了6次。所以两次轮询总共比较了10次。那如果数据比较大，轮询时间也会更久。

通过二分查找的方式，提取一部分元素节点，作为索引。如下图所示。

通过将【10、30、58、80 】抽出作为上一级索引节点，通过上一级索引的比较之后再进行原链表元素的比较，那时间会不会缩短呢？

想要查询数据为70的元素，首先从上一级索引开始查找，有以下查询流程。

将70和10比较，比10大，则向后继续比较
将70和30比较，比30大，则向后继续比较
将70和58比较，比58大，则向后继续比较
将70和80比较，没有80大，则走向元素为58所指向的原链表元素地址58
将70和原链表地址的58所指向的后继元素70进行比较，咦，相同则查询完成

如果数据元素相对较多，则查询的速度越明显快速。那是否还可以继续优化一下呢？

通过将【 10、58 】抽出作为二级索引节点，通过二级索引的比较之后，再进行一级索引比较，最后再进行原链表元素比较，那时间会不会更短呢？

想要查询数据为70的元素，首先从二级索引开始查找，有以下查询流程。

将70和10比较，比10大，则向后继续比较
将70和58比较，比58大，且发现没有后继二级元素了，则向一级索引走下去
将70和一级索引的80比较，没有80大，则向58所指向的原链表元素地址走下去
将70和原链表元素地址58的后继元素70进行比较，咦，相同则查询完成

此时可以发现，查询元素为 70 的效率已经得到了进一步的提升。二分查找法会跟着数据元素的增长，优势呈现的就越明显。

三、跳跃表

知道了数组和链表的特性之后，又有人发现了一种新的数据结构，它是基于有序链表的一个扩展。也就是说，在链表的基础之上改造了查询方法，而这个方法，类似于上文所说的二分查找法，通过这种优化去弥补链表查询慢的缺点，并结合链表的优点所诞生的新型数据结构我们称它为 “跳跃表”。

跳跃表是一种有序数据结构，通过在每个节点中维护多个指向其他节点的指针，从而达到快速访问节点的目的。

下图，是基于上文案例一个完整的跳跃表模型图。

1）上图跳跃表左侧的zskiplist结构定义如下

typedef struct zskiplist{    # 表头节点和表尾节点    struct skiplistNode *header, *tail;    # 表中节点的数量    unsigned long length;    # 表中层数最大的节点层数    int level;  }zskiplist;

分析上图，从左边开始介绍，位于图片最左边的是zskiplist结构，包含以下属性

header 属性，指向跳跃表表头节点
tail 属性，指向跳跃表的表尾节点
level 属性，记录目前跳跃表内层数最大的那个节点数（不计表头）
lenght 属性，记录跳跃表的长度，即节点的数量（不计算表头）

表头指针和表尾指针的查询时间复杂度为O(1)
返回跳跃表的长度时间复杂度是O(1)
返回跳跃表中层高最大的那个节点的层数量时间复杂度是O(1)

2）上图的右侧部分，是跳跃表zskilistNode结构模型，定义如下

typedef struct zskiplistNode{    struct zskiplistNode *backward;# 后退指;    double score;  # 分值    object *obj;   # 成员对象    # 层    struct zskiplistLevel {        # 前进指针        struct zsklistNode *forward;        # 跨度        unsigned int span;    }level[]}zskiplistNode;

位于右侧是9个zskiplistNode结构，该结构包含以下属性

level 层属性，节点中用level 字样标记的各个层。每个层有包含两个属性：前进指针，和跨度。前进指针用于访问位于表尾方向的其他节点，而跨度则记录了前进指针所指向节点和当前节点的距离。
backward后退指针，节点中用BW字样标记节点的后退指针，它指向位于当前节点的前一个节点。用于从表尾向表头遍历时使用。
score 分值属性，各个节点中的1.0、2.0、3.0 是节点所保存的分值，按分值从小到大排序的。
obj 成员对象属性，各个节点的【10、25、30...】是节点所保存的成员对象值。

注意：表头节点和其他节点的构造是一样的，只是表头节点的一些属性不会用到，则可以忽略不计。

3.1 跳跃表的查询

举个例子，如上图所示，我们要查询数据元素为45的值。想要查询某一元素，需要从header的最高层开始向下遍历，首先从Level 3 层开始找。

注意：跨度是横向定位最近的一个，前进指针是向下定位最近的一个。

将 45 和 10 比较，比10大，与跨度（后面）所指向的值进行对比
此时，将 45 和 58 对比，没有58大，则定位到前进指针（向下）所指向的L2层
此时，将 45 和 30 对比，比30大，则继续向跨度（后面）定位
此时，将 45 和 58 对比，没有 58 大，则定位到前进指针（向下）所指向的L1层
此时，将 45 和 L1 中存储的跨度（后面）所指向的值进行对比，跨度是1 所指向的值是45，检测到值相等，则查询结束。

3.2 随机层数

Redis中的跳跃表，表头节点的层高共有32层，层数是根据随机算法计算所得。对于一个新插入的节点来说，都需要调用一个随机算法给它分配一个合理的层数。最期望的目的是 50% 的概率分配到Level 1 层上，25% 的概率分配到 Leval 2 层上，12.5% 的概率分配到 Level 3 层上，以此类推，都是基于每一层的50%的晋升率为基准的。

但是在Redis中它的晋升率是 25%。

# Redis 中随机算法，ZSKIPLIST_P == 0.25 的概率int zslRandomLevel(void) {      int level = 1;          while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF))          level += 1;      return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;  }

为了确定插入的层高，需要使用上面的随机算法

1）生成一个随机数

2）如果随机数小于一个概率因子P,则执行方案A，否则走方案B

列的初始高度为1，当插入新的元素时，需要不停的执行随机算法，如果要求执行的是A操作，则将列的层高+1，并且继续反复执行随机算法，直到第 n 次。模块要求执行的是B操作，则结束循环，并向跳跃表中插入一个高度为 n 的列。

3.3 跳跃表的插入

想要插入一个元素到跳跃表中，首先要通过随机算法，获得该元素最终落入的层高。

如上图所示，插入一个元素值为76。

1）随机算法运行【高度等于2 = （高度+1 ）+ （高度+1 ）】

2）查找插入的位置：通过随机算法获得，该元素最高层数是L2

3）插入对应的元素：则从高层往底层处增加该元素的节点

如果通过随机算法获得的层高，高于已有的层数，则添加新的层。如下图所示。

如上图所示，插入一个元素值为89。

1）随机算法运行的状况【高度等于4 = ( 高度+1) + (高度+1 ) + (高度+1）+ (高度+1) 】

2）通过随机算法获得，该元素最高层数是L4

3）则从高层往底层处增加该元素的节点

3.4 跳跃表的删除

如上图所示，将元素89的值删除掉的效果图。

1）删除掉跳跃表中的某一元素，首先找到需要删除的元素，如果没有找到则直接退出

2）如果找到了需要删除的元素，则从高层到低层删该元素，并将多余的 “空链” 删除

四、总结

通过对跳跃表的初步了解，我们目前可以知道。Redis中的跳跃表，是基于单链表抽象出元素作为索引以优化查询效率的。这种方式类似于（二分查找法）其中索引的层高是由随机算法计算所得，Redis中的层高范围是1-32之间的随机数。跳跃表采用了空间换时间的做法，解决了单链表查询慢的缺陷。它每个节点上都有维护一个bw指针，通过该指针可以实现双向链表的反查询效果。在跳跃表中，多个节点的分值是可以重复的，但是每个节点的对象值必须唯一。

五、参考文献

《Redis 设计与实现》

继续滑动看下一个