当前位置: 首页 > 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…...

【大模型RAG】拍照搜题技术架构速览:三层管道、两级检索、兜底大模型

摘要 拍照搜题系统采用“三层管道&#xff08;多模态 OCR → 语义检索 → 答案渲染&#xff09;、两级检索&#xff08;倒排 BM25 向量 HNSW&#xff09;并以大语言模型兜底”的整体框架&#xff1a; 多模态 OCR 层 将题目图片经过超分、去噪、倾斜校正后&#xff0c;分别用…...

生成xcframework

打包 XCFramework 的方法 XCFramework 是苹果推出的一种多平台二进制分发格式&#xff0c;可以包含多个架构和平台的代码。打包 XCFramework 通常用于分发库或框架。 使用 Xcode 命令行工具打包 通过 xcodebuild 命令可以打包 XCFramework。确保项目已经配置好需要支持的平台…...

【Java学习笔记】Arrays类

Arrays 类 1. 导入包&#xff1a;import java.util.Arrays 2. 常用方法一览表 方法描述Arrays.toString()返回数组的字符串形式Arrays.sort()排序&#xff08;自然排序和定制排序&#xff09;Arrays.binarySearch()通过二分搜索法进行查找&#xff08;前提&#xff1a;数组是…...

大型活动交通拥堵治理的视觉算法应用

大型活动下智慧交通的视觉分析应用 一、背景与挑战 大型活动&#xff08;如演唱会、马拉松赛事、高考中考等&#xff09;期间&#xff0c;城市交通面临瞬时人流车流激增、传统摄像头模糊、交通拥堵识别滞后等问题。以演唱会为例&#xff0c;暖城商圈曾因观众集中离场导致周边…...

Python实现prophet 理论及参数优化

文章目录 Prophet理论及模型参数介绍Python代码完整实现prophet 添加外部数据进行模型优化 之前初步学习prophet的时候&#xff0c;写过一篇简单实现&#xff0c;后期随着对该模型的深入研究&#xff0c;本次记录涉及到prophet 的公式以及参数调优&#xff0c;从公式可以更直观…...

Frozen-Flask :将 Flask 应用“冻结”为静态文件

Frozen-Flask 是一个用于将 Flask 应用“冻结”为静态文件的 Python 扩展。它的核心用途是&#xff1a;将一个 Flask Web 应用生成成纯静态 HTML 文件&#xff0c;从而可以部署到静态网站托管服务上&#xff0c;如 GitHub Pages、Netlify 或任何支持静态文件的网站服务器。 &am…...

2021-03-15 iview一些问题

1.iview 在使用tree组件时&#xff0c;发现没有set类的方法&#xff0c;只有get&#xff0c;那么要改变tree值&#xff0c;只能遍历treeData&#xff0c;递归修改treeData的checked&#xff0c;发现无法更改&#xff0c;原因在于check模式下&#xff0c;子元素的勾选状态跟父节…...

Python爬虫(二):爬虫完整流程

爬虫完整流程详解&#xff08;7大核心步骤实战技巧&#xff09; 一、爬虫完整工作流程 以下是爬虫开发的完整流程&#xff0c;我将结合具体技术点和实战经验展开说明&#xff1a; 1. 目标分析与前期准备 网站技术分析&#xff1a; 使用浏览器开发者工具&#xff08;F12&…...

论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(一)

宇树机器人多姿态起立控制强化学习框架论文解析 论文解读&#xff1a;交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架&#xff08;一&#xff09; 论文解读&#xff1a;交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化…...

JUC笔记(上)-复习 涉及死锁 volatile synchronized CAS 原子操作

一、上下文切换 即使单核CPU也可以进行多线程执行代码&#xff0c;CPU会给每个线程分配CPU时间片来实现这个机制。时间片非常短&#xff0c;所以CPU会不断地切换线程执行&#xff0c;从而让我们感觉多个线程是同时执行的。时间片一般是十几毫秒(ms)。通过时间片分配算法执行。…...