Redis数据结构之跳跃表 (2)

每一个节点的层数都是随机算法得出的，插入一个新的节点不会影响其他节点的层数，因此，插入操作只需要修改插入节点前后的指针即可，避免了对后续节点的重新调整。这是跳表的一个很重要的特性，也是跳表性能明显由于平衡树的原因，因为平衡树在失去平衡之后也需要进行平衡调整。

上图最后的跳表中，我们需要查找节点22，则遍历到的节点依次是：7->37->19->22，可见，这种随机层数的跳表的查找时可能没有2:1结构的效率，但是却解决了插入/删除节点的问题。

2.3、跳表的复杂度

跳表搜索的时间复杂度平均 O(logN)，最坏O(N)，空间复杂度O(2N)，即O(N)

3、Redis中的跳表

在理解 Redis 的跳跃表之前，我们先回忆一下 Redis 的有序集合（sorted set）操作

不重复但有序的字符串元素集合；

每个元素均关联一个double类型的score，Redis 根据score进行从小到大排序；

score可以重复，重复的按照插入顺序进行排序；

示例如下：

redis 127.0.0.1:6379> ZADD runoobkey 1 redis (integer) 1 redis 127.0.0.1:6379> ZADD runoobkey 2 mongodb (integer) 1 redis 127.0.0.1:6379> ZADD runoobkey 3 mysql (integer) 1 redis 127.0.0.1:6379> ZADD runoobkey 3 mysql (integer) 0 redis 127.0.0.1:6379> ZADD runoobkey 4 mysql (integer) 0 redis 127.0.0.1:6379> ZRANGE runoobkey 0 10 WITHSCORES "redis" "1" "mongodb" "2" "mysql" "4"

这个是 Redis 中的有序列表的基本操作，我们答题可以看出，在有序列表中，有一个浮点数作为 score， 当对应一个值，可以根据 score 精确查找和范围查找，且效率很高

Redis 里面的这种操作的底层实现就是跳表。

上面理解了跳表，再去看 Redis 中的跳表就轻松多了，跳表的实现在 Redis 源码目录下 redis.h 文件中

3.1、zskiplistNode

zskiplistNode 表示跳表的一个节点，声明如下：

typedef struct zskiplistNode { robj *obj; double score; struct zskiplistNode *backward; struct zskiplistLevel { struct zskiplistNode *forward; unsigned int span; } level[]; } zskiplistNode;

robj 类型是 Redis 中用C语言实现一种集合数据结构，它可以表示 string、hash、list、set 和 zset 五种数据类型，这里不做详细说明，在跳表节点中，这个类型的指针表示节点的成员对象

score 表示分值，用于排序和范围查找

level 是一个柔性数组，它表示节点的层级，每层都有一个前进指针 forward，用于指向相同层级指向表尾方向的下一个节点，而 span 则表示当前节点在当前层级中距离下一个节点的跨度，即两个节点之间的距离。

初看上去，很容易以为跨度和遍历节点有关，实际并不是，遍历操作只用前进指针就够了，跨度是用来计算排位（rank）的：在查找某个节点的过程中，沿途访问过的所有层的跨度累计起来，就是目标节点在跳表中的排位。

下图中，查找成员o3，只经历了一层，排位为3

在 Redis 中，每个节点的层级都是根据幂次定律（power law，越大的树出现的概率越小）随机生成的，它是1~32之间的一个数，作为level数组的大小，即高度

下图分别展示了三个高度为1、3、5层的节点

backward 是一个后退指针，每个节点都有一个，指向当前节点的表头方向的下一个节点，用于从表尾进行遍历

3.2、zskiplist

zskiplist 表示一个跳表，声明如下：

typedef struct zskiplist { struct zskiplistNode *header, *tail; unsigned long length; int level; } zskiplist;

header 和 tail 指针分别指向表头和表尾节点

length 记录了节点数量

level 记录了所有节点中层级最高的节点的层级，表头节点的层高不计算在内

下图是一个跳表的示例，最左侧是一个 zskiplist 结构，其右侧是四个 zskiplistNode 节点，从左向右分别有32层、4层、2层、5层。每个节点向右的指针即前进指针 forward， BW 则表示后退指针 backward，每个节点依据节点的分值 score 进行排列