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源码解析(支持范围查询)
跳表是一个多层的有序链表,在跳表中进行查询操作时,查询代码可以从最高层开始查询。层数越高,结点数越少,同时高层结点的跨度会比较大。因此,在高层查询结点时,查询一个结点可能就已经查到了链表的中间位置…...

MVSNeRF:多视图立体视觉的快速推广辐射场重建(2021年)
MVSNeRF:多视图立体视觉的快速推广辐射场重建(2021年) 摘要1 引言2 相关工作3 MVSNeRF实现方法3.1 构建代价体3.2 辐射场的重建3.3 体渲染和端到端训练 3.4 优化神经编码体 Anpei Chen and Zexiang Xu and Fuqiang Zhao et al. MVSNeRF: Fast…...
华为OD机试真题-CPU算力分配-2023年OD统一考试(C卷)
题目描述: 现有两组服务器A和B,每组有多个算力不同的CPU,其中A[i]是A组第i个CPU的运算能力,B[i]是B组第i个CPU的运算能力。一组服务器的总算力是各CPU的算力之和。为了让两组服务器的算力相等,允许从每组各选出一个CPU进行一次交换,求两组服务器中,用于交换的CPU的算力,…...
校验数据是否重叠(各种操作符>,<,>=,<=,or,and)
最近接到一个需求,其中部分功能涉及到数据的重叠校验,并且录入的数据需要包含各种操作符。如果只通过java代码来查询并进行循环判断的话,判断情况会很复杂,幸好有同事的帮忙提供了一个用sql查询重叠部分的方法,现在分享…...
大一C语言作业 12.8
1.C 对一维数组初始化时,如果全部元素都赋了初值,可以省略数组长度。 这里没有指定数组长度,编译器会根据初始化列表的元素个数来确定数组长度。 2.C 在C语言中,字符数组是不能用赋值运算符直接赋值的。 3.C 在二维数组a中&#x…...

ELasticsearch:什么是语义搜索?
语义搜索定义 语义搜索是一种解释单词和短语含义的搜索引擎技术。 语义搜索的结果将返回与查询含义匹配的内容,而不是与查询中的单词字面匹配的内容。 语义搜索是一组搜索引擎功能,其中包括根据搜索者的意图及其搜索上下文理解单词。 此类搜索旨在通过…...

ooTD I 女儿是自己的,尽情打扮尽情可爱
分享女宝的时尚穿搭 奶乎乎的黄色也太好看了 超足充绒量+优质面料 柔软蓬松上身体验感超赞 怎么穿都好看系列 轻轻松松打造时尚造型!!...
第62天:django学习(十一)
cookie和session 发展史 一开始,只有一个页面,没有登录功能,大家看到东西都一样。 时代发展,出现了需要登录注册的网站,要有一门技术存储我们的登录信息,于是cookie诞生了。 cookie: - 存储形式:k:v键值对…...

Rust测试字符串的移动,Move
代码创建了一个结构体,结构体有test1 字符串,还有指向字符串的指针。一共创建了两个。 然后我们使用swap 函数 交换两个结构体内存的内容。 最后如上图。相同的地址,变成了另外结构体的内容。注意看指针部分,还是指向原来的地址…...

vue+electron问题汇总
1. Vue_Bug Failed to fetch extension, trying 4 more times 描述:项目启动时报错 解决:注释图片中内容 2. Module not found: Error: Can’t resolve ‘fs’ in 描述:项目启动报错 解决:vue.config.js中添加图中数据 3.导入…...

Linux中的网络时间服务器
本章主要介绍网络时间的服务器 使用chrony配置时间服务器配置chrony客户端服务器同步时间 1.1 时间同步的重要性 一些服务对时间要求非常严格,例如如图所示的由三台服务器搭建的ceph集群 这三台服务器的时间必须保持一致,如果不一致,就会显…...

fastadmin打印页面
如下图选中订单号进行打印 html中增加代码 <div id"toolbar" class"toolbar"><a href"javascript:;" class"btn btn-primary btn-refresh" title"{:__(Refresh)}" ><i class"fa fa-refresh">&l…...

Java 将word转为PDF的三种方式和处理在服务器上下载后乱码的格式
我这边是因为业务需要将之前导出的word文档转换为PDF文件,然后页面预览下载这样的情况。之前导出word文档又不是我做的,所以为了不影响业务,只是将最后在输出流时转换成了PDF,当时本地调用没什么问题,一切正常…...
C\C++ 获取最值
C C 语言的不同类型的最值可以在 limits.h 头文件里找到定义 #include <limits.h>int main() {printf("%d", INT_MAX); // 整数最大值printf("%d", INT_MIN); // 整数最小值 } C C 有模板,可以通过替换下面的 int 和 doubleÿ…...

机器学习之无监督学习:九大聚类算法
今天,和大家分享一下机器学习之无监督学习中的常见的聚类方法。 今天,和大家分享一下机器学习之无监督学习中的常见的聚类方法。 在无监督学习中,我们的数据并不带有任何标签,因此在无监督学习中要做的就是将这一系列无标签的数…...

Linux高级管理-搭建网站服务
在Ihternet 网络环境中,Web 服务无疑是最为流行的应用系统。有了Web站点,企业可以充分 展示自己的产品,宣传企业形象。Web站点还为企业提供了与客户交流、电子商务交易平台等丰富 的网络应用。部署与维护Web 服务是运维工程师必须掌握的一个技…...

Windows 系统,TortoiseSVN 无法修改 Log 信息解决方法
使用SVN提交版本信息时,注释内容写的不全。通过右键TortoiseSVN的Show log看到提交的的注释,右键看到Edit log message的选项,然而提交后却给出错误提示: Repository has not been enabled to accept revision propchanges; ask …...

编译 Android gradle-4.6-all.zip 报错问题记录
编译 Android gradle-4.6-all.zip 报错问题记录 方法一:替换资源:方法二:修改源方法三:修改版本 编译时候无法下载 gradle-4.6-all Downloading https://services.gradle.org/distributions/gradle-4.6-all.zip 方法一…...

Linux系统调试课:Valgrind 内存调试
文章目录 一、为什么要学会Valgrind二、什么是内存泄露三、Valgrind的移植四、Valgrind相关参数沉淀、分享、成长,让自己和他人都能有所收获!😄 📢Valgrind 是一个开源的内存调试和性能分析工具,用于帮助开发者找出程序中的内存错误,如内存泄漏、使用未初始化的内存、非…...

python主流开发工具排名,python开发工具有哪些
本篇文章给大家谈谈python的开发工具软件有哪些,以及python主流开发工具排名,希望对各位有所帮助,不要忘了收藏本站喔。 python中用到哪些软件 一、Python代码编辑器1、sublime Textsublime Text是一款非常流行的代码编辑器,支持P…...
HTML 语义化
目录 HTML 语义化HTML5 新特性HTML 语义化的好处语义化标签的使用场景最佳实践 HTML 语义化 HTML5 新特性 标准答案: 语义化标签: <header>:页头<nav>:导航<main>:主要内容<article>&#x…...

7.4.分块查找
一.分块查找的算法思想: 1.实例: 以上述图片的顺序表为例, 该顺序表的数据元素从整体来看是乱序的,但如果把这些数据元素分成一块一块的小区间, 第一个区间[0,1]索引上的数据元素都是小于等于10的, 第二…...
应用升级/灾备测试时使用guarantee 闪回点迅速回退
1.场景 应用要升级,当升级失败时,数据库回退到升级前. 要测试系统,测试完成后,数据库要回退到测试前。 相对于RMAN恢复需要很长时间, 数据库闪回只需要几分钟。 2.技术实现 数据库设置 2个db_recovery参数 创建guarantee闪回点,不需要开启数据库闪回。…...

Zustand 状态管理库:极简而强大的解决方案
Zustand 是一个轻量级、快速和可扩展的状态管理库,特别适合 React 应用。它以简洁的 API 和高效的性能解决了 Redux 等状态管理方案中的繁琐问题。 核心优势对比 基本使用指南 1. 创建 Store // store.js import create from zustandconst useStore create((set)…...
Spring Boot 实现流式响应(兼容 2.7.x)
在实际开发中,我们可能会遇到一些流式数据处理的场景,比如接收来自上游接口的 Server-Sent Events(SSE) 或 流式 JSON 内容,并将其原样中转给前端页面或客户端。这种情况下,传统的 RestTemplate 缓存机制会…...

解决Ubuntu22.04 VMware失败的问题 ubuntu入门之二十八
现象1 打开VMware失败 Ubuntu升级之后打开VMware上报需要安装vmmon和vmnet,点击确认后如下提示 最终上报fail 解决方法 内核升级导致,需要在新内核下重新下载编译安装 查看版本 $ vmware -v VMware Workstation 17.5.1 build-23298084$ lsb_release…...
Linux简单的操作
ls ls 查看当前目录 ll 查看详细内容 ls -a 查看所有的内容 ls --help 查看方法文档 pwd pwd 查看当前路径 cd cd 转路径 cd .. 转上一级路径 cd 名 转换路径 …...
Auto-Coder使用GPT-4o完成:在用TabPFN这个模型构建一个预测未来3天涨跌的分类任务
通过akshare库,获取股票数据,并生成TabPFN这个模型 可以识别、处理的格式,写一个完整的预处理示例,并构建一个预测未来 3 天股价涨跌的分类任务 用TabPFN这个模型构建一个预测未来 3 天股价涨跌的分类任务,进行预测并输…...

论文浅尝 | 基于判别指令微调生成式大语言模型的知识图谱补全方法(ISWC2024)
笔记整理:刘治强,浙江大学硕士生,研究方向为知识图谱表示学习,大语言模型 论文链接:http://arxiv.org/abs/2407.16127 发表会议:ISWC 2024 1. 动机 传统的知识图谱补全(KGC)模型通过…...

微服务商城-商品微服务
数据表 CREATE TABLE product (id bigint(20) UNSIGNED NOT NULL AUTO_INCREMENT COMMENT 商品id,cateid smallint(6) UNSIGNED NOT NULL DEFAULT 0 COMMENT 类别Id,name varchar(100) NOT NULL DEFAULT COMMENT 商品名称,subtitle varchar(200) NOT NULL DEFAULT COMMENT 商…...