(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还要匹配对象。
参考: