Redis 跳跃表

基本概念

跳跃表是有序集合的底层表现之一

Redis使用跳跃表作为有序集合键的底层实现之一,如果一个有序集合包含的元素数量比较多,又或者有序集合中元素的成员是比较长的字符串时, Redis就会使用跳跃表来作为有序集合健的底层实现。

跳跃表(skiplist)是一种****有序数据结构****，它通过在****每个节点中维持多个指向其他节点的指针(注：可以理解为维护了多条路径)，从而达到快速访问节点的目的。****

Redis的跳跃表由****redis.h/zskiplistNode和redis.h/zskiplist****两个结构定义，其中zskiplistNode结构用于表示跳跃表节点，而zskiplist结构则用于保存跳跃表节点的相关信息，比如节点的数量，以及指向表头节点和表尾节点的指针等等。

实际是一个由层数概念的双向链表。

组成

头节点 尾节点 记录长度 层数

1、 表头head：负责维护跳跃表的节点指针

2、 节点node：实际保存元素值，每个节点有一层或多层

3、 层level：保存着指向该层下一个节点的指针

4、 表尾tail：全部由null组成

跳跃表的遍历总是从高层开始，然后随着元素值范围的缩小，慢慢降低到低层。

添加元素

每一个节点都有层数的概念

层数是通过插入前的随机数来判断的（可以理解为生成一个0-1的随机数，如果小于0.25当前节点层数加一，并且有机会再进行一个随机数，通过多次随机可以获得节点的层数）

最下面一层是双向链表 其他层都是单向链表

每个节点还需要维护一个数字记录着当前节点在当前层中距离下一个节点的距离。

zadd test 3 a 6 b 8 c 4 d

更新元素

比如zadd test 7 b

实际上 b已经存在 但是位置不是在7上

zset是使用另一个字典去存储member和score的映射

如果进行更新 就先找到该节点

首先新 旧 分数不同 6 ！= 7

再判断新分数是否仍然处于在之前节点和前后节点区间之中。

7仍然是大于4 小于8 直接更新分数6变成7即可

但是如果不在这个区间之中 比如指令是

zadd test 9 b

9不在4 - 8区间之中，那么这次的命令就会变成删除加新增

先把当前节点删除 然后使用新的分数插入一个新的节点

查询

比如查询 4b

先从最上层头节点向后查 发现在头节点和6b之间 到下一层 发现这层没有

再到下一层 到了底层的双向链表 就能找到了4b

删除

• 先进行查询操作，找到这个数字
• 将其及索引进行删除 层数也会被删除

时间复杂度

如果按照标准的跳表来看的话，每一级索引减少k/2个元素（k为其下面一级索引的个数），那么整个跳表的高度就是(log n)。 时间复杂度也就是O(logn)

空间复杂度为O（n）

总结

(1)跳跃表的每一层都是一条有序的链表。

(2)维护了多条节点路径。

(3)最底层的链表包含所有元素。+

(4)跳跃表的空间复杂度为 O(n)。

(5)跳跃表支持平均O(logN)、最坏O(N)复杂度的节点查找，还可以通过顺序性操作来批量处理节点。

在大部分情况下，跳跃表的效率可以和平衡树相媲美，并且因为跳跃表的实现比平衡树要来得更为简单，所以有不少程序都使用跳跃表来代替平衡树。

为什么使用跳表而不是红黑树

• 插入元素
• 删除元素
• 查找元素
• 有序输出所有元素
• 查找区间内所有元素

前四项红黑树都可以完成，且时间复杂度与跳表一致

但是，最后一项，红黑树就不如跳表查询的快

在跳表中，要查找区间的元素，我们只要定位到两个区间端点在最低层级的位置，然后按顺序遍历元素就可以了，非常高效。

而红黑树只能定位到端点后，再从首位置开始每次都要查找后继节点，相对来说是比较耗时的。

跳表实现起来很容易且易读，红黑树实现起来相对困难，所以Redis选择使用跳表来实现有序集合。