当前位置: 首页 > news >正文

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源码解析(支持范围查询)

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

MVSNeRF:多视图立体视觉的快速推广辐射场重建(2021年)

MVSNeRF&#xff1a;多视图立体视觉的快速推广辐射场重建&#xff08;2021年&#xff09; 摘要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)

最近接到一个需求&#xff0c;其中部分功能涉及到数据的重叠校验&#xff0c;并且录入的数据需要包含各种操作符。如果只通过java代码来查询并进行循环判断的话&#xff0c;判断情况会很复杂&#xff0c;幸好有同事的帮忙提供了一个用sql查询重叠部分的方法&#xff0c;现在分享…...

大一C语言作业 12.8

1.C 对一维数组初始化时&#xff0c;如果全部元素都赋了初值&#xff0c;可以省略数组长度。 这里没有指定数组长度&#xff0c;编译器会根据初始化列表的元素个数来确定数组长度。 2.C 在C语言中&#xff0c;字符数组是不能用赋值运算符直接赋值的。 3.C 在二维数组a中&#x…...

ELasticsearch:什么是语义搜索?

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

ooTD I 女儿是自己的,尽情打扮尽情可爱

分享女宝的时尚穿搭 奶乎乎的黄色也太好看了 超足充绒量&#xff0b;优质面料 柔软蓬松上身体验感超赞 怎么穿都好看系列 轻轻松松打造时尚造型&#xff01;&#xff01;...

第62天:django学习(十一)

cookie和session 发展史 一开始,只有一个页面&#xff0c;没有登录功能&#xff0c;大家看到东西都一样。 时代发展&#xff0c;出现了需要登录注册的网站&#xff0c;要有一门技术存储我们的登录信息&#xff0c;于是cookie诞生了。 cookie: - 存储形式&#xff1a;k:v键值对…...

Rust测试字符串的移动,Move

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

vue+electron问题汇总

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

Linux中的网络时间服务器

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

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文件&#xff0c;然后页面预览下载这样的情况。之前导出word文档又不是我做的&#xff0c;所以为了不影响业务&#xff0c;只是将最后在输出流时转换成了PDF&#xff0c;当时本地调用没什么问题&#xff0c;一切正常&#xf…...

C\C++ 获取最值

C C 语言的不同类型的最值可以在 limits.h 头文件里找到定义 #include <limits.h>int main() {printf("%d", INT_MAX); // 整数最大值printf("%d", INT_MIN); // 整数最小值 } C C 有模板&#xff0c;可以通过替换下面的 int 和 double&#xff…...

机器学习之无监督学习:九大聚类算法

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

Linux高级管理-搭建网站服务

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

Windows 系统,TortoiseSVN 无法修改 Log 信息解决方法

使用SVN提交版本信息时&#xff0c;注释内容写的不全。通过右键TortoiseSVN的Show log看到提交的的注释&#xff0c;右键看到Edit log message的选项&#xff0c;然而提交后却给出错误提示&#xff1a; Repository has not been enabled to accept revision propchanges; ask …...

编译 Android gradle-4.6-all.zip 报错问题记录

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

Linux系统调试课:Valgrind 内存调试

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

python主流开发工具排名,python开发工具有哪些

本篇文章给大家谈谈python的开发工具软件有哪些&#xff0c;以及python主流开发工具排名&#xff0c;希望对各位有所帮助&#xff0c;不要忘了收藏本站喔。 python中用到哪些软件 一、Python代码编辑器1、sublime Textsublime Text是一款非常流行的代码编辑器&#xff0c;支持P…...

阿里云ACP云计算备考笔记 (5)——弹性伸缩

目录 第一章 概述 第二章 弹性伸缩简介 1、弹性伸缩 2、垂直伸缩 3、优势 4、应用场景 ① 无规律的业务量波动 ② 有规律的业务量波动 ③ 无明显业务量波动 ④ 混合型业务 ⑤ 消息通知 ⑥ 生命周期挂钩 ⑦ 自定义方式 ⑧ 滚的升级 5、使用限制 第三章 主要定义 …...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院挂号小程序

一、开发准备 ​​环境搭建​​&#xff1a; 安装DevEco Studio 3.0或更高版本配置HarmonyOS SDK申请开发者账号 ​​项目创建​​&#xff1a; File > New > Create Project > Application (选择"Empty Ability") 二、核心功能实现 1. 医院科室展示 /…...

【算法训练营Day07】字符串part1

文章目录 反转字符串反转字符串II替换数字 反转字符串 题目链接&#xff1a;344. 反转字符串 双指针法&#xff0c;两个指针的元素直接调转即可 class Solution {public void reverseString(char[] s) {int head 0;int end s.length - 1;while(head < end) {char temp …...

Module Federation 和 Native Federation 的比较

前言 Module Federation 是 Webpack 5 引入的微前端架构方案&#xff0c;允许不同独立构建的应用在运行时动态共享模块。 Native Federation 是 Angular 官方基于 Module Federation 理念实现的专为 Angular 优化的微前端方案。 概念解析 Module Federation (模块联邦) Modul…...

JDK 17 新特性

#JDK 17 新特性 /**************** 文本块 *****************/ python/scala中早就支持&#xff0c;不稀奇 String json “”" { “name”: “Java”, “version”: 17 } “”"; /**************** Switch 语句 -> 表达式 *****************/ 挺好的&#xff…...

OPenCV CUDA模块图像处理-----对图像执行 均值漂移滤波(Mean Shift Filtering)函数meanShiftFiltering()

操作系统&#xff1a;ubuntu22.04 OpenCV版本&#xff1a;OpenCV4.9 IDE:Visual Studio Code 编程语言&#xff1a;C11 算法描述 在 GPU 上对图像执行 均值漂移滤波&#xff08;Mean Shift Filtering&#xff09;&#xff0c;用于图像分割或平滑处理。 该函数将输入图像中的…...

Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决

Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决 问题背景 在一个基于 Spring Cloud Gateway WebFlux 构建的微服务项目中&#xff0c;新增了一个本地验证码接口 /code&#xff0c;使用函数式路由&#xff08;RouterFunction&#xff09;和 Hutool 的 Circle…...

七、数据库的完整性

七、数据库的完整性 主要内容 7.1 数据库的完整性概述 7.2 实体完整性 7.3 参照完整性 7.4 用户定义的完整性 7.5 触发器 7.6 SQL Server中数据库完整性的实现 7.7 小结 7.1 数据库的完整性概述 数据库完整性的含义 正确性 指数据的合法性 有效性 指数据是否属于所定…...

Golang——6、指针和结构体

指针和结构体 1、指针1.1、指针地址和指针类型1.2、指针取值1.3、new和make 2、结构体2.1、type关键字的使用2.2、结构体的定义和初始化2.3、结构体方法和接收者2.4、给任意类型添加方法2.5、结构体的匿名字段2.6、嵌套结构体2.7、嵌套匿名结构体2.8、结构体的继承 3、结构体与…...

Android写一个捕获全局异常的工具类

项目开发和实际运行过程中难免会遇到异常发生&#xff0c;系统提供了一个可以捕获全局异常的工具Uncaughtexceptionhandler&#xff0c;它是Thread的子类&#xff08;就是package java.lang;里线程的Thread&#xff09;。本文将利用它将设备信息、报错信息以及错误的发生时间都…...