（Redis篇-5）- Redis的跳表？
2021-09-11 本文已影响0人
Burlong
redis使用跳跃表作为有序集合键的底层实现之一，当一个有序集合包含的元素数量比较多时，redis会使用跳表结构对查询效率进行优化。
与常规链表的不同之处
redis的跳表与常规跳表不同的地方在于
- score值可以重复，即多个不同member可以存储相同的score值，因此确定一个元素需要检查score和member
- 每个节点会携带一个后退指针
redis中的跳表两个关键struct-结构体
1、zskipList
c语言代码示例：
typedef struct zskiplist {
// 头节点，尾节点
struct zskiplistNode *header, *tail;
// 节点数量
unsigned long length;
// 目前表内节点的最大层数
int level;
} zskiplist;
属性：
- header：头指针
- tail：尾指针
- evel：记录当前跳表中所有节点中最大的层数。
- length：记录跳表长度，即节点数量（注意，不包含表头节点）
2、zskiplistNode
c语言代码示例：
typedef struct zskiplistNode {
// member 对象
robj *obj;
// 分值
double score;
// 后退指针
struct zskiplistNode *backward;
// 层
struct zskiplistLevel {
// 前进指针
struct zskiplistNode *forward;
// 这个层跨越的节点数量
unsigned int span;
} level[];
} zskiplistNode;
属性：
-
层（levelN）
1、L1、L2。。LN表示第N层，每一层都会带两个属性：前进指针与跨度。前进指针指向后面的其他节点，而跨度则表示离后面节点的距离。如第一张图中的箭头，表示前进指针，上面的数字则是跨度。
2、在创建一个新跳表时，程序会根据幂次定律(powerlaw,越大的数出现的概率越小)随机生成一个介于1～32的值作为level数组大小，这个大小就是层的“高度”。
-
后退指针（backward）
每个节点维护一个后退指针，因只有一个指针，意味着节点最多一次只能后退一个节点。（个人理解，由于一个节点会有多个指向后续节点的指针，但只有一个后退指针，所以不可认为是双向链表。）
-
分值（score）
各个节点根据该值进行排序
-
成员对象（obj）
节点所存的成员对象。在同个跳表中，各节点存的成员对象必须唯一，但不同节点可以保存相同的分值score（意味着匹配节点时除了匹配score还要匹配对象），在分值相同时，会比较对象大小，小的排在前面。
两个数据结构的各个API的时间复杂度一览
image.png
应用
redis中跳表唯一的应用就是用来实现有序集数据类型。
如下，创建一个带3个元素的有序集：
redis> ZADD s 6 x 10 y 15 z
(integer) 3
redis> ZRANGE s 0 -1 WITHSCORES
1) "x"
2) "6"
3) "y"
4) "10"
5) "z"
6) "15"
在redis中则会映射出这样一个跳表
image.png
注：图中的score值实际只存储了指针，由于要跟另一个实现有序集的结构（字典）分享，真实值是不存储于节点中的。
总结：
- redis跳表基于单链表加索引的数据结构进行实现，本质上是空间换时间
- 指在有序集合节点元素较大或者元素较多时会用跳表实现
- 两个核心数据结构：zskiplist和zskipnode
- redis每个跳跃表节点层高在1～32之间
- 不同节点分值可以相同，但对象必然不同，因此在查找匹配对象时，除了匹配score还要匹配对象。
参考：
