Redis跳表

作为Redis对象中特别重要的ZSet的底层实现原理，理解跳表特别重要。那么我们接下来来介绍一下跳表；

1.什么是跳表

跳表的本质还是链表，普通链表的结构如下所示:

这种结构虽然简单清晰，但是查询某个节点的效率比较低，而在有序集合场景，无论是查找还是添加删除元素，我们是需要能快速通过score定位到具体位置，如果用链表那时间复杂度其实就是O(N)，N是节点个数。为了提升查找的性能，Redis就引入了跳表，跳表在链表的基础上，给链表增加了多级的索引，通过索引可以一次实现多个节点的跳跃，提高性能。

跳跃表是一种支持多级索引的结构，查询效率可以媲美二分查找，它插入一条数据也是需要先查找，找到之后会进行索引的重建，整体平均时间复杂度是O(logN)

2.跳表的结构

可以看到，这个图某些节点不光只有一层，如果只用普通链表，只能一步一步往后走，如果用这种有高层的节点，那是不是可以一次多走几步，理论上，层次越高平均步长越大，但并不完全像示意图一样是绝对均衡的，节点的层高其实是概率随机的。为了理解这个结构有什么好处，我们分几个场景来分析

场景一:查找分数为45的数据
如果只有原始的链表，那需要走4步，如果有图中的二级索引，只用走2步，那如果找45呢，其实就是从第1个节点出发，通过二级索引走到35，再查看到下一个节点是65，已经超过了，所以降低到下方的索引，也就是一级索引，往后走一次就可以找到45。

由此可见，跳表的查找过程为从高级索引往后查找，如果下个节点的数值比目标节点小，则继续找，否则不跳过去，而是用下级索引往下找。

场景二:插入一条score为36的数据

首先，定位到第一个比score大的位置，这里是45，定位方式和查询类似.然后，构造一个新的节点，这里我们假设节点层高随机到3，最后，将各层链表补齐，其实就是在每一层进行链接，效果如图

标准的跳表有如下限制:

1. score值不能重复
2. 只有向前的指针，没有回退的指针；

但是Redis并不是标准的跳表，上面的两个限制都不存在；它的最下面一层就是双向链表

/* ZSETs use a specialized version of SkipLists */ typedef struct zskiplistNode { sds ele; double score; struct zskiplistNode *backward; struct zskiplistLevel { struct zskiplistNode *forward; unsigned long span; } level[]; } zskiplistNode;

我们现在来看一下字段的含义:

• ele:很熟悉的SDS结构，用来存储数据。
• score:节点的分数，从小到大排序，浮点型数据，是节点排序的重要指标
• backward:指向上一个节点的回退指针，支持从表尾向表头遍历，也就是ZREVRANGE命
• level:是个zskiplistLevel结构体数组，zskiplistLevel这个结构体包含了两个字段，一个是forward，指向该层下个能跳到的节点，span记录了距离下个节点的步数，是站在最底下的数据节点的角度来看的。数组结构就表示每个节点都可能是个多层结构。

那么，Redis跳表单个节点有几层呢?

层次的决定，需要比较随机，才能在各个场景表现出较为平均的性能，这里Redis使用概率均衡的思路来确定新插入节点的层数:Redis跳表决定每一个节点，是否能增加一层的概率为25%，而最大层数限制在Redis 5.0是64层，在Redis7.0是32层。

简而言之。每个节点在创建时会随机得到一个层数（Redis7.0是1到32层），层数越高的节点越少。插入时，新节点总是放在最底层，然后根据它的随机层数，把对应层的指针连接到跳表中。高层节点就像“快速通道”，可以跳过许多节点，使得查找效率很高，同时又很简单高效。

因此跳表插入数据不会影响其它节点层高，因为节点层高在创建时就确认了，不会被新插入的节点影响。新插入的节点只会影响每一层前一跳，后一跳的关联指针。

声明: 本篇笔记仅为学习时整理的笔记以及疑问解决点，无其他任何商业用途，如有侵权联系即删。