Redis skiplist源码解析(支持范围查询)

2023-12-05 08:45

本文主要是介绍Redis skiplist源码解析(支持范围查询),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

跳表是一个多层的有序链表,在跳表中进行查询操作时,查询代码可以从最高层开始查询。层数越高,结点数越少,同时高层结点的跨度会比较大。因此,在高层查询结点时,查询一个结点可能就已经查到了链表的中间位置了。

这样一来,跳表就会先查高层,如果高层直接查到了等于待查元素的结点,那么就可以直接返回。如果查到第一个大于待查元素的结点后,就转向下一层查询。下层上的结点数多于上层,所以这样可以在更多的结点中进一步查找待查元素是否存在。

跳表的这种设计方法就可以节省查询开销,同时,跳表设计采用随机的方法来确定每个结点的层数,这样就可以避免新增结点时,引起结点连锁更新问题。

有些拗口,详细掰掰。

基础数据结构

zskiplist是一个多层的有序列表,是一个双向链表。

zskiplistNode:代表zskiplist里的每一个节点,包含了对象权重,权重越大越往后插入。

zskiplistLevel代表索引层级,每一层就是一个zskiplistLevel,插入时会采用随机分层方式决定当前元素插入到那一层去,或者直接加入一层。跨度是决定在当前层还要根据当前指针来计算还要跨过多少元素才可以插入。

/* ZSETs use a specialized version of Skiplists */
/** 跳跃表节点*/
typedef struct zskiplistNode {// 成员对象robj *obj;// 分值double score;// 后退指针struct zskiplistNode *backward;// 层struct zskiplistLevel {// 前进指针struct zskiplistNode *forward;// 跨度unsigned int span;} level[];} zskiplistNode;/** 跳跃表*/
typedef struct zskiplist {// 表头节点和表尾节点struct zskiplistNode *header, *tail;// 表中节点的数量unsigned long length;// 表中层数最大的节点的层数int level;} zskiplist;

查询元素过程(level->score->sds)

level层: 从头节点开始直接从层级最高的地方开始由上往下查询。

score权重:同一层比较的就是score大小,score越大越往后。

sds数据:发生score相等的场景,这个时候就会比较数据的大小。

zskiplistNode *zslFirstInRange(zskiplist *zsl, zrangespec *range) {zskiplistNode *x;int i;/* If everything is out of range, return early. */if (!zslIsInRange(zsl,range)) return NULL;// 遍历跳跃表,查找符合范围 min 项的节点// T_wrost = O(N), T_avg = O(log N)x = zsl->header;for (i = zsl->level-1; i >= 0; i--) {/* Go forward while *OUT* of range. */while (x->level[i].forward &&!zslValueGteMin(x->level[i].forward->score,range))x = x->level[i].forward;}/* This is an inner range, so the next node cannot be NULL. */x = x->level[0].forward;redisAssert(x != NULL);/* Check if score <= max. */// 检查节点是否符合范围的 max 项// T = O(1)if (!zslValueLteMax(x->score,range)) return NULL;return x;
}/** 检测给定值 value 是否大于(或大于等于)范围 spec 中的 min 项。** 返回 1 表示 value 大于等于 min 项,否则返回 0 。** T = O(1)*/
static int zslValueGteMin(double value, zrangespec *spec) {return spec->minex ? (value > spec->min) : (value >= spec->min);
}/** 检测给定值 value 是否小于(或小于等于)范围 spec 中的 max 项。** 返回 1 表示 value 小于等于 max 项,否则返回 0 。** T = O(1)*/
static int zslValueLteMax(double value, zrangespec *spec) {return spec->maxex ? (value < spec->max) : (value <= spec->max);
}

插入元素过程

1、层数算法:随机生成每个结点的层数

过程:初始化层数为1,生成一个随机数,如果一个随机数的小于拟定的25%的概率,层数+1,直到拟定的最大层数64为止。

这个算法并不是真正意义上的二分查找法,它永远不会保证上层和下层1:2的比例,同时这个算法可以避免插入删除更新导致连续更新问题(一个元素改后面元素全部需要改),仅仅只需要修改下指针即可。

/* Returns a random level for the new skiplist node we are going to create.** 返回一个随机值,用作新跳跃表节点的层数。** The return value of this function is between 1 and ZSKIPLIST_MAXLEVEL* (both inclusive), with a powerlaw-alike distribution where higher* levels are less likely to be returned. ** 返回值介乎 1 和 ZSKIPLIST_MAXLEVEL 之间(包含 ZSKIPLIST_MAXLEVEL),* 根据随机算法所使用的幂次定律,越大的值生成的几率越小。* ZSKIPLIST_P  指跳表结点增加层数的概率,值为 0.25* T = O(N)*/
int zslRandomLevel(void) {int level = 1;while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF))level += 1;return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}

 插入过程:和查询一样,sds数据从小到大,每一层从小到大,层数也是由小到大。

/* Insert (element,score) pair in ziplist. ** 将 ele 成员和它的分值 score 添加到 ziplist 里面** ziplist 里的各个节点按 score 值从小到大排列** This function assumes the element is not yet present in the list. ** 这个函数假设 elem 不存在于有序集*/
unsigned char *zzlInsert(unsigned char *zl, robj *ele, double score) {// 指向 ziplist 第一个节点(也即是有序集的 member 域)unsigned char *eptr = ziplistIndex(zl,0), *sptr;double s;// 解码值ele = getDecodedObject(ele);// 遍历整个 ziplistwhile (eptr != NULL) {// 取出分值sptr = ziplistNext(zl,eptr);redisAssertWithInfo(NULL,ele,sptr != NULL);s = zzlGetScore(sptr);if (s > score) {/* First element with score larger than score for element to be* inserted. This means we should take its spot in the list to* maintain ordering. */// 遇到第一个 score 值比输入 score 大的节点// 将新节点插入在这个节点的前面,// 让节点在 ziplist 里根据 score 从小到大排列zl = zzlInsertAt(zl,eptr,ele,score);break;} else if (s == score) {/* Ensure lexicographical ordering for elements. */// 如果输入 score 和节点的 score 相同// 那么根据 member 的字符串位置来决定新节点的插入位置if (zzlCompareElements(eptr,ele->ptr,sdslen(ele->ptr)) > 0) {zl = zzlInsertAt(zl,eptr,ele,score);break;}}/* Move to next element. */// 输入 score 比节点的 score 值要大// 移动到下一个节点eptr = ziplistNext(zl,sptr);}/* Push on tail of list when it was not yet inserted. */if (eptr == NULL)zl = zzlInsertAt(zl,NULL,ele,score);decrRefCount(ele);return zl;
}

这篇关于Redis skiplist源码解析(支持范围查询)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/456892

相关文章

SpringCloud动态配置注解@RefreshScope与@Component的深度解析

《SpringCloud动态配置注解@RefreshScope与@Component的深度解析》在现代微服务架构中,动态配置管理是一个关键需求,本文将为大家介绍SpringCloud中相关的注解@Re... 目录引言1. @RefreshScope 的作用与原理1.1 什么是 @RefreshScope1.

Java并发编程必备之Synchronized关键字深入解析

《Java并发编程必备之Synchronized关键字深入解析》本文我们深入探索了Java中的Synchronized关键字,包括其互斥性和可重入性的特性,文章详细介绍了Synchronized的三种... 目录一、前言二、Synchronized关键字2.1 Synchronized的特性1. 互斥2.

SpringKafka消息发布之KafkaTemplate与事务支持功能

《SpringKafka消息发布之KafkaTemplate与事务支持功能》通过本文介绍的基本用法、序列化选项、事务支持、错误处理和性能优化技术,开发者可以构建高效可靠的Kafka消息发布系统,事务支... 目录引言一、KafkaTemplate基础二、消息序列化三、事务支持机制四、错误处理与重试五、性能优

Python实现无痛修改第三方库源码的方法详解

《Python实现无痛修改第三方库源码的方法详解》很多时候,我们下载的第三方库是不会有需求不满足的情况,但也有极少的情况,第三方库没有兼顾到需求,本文将介绍几个修改源码的操作,大家可以根据需求进行选择... 目录需求不符合模拟示例 1. 修改源文件2. 继承修改3. 猴子补丁4. 追踪局部变量需求不符合很

Java的IO模型、Netty原理解析

《Java的IO模型、Netty原理解析》Java的I/O是以流的方式进行数据输入输出的,Java的类库涉及很多领域的IO内容:标准的输入输出,文件的操作、网络上的数据传输流、字符串流、对象流等,这篇... 目录1.什么是IO2.同步与异步、阻塞与非阻塞3.三种IO模型BIO(blocking I/O)NI

Python 中的异步与同步深度解析(实践记录)

《Python中的异步与同步深度解析(实践记录)》在Python编程世界里,异步和同步的概念是理解程序执行流程和性能优化的关键,这篇文章将带你深入了解它们的差异,以及阻塞和非阻塞的特性,同时通过实际... 目录python中的异步与同步:深度解析与实践异步与同步的定义异步同步阻塞与非阻塞的概念阻塞非阻塞同步

浅谈mysql的sql_mode可能会限制你的查询

《浅谈mysql的sql_mode可能会限制你的查询》本文主要介绍了浅谈mysql的sql_mode可能会限制你的查询,这个问题主要说明的是,我们写的sql查询语句违背了聚合函数groupby的规则... 目录场景:问题描述原因分析:解决方案:第一种:修改后,只有当前生效,若是mysql服务重启,就会失效;

MySQL多列IN查询的实现

《MySQL多列IN查询的实现》多列IN查询是一种强大的筛选工具,它允许通过多字段组合快速过滤数据,本文主要介绍了MySQL多列IN查询的实现,具有一定的参考价值,感兴趣的可以了解一下... 目录一、基础语法:多列 IN 的两种写法1. 直接值列表2. 子查询二、对比传统 OR 的写法三、性能分析与优化1.

Redis 中的热点键和数据倾斜示例详解

《Redis中的热点键和数据倾斜示例详解》热点键是指在Redis中被频繁访问的特定键,这些键由于其高访问频率,可能导致Redis服务器的性能问题,尤其是在高并发场景下,本文给大家介绍Redis中的热... 目录Redis 中的热点键和数据倾斜热点键(Hot Key)定义特点应对策略示例数据倾斜(Data S

redis+lua实现分布式限流的示例

《redis+lua实现分布式限流的示例》本文主要介绍了redis+lua实现分布式限流的示例,可以实现复杂的限流逻辑,如滑动窗口限流,并且避免了多步操作导致的并发问题,具有一定的参考价值,感兴趣的可... 目录为什么使用Redis+Lua实现分布式限流使用ZSET也可以实现限流,为什么选择lua的方式实现