Redis(四)跳跃表

跳跃表是一种有序数据结构，通过在每个节点中维持多个指向其他节点的指针，从而达到快速访问节点的目的。支持平均O(logN)、最坏O(N)复杂度的节点查找，还可以通过顺序性操作来批处理节点，跳跃表所有操作时间复杂度平均都是O(logN)。

跳表是可以实现二分查找的有序链表。

跳跃表效率可以和平衡树相媲美，并且跳跃表实现更为简单，所以不少程序都用跳跃表代替平衡树。和链表、字典等数据结构广泛应用在Redis内部不同，Redis只有在两个地方用到了跳跃表，一个是实现有序集合键，另一个是在集群节点中作为内部数据结构。

为什么Redis使用跳表而不使用红黑树来实现有序集合？

Redis有序集合支持插入、删除、查找、有序输出所有元素、按照范围区间查找元素。

前面四个操作跳跃表和红黑树的时间复杂度一样，但是按照范围区间查找数据这个操作，红黑树的效率没有跳表高。按照区间查找数据时，跳表可以做到 O(logn) 的时间复杂度定位区间的起点，然后在原始链表中顺序往后遍历就可以了，非常高效。

另外红黑树的实现相比与跳跃表也更加复杂。

1、跳跃表的实现

Redis的跳跃表由两个结构定义，其中zskiplistNode结构用于表示跳跃表节点，而zskiplist结构保存跳跃表节点相关信息。

位于图最左边是zskiplist结构，包含以下属性：

• header：指向跳跃表的表头节点。
• tail：指向跳跃表的表尾节点。
• level：记录目前跳跃表内，层数最大那个节点的层数。
• length：记录跳跃表的长度

右边有四个zskiplistNode结构，包含以下属性：

• 层level：节点用L1、L2、L3等字样标记节点的各个层。每个层都有两个属性：前进指针和跨度。上图分别用连线和连线上的数字表示。
• 后退指针backward：节点中用BW字样标记节点的后退指针，指向当前节点的前一个节点。在程序从表尾向表头遍历是使用。
• 分值score：各节点中的1.0、2.0、3.0是节点所保存的分值。
• 成员对象obj：各节点中o1、o2和o3是节点所保存的成员对象。

注意：表头节点和其他节点构造一样，也有后退指针、分值和成员对象，不过由于不会用到，所以图中进行了省略。

跳跃表节点

跳跃表节点结构体定义：

• 层

level数组可以包含多个元素，每个元素都包含一个指向其他节点的指针，程序可以通过这些层来加快访问其他节点的速度，一般层数越多，访问其他节点的速度越快。每次创建新跳跃表节点时，程序都会根据幂次定律随机生成一个介于1和32之间的值作为level数组的大小，称为层的高度。

• 前进指针

每个层都有一个指向表尾方向的前进指针(level[i].forward属性),用于从表头向表尾方向访问节点。

• 跨度

层的跨度(level[i].span属性)用于记录两个节点之间的距离：

1. 两个节点之间跨度越大，相距越远。
2. 指向null的所有前进指针的跨度都为0。

跨度实际上是用来计算排位(rank)的：在查找某个节点的过程中，将沿途访问过的所有层的跨度累计起来，结果就是目标节点在跳跃表中的排位。

• 后退指针

节点的后退指针用于从表尾向表头方向访问节点：每个节点只有一个后退指针，所以每次只能后退至前一个节点。

• 分值和成员

节点的分值是一个double类型的浮点数，所有节点按分值从小到大排序。

节点的成员对象是一个指针，指向一个字符串对象，而字符串对象保存着SDS值。

注意：同一跳跃表中，各节点成员对象必须唯一，分值可以相同。分值相同的节点按照成员对象在字典序中大小进行排序，成员对象较小的节点会靠近表头。

跳跃表

zskiplist结构定义如下：

重点回顾