深入解读redis的zset和跳表【源码分析】

1.基本指令

部分指令,涉及到第4章的api,没有具体看实现,但是逻辑应该差不多。

  • zadd <key><score1><value1><score2><value2>...
    • 将一个或多个member元素及其score值加入到有序集key当中。
    • 根据zslInsert
  • zrange <key><start><stop>[WITHSCORES]
    • 返回有序集key中,下标在 之间的元素
    • 根据zslGetElementByRank以及backward指针
  • zrangebyscore key min max [withscores] [limit offset count]
    • 返回有序集 key 中,所有score值介于min和max 之间(包括等于min或max )的成员
    • 根据zslFirstInRangezslLastInRange以及backward指针
  • zrank <key><value>
    • 返回该值在集合中的排名,从0开始。
    • 根据zslGetRank

2.数据结构

ZSET是由有序集合跳表实现的,按照分值的大小排序,分值相同时,按照成员对象的大小进行排序。同一个跳表可以有同分值的节点,但是对象必须是唯一的。
在这里插入图片描述
定义结构的代码src/server.h

// 1.ZSET节点
/* ZSETs use a specialized version of Skiplists */
typedef struct zskiplistNode {// member元素的valuesds ele;// member元素的scoredouble score;// 后向指针struct zskiplistNode *backward;// 层struct zskiplistLevel {// 前进指针struct zskiplistNode *forward;// 跨度unsigned long span;} level[];
} zskiplistNode;// 2.ZSET链表
typedef struct zskiplist {// 头节点和尾节点struct zskiplistNode *header, *tail;// 节点的数量(不包括头节点)unsigned long length;// 表中层数最大节点的层数int level;
} zskiplist;

结合上方的图容易理解,其中有一些值得注意的点

  1. header表头节点只有level,没有存放元素的value和score。在zskiplist的length也不包括头节点。
  2. 每一层都有两个属性:前向forward指针和跨度。前向指针指向包含同一层的下一个结点,跨度记录了两个节点间的距离。指向NULL的跨度都为0。跨度是用来计算排位rank的,在查找某个节点的过程中,将沿途访问过的所有层跨度累计起来,就能得到目标节点的排位。
  3. 后向backward指针指向当前节点的前一个节点。目的是遍历。和range有关的指令,可以获得range范围的首尾节点后,从尾节点遍历到首节点。(只有backward指针是遍历相邻节点,forward指针每一层都有,指向的间隔为span的节点,不是下一个节点)
  4. 每次创建一个跳表节点时,根据幂次定律随机生成一个介于1到32之间的值作为level数组的大小。(见第3章节复杂度分析)
  5. 节点的score是一个double类型的浮点数,成员对象value是一个SDS(字符串对象)。如果想用zset实现两个维度排序,可以用拼接的思想。

3.跳表通用复杂度分析

跳表的复杂度和level的层数有关,如果只有一层,那复杂度必然都是最坏情况O(N)。一个节点有多少层来自于下面这个函数,在新建节点时,根据幂次定律生成一个1到32间的随机数。
可以理解为有概率P多加一层。

int zslRandomLevel(void) {static const int threshold = ZSKIPLIST_P*RAND_MAX;int level = 1;while (random() < threshold)level += 1;return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}

我们知道完全二叉树的复杂度推导是
2 h − 1 = N 2^h-1=N 2h1=N
h = l o g 2 ( N + 1 ) h=log_2(N+1) h=log2(N+1)所以平均查找的时间复杂度是O(log(N))
跳表相当于一个多叉树,叉为 1 P \frac{1}{P} P1。(每一个节点有P的概率加一层,那相邻两层的节点数比为P。由于跳表最多32层,相邻两层实际节点数也不严格为P,所以这是一个近似的概念。)
复杂度推导为
( 1 P ) h − 1 − 1 = N (\frac{1}{P})^{h-1}-1=N (P1)h11=N
h = l o g 1 p ( N + 1 ) h=log_{\frac{1}{p}}(N+1) h=logp1(N+1)
如果p=0.25, h = 0.5 ∗ l o g 2 ( N + 1 ) h=0.5*log_2(N+1) h=0.5log2(N+1)
如果p=0.5, h = l o g 2 ( N + 1 ) h=log_2(N+1) h=log2(N+1)
所以p在一定范围都是O(log(N))级别的复杂度。P在极端情况下(比如接近0或1)会变成O(N)。

推导比较粗糙,可能有问题

4.API复杂度分析

4.1. 查找元素

zslFirstInRange找到分值范围的第一个元素;zslLastInRange找到分值范围的最后一个元素
平均O(logN),最坏O(N)

zskiplistNode *zslFirstInRange(zskiplist *zsl, zrangespec *range) {zskiplistNode *x;int i;/* 判断跳表分数的范围是否在该范围内 */if (!zslIsInRange(zsl,range)) return NULL;x = zsl->header;/** 从最高的层数开始遍历,直到最底层 **/for (i = zsl->level-1; i >= 0; i--) {/* 在同一层通过前向指针遍历,直到下一个节点为空或者下一节点分数大于等于范围最小值,进入下一层 */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;serverAssert(x != NULL);/* Check if score <= max. */if (!zslValueLteMax(x->score,range)) return NULL;return x;
}
int zslValueGteMin(double value, zrangespec *spec) {return spec->minex ? (value > spec->min) : (value >= spec->min);
}

4.2. 判断分值是否在范围

zslIsInRange判断是否至少一个节点的分值在范围内
O(1),根据头尾节点实现。zslFirstInRangezslLastInRange都会先调用这个函数进行判断。

/* 存在返回1,不存在返回0 */
int zslIsInRange(zskiplist *zsl, zrangespec *range) {zskiplistNode *x;/* 对值的范围进行判定 */if (range->min > range->max ||(range->min == range->max && (range->minex || range->maxex)))return 0;// 1.获取尾节点,尾节点的分数不大于等于(就是小于)范围的最小值返回0x = zsl->tail;if (x == NULL || !zslValueGteMin(x->score,range))return 0;// 2.获取头节点,头节点的分数大于范围的最大值返回0x = zsl->header->level[0].forward;if (x == NULL || !zslValueLteMax(x->score,range))return 0;return 1;
}

4.3. 添加元素

zslInsert添加元素
平均O(logN),最坏O(N)

zskiplistNode *zslInsert(zskiplist *zsl, double score, sds ele) {/* 为了插入节点到正确位置,存储遍历过程中每一层最尽头的节点,其实就是新节点的上一个节点(该节点的forward指向新节点)*/zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;/* 为了更新span,存储遍历过程中每一层的rank */unsigned long rank[ZSKIPLIST_MAXLEVEL];int i, level;serverAssert(!isnan(score));/**和查找类似的思路**/x = zsl->header;for (i = zsl->level-1; i >= 0; i--) {/* 存储每一层的rank值 */rank[i] = i == (zsl->level-1) ? 0 : rank[i+1];/* 在同一层通过前向指针遍历,直到1.下一个节点为空2.下一节点分数大于等于范围最小值3.节点分数相同元素值更大进入下一层 */while (x->level[i].forward &&(x->level[i].forward->score < score ||(x->level[i].forward->score == score &&sdscmp(x->level[i].forward->ele,ele) < 0))){/* 累加span获得rank */rank[i] += x->level[i].span;x = x->level[i].forward;}/* 记录每一层最末节点 */update[i] = x;}/* 获取一个随机的level层数 */level = zslRandomLevel();/* 如果新层数大于原跳表最大层数,更新zsl-level,并将超出的层记录下来 */if (level > zsl->level) {for (i = zsl->level; i < level; i++) {rank[i] = 0; update[i] = zsl->header;update[i]->level[i].span = zsl->length; }zsl->level = level; }x = zslCreateNode(level,score,ele);/* 更新新节点和每层新节点前一个节点的forward和span */for (i = 0; i < level; i++) {x->level[i].forward = update[i]->level[i].forward;update[i]->level[i].forward = x;/* update span covered by update[i] as x is inserted here */x->level[i].span = update[i]->level[i].span - (rank[0] - rank[i]);update[i]->level[i].span = (rank[0] - rank[i]) + 1;}/* increment span for untouched levels *//* 高于该节点的每一个span因为插入了一个节点所以要增加1 */for (i = level; i < zsl->level; i++) {update[i]->level[i].span++;}/* 更新backward指针 */x->backward = (update[0] == zsl->header) ? NULL : update[0];if (x->level[0].forward)x->level[0].forward->backward = x;elsezsl->tail = x;zsl->length++;return x;
}

4.4.获取成员排位

zslGetRank返回包含给定成员和score的节点的排位
平均O(logN),最坏O(N)

unsigned long zslGetRank(zskiplist *zsl, double score, sds ele) {zskiplistNode *x;unsigned long rank = 0;int i;x = zsl->header;for (i = zsl->level-1; i >= 0; i--) {while (x->level[i].forward &&(x->level[i].forward->score < score ||(x->level[i].forward->score == score &&sdscmp(x->level[i].forward->ele,ele) <= 0))) {/* 这一步记录了rank */rank += x->level[i].span;x = x->level[i].forward;}/* x might be equal to zsl->header, so test if obj is non-NULL */if (x->ele && x->score == score && sdscmp(x->ele,ele) == 0) {return rank;}}return 0;
}

4.5. 获取某排位节点

zslGetElementByRank返回跳跃表在给定排位上的节点

zskiplistNode* zslGetElementByRank(zskiplist *zsl, unsigned long rank) {zskiplistNode *x;/* 记录了遍历过程中的rank累加值 */unsigned long traversed = 0; int i;x = zsl->header;for (i = zsl->level-1; i >= 0; i--) {while (x->level[i].forward && (traversed + x->level[i].span) <= rank){traversed += x->level[i].span;x = x->level[i].forward;}if (traversed == rank) {return x;}}return NULL;
}

参考

  1. 《redis的设计与实现》
  2. redis源码-7.2.1

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/150570.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

手把手教你开发律师法律咨询小程序

随着科技的快速发展&#xff0c;移动互联网已经成为人们获取信息和服务的主要途径之一。对于律师和法律机构来说&#xff0c;开发一个律师法律咨询小程序&#xff0c;可以更好地满足用户的需求&#xff0c;提供便捷的法律咨询服务。本文将引导您如何使用乔拓云网这个第三方制作…

Jmeter控制RPS

一、前言 ​ RPS (Request Per Second)一般用来衡量服务端的吞吐量&#xff0c;相比于并发模式&#xff0c;更适合用来摸底服务端的性能。我们可以通过使用 JMeter 的常数吞吐量定时器来限制每个线程的RPS。对于RPS&#xff0c;我们可以把他理解为我们的TPS&#xff0c;我们就不…

精确到区县级街道乡镇行政边界geojson格式矢量数据的获取拼接实现Echarts数据可视化大屏地理坐标信息地图的解决方案

在Echarts制作地理信息坐标地图时&#xff0c;最麻烦的就是街道乡镇级别的行政geojson的获取&#xff0c; 文件大小 788M 文件格式 .json格式&#xff0c;由于是大文件数据&#xff0c;无法直接使用记事本或者IDE编辑器打开&#xff0c;推荐Dadroit Viewer&#xff08;国外…

【小黑送书—第三期】>>《深入浅出SSD》

近年来国家大力支持半导体行业&#xff0c;鼓励自主创新&#xff0c;中国SSD技术和产业良性发展&#xff0c;产业链在不断完善&#xff0c;与国际厂商的差距逐渐缩小。但从行业发展趋势来看&#xff0c;SSD相关技术仍有大幅进步的空间&#xff0c;SSD相关技术也确实在不断前进。…

stack和queque

1.stack 1.1定义 T 是容器内的数据类型&#xff1b; Container是数据类型的容器适配器 vector和list和stack的区别 1.2 stack的功能 注意这里没有迭代器&#xff1b;原因stack是先进后出的规律&#xff1b;这就规定该容器不可以随机访问&#xff1b; 2. queue

算法笔记:0-1背包问题

n个商品组成集合O&#xff0c;每个商品有两个属性vi&#xff08;体积&#xff09;和pi&#xff08;价格&#xff09;&#xff0c;背包容量为C。 求解一个商品子集S&#xff0c;令 优化目标 1. 枚举所有商品组合 共2^n - 1种情况 2. 递归求解 KnapsackSR(h, i, c)&#xff…

VScode配置Jupyter

环境 安装步骤 1、插件安装 2、更改pip加速源 pip config set global.index-url https://pypi.tuna.tsinghua.edu.cn/simple 参考&#xff1a;vscode python配置pip源 ​​​​​​​ 【Python学习】Day-00 Python安装、VScode安装、pip命令、镜像源配置、虚拟环境 3、建…

怎么通过docker/portainer部署vue项目

这篇文章分享一下如何通过docker将vue项目打包成镜像文件&#xff0c;并使用打包的镜像在docker/portainer上部署运行&#xff0c;写这篇文章参考了vue-cli和docker的官方文档。 首先&#xff0c;阅读vue-cli关于docker部署的说明&#xff0c;上面提供了关键的几个步骤。 从上面…

体会jdk17对于空指针的增强

jdk17 // 可以清楚的看出来a.b.c.num中由于c是空指针&#xff0c;所以导致异常 jdk11 // 只报第6行空指针了&#xff0c;但是因为哪个变量&#xff0c;不知道

Spring注册Bean系列--方法5:@Import+ImportBeanDefinitionRegistrar

原文网址&#xff1a;Spring注册Bean系列--方法5&#xff1a;ImportImportBeanDefinitionRegistrar_IT利刃出鞘的博客-CSDN博客 简介 本文介绍Spring注册Bean的方法&#xff1a;ImportImportBeanDefinitionRegistrar。 注册Bean的方法我写了一个系列&#xff0c;见&#xff…

14:00面试,14:06就出来了,这问的过于变态了。。。

前言 刚从小厂出来&#xff0c;没想到在另一家公司我又寄了。 在这家公司上班&#xff0c;每天都要加班&#xff0c;但看在钱给的比较多的份上&#xff0c;也就不太计较了。但万万没想到9月一纸通知&#xff0c;所有人不准加班了&#xff0c;不仅加班费没有了&#xff0c;薪资…

秒验:可以自定义UI的一键登录服务

一键登录如今成为越来越多移动应用的首选&#xff0c;但千篇一律的登陆界面在引发用户担忧其安全性的同时&#xff0c;也容易让用户在不同APP切换时产生误解。因此&#xff0c;由国内知名移动应用开发服务商MobTech打造的一键登录工具——秒验&#xff0c;通过允许开发者自定义…

Qt之QDial(表盘)

简介 QDial类提供了一个四舍五入的范围控制&#xff08;如速度计或电位计&#xff09;&#xff0c;非常适合需要循环计数的情况&#xff0c;例如角度等。 头文件&#xff1a;#include <QDial> qmake&#xff1a;QT widgets 继承&#xff1a;QAbstractSlider …

FPGA设计时序约束三、设置时钟组set_clock_groups

目录 一、背景 二、时钟间关系 2.1 时钟关系分类 2.2 时钟关系查看 三、异步时钟组 3.1 优先级 3.2 使用格式 3.3 asynchronous和exclusive 3.4 结果示例 四、参考资料 一、背景 Vivado中时序分析工具默认会分析设计中所有时钟相关的时序路径&#xff0c;除非时序约束…

Flink学习笔记(一):Flink重要概念和原理

文章目录 1、Flink 介绍2、Flink 概述3、Flink 组件介绍3.1、Deploy 物理部署层3.2、Runtime 核心层3.3、API&Libraries 层3.4、扩展库 4、Flink 四大基石4.1、Checkpoint4.2、State4.3、Time4.4、Window 5、Flink 的应用场景5.1、Event-driven Applications【事件驱动】5.…

docker数据管理和网络通信

docker数据管理 管理 Docker 容器中数据主要有两种方式&#xff1a; 数据卷&#xff08;Data Volumes&#xff09;和数据卷容器&#xff08;DataVolumes Containers&#xff09;。 1&#xff0e;数据卷 数据卷是一个供容器使用的特殊目录&#xff0c;位于容器中。可将宿主机…

轻量级MobileSAM:比FastSAM快4倍,处理一张图像仅需10ms(附源代码)

论文地址&#xff1a;https://arxiv.org/pdf/2306.14289.pdf 代码地址&#xff1a;https://github.com/ChaoningZhang/MobileSAM 一、概要简介 SAM是一种prompt-guided的视觉基础模型&#xff0c;用于从其背景中剪切出感兴趣的对象。自Meta研究团队发布SA项目以来&#xff0c…

浅析如何在抖音快速通过新手期并积累粉丝

抖音是一款非常受欢迎的短视频分享平台&#xff0c;它提供了一个快速成名和积累粉丝的机会。对于新手来说&#xff0c;通过四川不若与众总结的以下几个步骤可以帮助你快速通过抖音的新手期。 首先&#xff0c;确定你的内容定位。在抖音上&#xff0c;有各种各样的内容类型&…

解决报错:模块“react-redux“没有导出的成员“TypedUseSelectorHook”

在react整合typescript,redux时&#xff0c;写hook.ts时报这个错&#xff1a;模块"react-redux"没有导出的成员“TypedUseSelectorHook” 现象如下&#xff1a; 原因&#xff1a;react-redux版本太低&#xff0c;至少要升级到7.2.3以后才能包含TypedUseSelectorHook…

用 Pytorch 自己构建一个Transformer

一、说明 用pytorch自己构建一个transformer并不是难事,本篇使用pytorch随机生成五千个32位数的词向量做为源语言词表,再生成五千个32位数的词向量做为目标语言词表,让它们模拟翻译过程,transformer全部用pytorch实现,具备一定实战意义。 二、论文和概要 …