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…...
云原生核心技术 (7/12): K8s 核心概念白话解读(上):Pod 和 Deployment 究竟是什么?
大家好,欢迎来到《云原生核心技术》系列的第七篇! 在上一篇,我们成功地使用 Minikube 或 kind 在自己的电脑上搭建起了一个迷你但功能完备的 Kubernetes 集群。现在,我们就像一个拥有了一块崭新数字土地的农场主,是时…...
SCAU期末笔记 - 数据分析与数据挖掘题库解析
这门怎么题库答案不全啊日 来简单学一下子来 一、选择题(可多选) 将原始数据进行集成、变换、维度规约、数值规约是在以下哪个步骤的任务?(C) A. 频繁模式挖掘 B.分类和预测 C.数据预处理 D.数据流挖掘 A. 频繁模式挖掘:专注于发现数据中…...
渗透实战PortSwigger靶场-XSS Lab 14:大多数标签和属性被阻止
<script>标签被拦截 我们需要把全部可用的 tag 和 event 进行暴力破解 XSS cheat sheet: https://portswigger.net/web-security/cross-site-scripting/cheat-sheet 通过爆破发现body可以用 再把全部 events 放进去爆破 这些 event 全部可用 <body onres…...
Java - Mysql数据类型对应
Mysql数据类型java数据类型备注整型INT/INTEGERint / java.lang.Integer–BIGINTlong/java.lang.Long–––浮点型FLOATfloat/java.lang.FloatDOUBLEdouble/java.lang.Double–DECIMAL/NUMERICjava.math.BigDecimal字符串型CHARjava.lang.String固定长度字符串VARCHARjava.lang…...
【快手拥抱开源】通过快手团队开源的 KwaiCoder-AutoThink-preview 解锁大语言模型的潜力
引言: 在人工智能快速发展的浪潮中,快手Kwaipilot团队推出的 KwaiCoder-AutoThink-preview 具有里程碑意义——这是首个公开的AutoThink大语言模型(LLM)。该模型代表着该领域的重大突破,通过独特方式融合思考与非思考…...
什么是库存周转?如何用进销存系统提高库存周转率?
你可能听说过这样一句话: “利润不是赚出来的,是管出来的。” 尤其是在制造业、批发零售、电商这类“货堆成山”的行业,很多企业看着销售不错,账上却没钱、利润也不见了,一翻库存才发现: 一堆卖不动的旧货…...
cf2117E
原题链接:https://codeforces.com/contest/2117/problem/E 题目背景: 给定两个数组a,b,可以执行多次以下操作:选择 i (1 < i < n - 1),并设置 或,也可以在执行上述操作前执行一次删除任意 和 。求…...
SpringBoot+uniapp 的 Champion 俱乐部微信小程序设计与实现,论文初版实现
摘要 本论文旨在设计并实现基于 SpringBoot 和 uniapp 的 Champion 俱乐部微信小程序,以满足俱乐部线上活动推广、会员管理、社交互动等需求。通过 SpringBoot 搭建后端服务,提供稳定高效的数据处理与业务逻辑支持;利用 uniapp 实现跨平台前…...
【Go语言基础【12】】指针:声明、取地址、解引用
文章目录 零、概述:指针 vs. 引用(类比其他语言)一、指针基础概念二、指针声明与初始化三、指针操作符1. &:取地址(拿到内存地址)2. *:解引用(拿到值) 四、空指针&am…...
CSS | transition 和 transform的用处和区别
省流总结: transform用于变换/变形,transition是动画控制器 transform 用来对元素进行变形,常见的操作如下,它是立即生效的样式变形属性。 旋转 rotate(角度deg)、平移 translateX(像素px)、缩放 scale(倍数)、倾斜 skewX(角度…...
