redis6.0源码分析:跳表skiplist

文章目录

  • 前言
  • 什么是跳表
  • 跳表(redis实现)的空间复杂度
    • 相关定义
  • 跳表(redis实现)相关操作
    • 创建跳表
    • 插入节点
    • 查找节点
    • 删除节点

前言

太长不看版

  • 跳跃表是有序集合zset的底层实现之一, 除此之外它在 Redis 中没有其他应用。
  • 每个跳跃表节点的层高都是 1 至 64 之间的随机数。
  • 层高越高出现的概率越低,层高为i的概率为在这里插入图片描述
  • 跳跃表中,分值可以重复, 但对象成员唯一。分值相同时,节点按照成员对象的大小进行排序。

本篇解析基于redis 5.0.0版本,本篇涉及源码文件为t_zset.c,server.h。

什么是跳表

跳表是一个随机化的数据结构,实质就是一种可以进行二分查找的有序链表。

我们都知道在有序数组中进行查找,可以使用二分查找,将时间复杂度降为O(log n)。但是有序链表做不到,是因为有序链表获取某元素复杂度为O(n),无法通过二分的思想去跳过一些元素的访问。

例如下图要查找元素50,就必须 5 -> 6 -> 10 -> 30 -> 49 这样去找,而不能说先看 中心元素49小于50,则开始从中心右边开始查找,跳过元素5,6,10, 30的访问。

在这里插入图片描述

而跳跃表则是通过在节点中提取索引的方式,实现有序链表的快速查找。本质上是一个空间(额外的步进指针)换时间的操作。例如下图:

在这里插入图片描述

这时查找元素50变成了 5 -> 49,略过了中间元素6,10, 30。上图中通过首节点存储不同步长的指针将链表完美二分,但是实际上的跳表却类似与下面这张图的结构,大部分情况喜爱不是完美二分的:

在这里插入图片描述

跳跃表采用了随机算法(层高越高概率越小)来决定层高,相同层之间通过指针相连。redis实现中某节点层高为i的概率为在这里插入图片描述

为什么不采用最完美的二分结构?

考虑一下,插入节点的情况。当中间插入一个节点,此时的二分结构会被打破,所以需要不断的进行调整。想想平衡树,红黑树复杂的再平衡操作,而此处的再平衡调整比之有过之而无不及。而使用随机算法进行层高选择的方法也可以实现O(logN)的平均复杂度,而且操作也相对简化的很多。

跳表(redis实现)的空间复杂度

相关定义

// 层高最大值限制
#define ZSKIPLIST_MAXLEVEL 64 /* Should be enough for 2^64 elements */
// 层高是否继续增长的概率
#define ZSKIPLIST_P 0.25      /* Skiplist P = 1/4 */
// 跳表节点定义
typedef struct zskiplistNode {// 存储内容sds ele;// 分值,用于排序double score;// 后退指针struct zskiplistNode *backward;// 变长数组,记录层信息。层高越高跳过的节点越多(因为层高越高概率越低)struct zskiplistLevel {// 指向当前层下一个节点struct zskiplistNode *forward;// 当前节点与forward所指节点中间节点数unsigned long span;} level[];
} zskiplistNode;
// 跳表结构管理节点
typedef struct zskiplist {struct zskiplistNode *header, *tail;// 长度unsigned long length;// 跳表高度(所有节点最高层高)int level;
} zskiplist;int zslRandomLevel(void) {// 计算当前插入元素层高的随机函数int level = 1;// (random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF) 概率为1/4while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF))level += 1;return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}

层高为1概率为 1-p(不进while)

层高为2的概率为 p(进一次while) * (1 - p)(不进while)

层高为3的概率为 p(进一次while) * p(进一次while) * (1 - p)(不进while)

层高为n的概率为 在这里插入图片描述

层高的期望在这里插入图片描述

在概率论和统计学中,数学期望(mean)(或均值,亦简称期望)是试验中每次可能结果的概率乘以其结果的总和,是最基本的数学特征之一。它反映随机变量平均取值的大小

在redis实现中 p=1/4, 层高期望为E约等于1.33,所以节点的平均层高约等于1.33是个常数,从而得出跳跃表的空间复杂度为O(n)。

跳表(redis实现)相关操作

创建跳表

zskiplistNode *zslCreateNode(int level, double score, int ele) {zskiplistNode *zn =malloc(sizeof(*zn)+level*sizeof(struct zskiplistLevel));zn->score = score;zn->ele = ele;return zn;
}/* Create a new skiplist. */
zskiplist *zslCreate(void) {int j;zskiplist *zsl;zsl = malloc(sizeof(*zsl));zsl->level = 1;zsl->length = 0;// 头节点层高为64(层高的最大限制)zsl->header = zslCreateNode(ZSKIPLIST_MAXLEVEL,0,NULL);for (j = 0; j < ZSKIPLIST_MAXLEVEL; j++) {zsl->header->level[j].forward = NULL;zsl->header->level[j].span = 0;}zsl->header->backward = NULL;zsl->tail = NULL;return zsl;
}

上述代码中可以看到,头节点的层高数组直接为最大长度,因为每次查找都要从头部开始,而且整个跳跃表的高度是动态增加的,初始化时直接按照最大值申请高度,避免后续高度增加时为头节点重新分配内存。所以之前的跳跃表图例应该如下图所示:

在这里插入图片描述

因为有backward指针的存在,所以第一层可以看作是一个双向链表。

插入节点

int zslRandomLevel(void) {// 计算当前插入元素层高的随机函数int level = 1;// (random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF) 概率为1/4while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF))level += 1;return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}zskiplistNode *zslInsert(zskiplist *zsl, double score, sds ele) {// update存放需要更新的节点zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;unsigned int rank[ZSKIPLIST_MAXLEVEL];int i, level;serverAssert(!isnan(score));x = zsl->header;// 第一步,收集需要更新的节点与步长信息for (i = zsl->level-1; i >= 0; i--) {/* store rank that is crossed to reach the insert position */rank[i] = i == (zsl->level-1) ? 0 : rank[i+1];// score可以重复,重复时使用ele大小进行排序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[i] += x->level[i].span;x = x->level[i].forward;}update[i] = x;}// 第二步, 获取随机层高,补全需要更新的节点level = zslRandomLevel();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);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 */for (i = level; i < zsl->level; i++) {update[i]->level[i].span++;}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;
}

插入节点分为四步(举个栗子,边吃边看):

在这里插入图片描述

假设现在我需要插入元素80,且获取到随机的层高为5(为了所有情况都覆盖到)。

在这里插入图片描述

  1. 收集需要更新的节点与步长信息

    • 将插入新增节点后每层受影响节点存在update数组中,update[i]为第i + 1层会受影响节点(红框框出来的就是例子中可能会受影响的节点)。

    • 将每层头节点与会受影响的节点中间存在节点数存在rank数组中,rank[i]为头节点与第i + 1层会受影响节点中间存在的节点数(rank为[6, 5, 3, 3])。

    在这里插入图片描述

  2. 获取随机层高,补全需要更新的节点,同时可能更新跳表高度

    • 通过zslRandomLevel函数计算当前插入节点侧层高,层高越高出现的几率越小(我们指定了是5,实际是随机的)。

    • 因为搜索需要更新节点是从跳跃表当前高度的那一层开始的,如果新插入的节点的层高比当前表高还高,那么高出的这几层的头节点也是需要更新信息的(第五层的头节点后继有人了,所以它也需要被更新)。

    • 如果当前层高高于表高,则更新表高(表高从4变成5)。

    在这里插入图片描述

  3. 创建并分层插入节点,同时更新同层前一节点步长信息

    • 创建节点,然后根据当前节点的层高,在每一层进行节点插入(和简单链表插入一样)。

    • 更新下每层前一个节点(update[i]对应节点)与自身节点的步长信息。

  4. 更新新增节点未涉及层节点的步长信息,以及跳表相关信息与节点自身的相关信息

    • 如果当前节点的层高比跳表高度低,那么高于当前节点层高的那些层中排在当前节点之后的节点步长信息都需要+1(因为在它和它的前一个节点之间插入了新元素)。

    • 更新跳表长度与当前节点与第一层下一节点的后退指针(后退指针可以理解为只有底层链表有)。

查找节点

/* Find the rank for an element by both score and key.* Returns 0 when the element cannot be found, rank otherwise.* Note that the rank is 1-based due to the span of zsl->header to the* first element. */
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 += 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 && sdscmp(x->ele,ele) == 0) {return rank;}}return 0;
}/* Finds an element by its rank. The rank argument needs to be 1-based. */
zskiplistNode* zslGetElementByRank(zskiplist *zsl, unsigned long rank) {zskiplistNode *x;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;
}

redis实现中跳跃表和dict共同实现了zset,dict实现O(1)复杂度获取元素对应score,跳跃表用来处理区间查询的相关操作,同时因为score可以重复,所以跳跃表无需实现通过ele获取score(通过dict查)以及通过score获取ele(貌似也没有这个需求)。

一般查询需求有两个:

  • 根据rank查询节点,主要是为了通过该节点指针进行遍历获取某个区间的节点数据。
  • 根据score与ele(score可能重复,所以需要ele)获取节点的rank,进行count之类的数值计算。

在这里插入图片描述

大体的流程都是按照从左上方开始向右下方搜索的路线进行查询(如上图红线标记路径)。

删除节点

/* Internal function used by zslDelete, zslDeleteByScore and zslDeleteByRank */
void zslDeleteNode(zskiplist *zsl, zskiplistNode *x, zskiplistNode **update) {int i;for (i = 0; i < zsl->level; i++) {// 被删除节点在第i层有节点,则update[i]为被删除节点的前一个节点if (update[i]->level[i].forward == x) {// 步长 = 原步长 + 被删除节点步长 - 1(被删除节点)update[i]->level[i].span += x->level[i].span - 1;// 指针越过被删除节点update[i]->level[i].forward = x->level[i].forward;} else {// 被删除节点在第i层无节点,则 步长 = 原步长 - 1(被删除节点)update[i]->level[i].span -= 1;}}if (x->level[0].forward) {// 更新被删除节点下一节点的后退指针x->level[0].forward->backward = x->backward;} else {zsl->tail = x->backward;}while(zsl->level > 1 && zsl->header->level[zsl->level-1].forward == NULL)zsl->level--;zsl->length--;
}int zslDelete(zskiplist *zsl, double score, sds ele, zskiplistNode **node) {zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;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))){x = x->level[i].forward;}update[i] = x;}/* We may have multiple elements with the same score, what we need* is to find the element with both the right score and object. */x = x->level[0].forward;if (x && score == x->score && sdscmp(x->ele,ele) == 0) {zslDeleteNode(zsl, x, update);if (!node)zslFreeNode(x);else*node = x;return 1;}return 0; /* not found */
}

删除节点与添加节点步骤类似,分为三步:

  1. 收集需要更新的节点。
  2. 删除节点所在的层链表移除节点(和简单链表移除节点一样),并更新前一节点的步长信息(update[i]所存节点)。
  3. 更新跳跃表高度与长度。

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

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

相关文章

深度学习入门(二)之神经网络

文章目录 从感知机到神经网络神经网络的例子复习感知机激活函数 激活函数sigmoid函数阶跃函数的实现阶跃函数的图形sigmoid函数的图形sigmoid函数与阶跃函数比较非线性函数ReLU函数 多维数组的运算多维数组矩阵乘法神经网络的内积 三层神经网络的实现符号确认各层间信号传递的实…

10kb的WordPress外链页面安全跳转插件

老白博客我参照csdn和腾讯云的外链跳转页面&#xff0c;写了一个WordPress外链安全跳转插件&#xff1a;给网站所有第三方链接添加nofollow标签和重定向功能&#xff0c;提高网站安全性。插件包括两个样式&#xff0c;由于涉及到的css不太一样&#xff0c;所以分别写了两个版本…

高效处理异常值的算法:One-class SVM模型的自动化方案

一、引言 数据清洗和异常值处理在数据分析和机器学习任务中扮演着关键的角色。清洗数据可以提高数据质量&#xff0c;消除噪声和错误&#xff0c;从而确保后续分析和建模的准确性和可靠性。而异常值则可能对数据分析结果产生严重影响&#xff0c;导致误导性的结论和决策。因此&…

纪念基于JavaScript 实现的后台桌面 UI 设计

目录 前言 C/S 到 B/S ASP Builder 的诞生 关于 Craneoffice.net 开发环境配置 后台界面的 UI 区域要素 桌面系统的想法和设计 搜索引擎 导航面板 快捷访问 二级导航 小组件及其它 设置桌面壁纸 小时钟 附件小程序 计算器界面设计 日历与任务 系统设置 天气小…

【HeidiSql_01】python在heidisql当中创建新表的注意事项

python在heidisql当中创建新表的注意事项 假设你已经在python当中弄好了所有的结果&#xff0c;并且保存在df_all这个dataframe当中&#xff0c;然后要将其导入数据库当中并创建一张新的表进行保存。 # 构建数据库连接,将merged_df写回数据库 from sqlalchemy import create_e…

进口跨境商城源码:高效、安全、可扩展的电商平台解决方案

电子商务的兴起为跨境贸易提供了前所未有的机会和挑战。在这个全球化的时代&#xff0c;跨境电商平台成为许多企业进军国际市场的首选。然而&#xff0c;搭建一个高效、安全、可扩展的进口跨境商城并非易事。 1. 解决方案概述 我们推出的 "进口跨境商城源码" 提供了一…

小程序商城免费搭建之java商城 电子商务Spring Cloud+Spring Boot+二次开发+mybatis+MQ+VR全景+b2b2c

1. 涉及平台 平台管理、商家端&#xff08;PC端、手机端&#xff09;、买家平台&#xff08;H5/公众号、小程序、APP端&#xff08;IOS/Android&#xff09;、微服务平台&#xff08;业务服务&#xff09; 2. 核心架构 Spring Cloud、Spring Boot、Mybatis、Redis 3. 前端框架…

uniapp @click点击事件在新版chrome浏览器点击没反应

问题描述 做项目时&#xff0c;有一个弹出选择的组件&#xff0c;怎么点都不出来&#xff0c;最开始还以为是业务逻辑限制了不能点击。后来才发现别人的电脑可以点出来&#xff0c;老版本的浏览器也可以点出来&#xff0c;最后定位到是新版的chrome就不行了 这是我的浏览器版本…

【C++的OpenCV】第十四课-OpenCV基础强化(三):单通道Mat元素的访问之data和step属性

&#x1f389;&#x1f389;&#x1f389; 欢迎来到小白 p i a o 的学习空间&#xff01; \color{red}{欢迎来到小白piao的学习空间&#xff01;} 欢迎来到小白piao的学习空间&#xff01;&#x1f389;&#x1f389;&#x1f389; &#x1f496; C\Python所有的入门技术皆在 我…

STM32F407的系统定时器

文章目录 系统定时器SysTick滴答定时器寄存器STK_CTRL 控制寄存器STK_LOAD 重载寄存器STK_VAL 当前值寄存器STK_CALRB 校准值寄存器 初始化 Systick 定时器SysTick_InitSysTick_CLKSourceConfig delay_us寄存器delay_us库函数delay_xms短时delay_ms长时SysTick_Config 系统定时…

HTML和CSS的基础-前端扫盲

想要写出一个网页&#xff0c;就需要学习前端开发&#xff08;写网页代码&#xff09;和后端开发&#xff08;服务器代码&#xff09;。 对于前端的要求&#xff0c;我们不需要了解很深&#xff0c;仅仅需要做到扫盲的程度就可以了。 写前端&#xff0c;主要用到的有&#xf…

〔001〕虚幻 UE5 发送 get、post 请求、读取 json 文件

✨ 目录 🎈 安装 varest 扩展🎈 开启 varest 扩展🎈 发送 get 请求🎈 发送 post 请求🎈 读取 json 文件🎈 安装 varest 扩展 打开 虚幻商城,搜索 varest 关键字进行检索, varest 是一个 api 调用插件,支持 http/https 请求,也支持 json 文件的读取,最关键是该…

JavaScript

一. JavaScript概述 1. ECMAScript和JavaScript的关系 1996年11月&#xff0c;JavaScript的创造者--Netscape公司&#xff0c;决定将JavaScript提交给国际标准化组织ECMA&#xff0c;希望这门语言能够成为国际标准。次年&#xff0c;ECMA发布262号标准文件&#xff08;ECMA-26…

水库大坝可视化智能远程监管方案,助力安全监测智能巡检

一、背景需求 水库大坝作为防洪度汛的重要设施&#xff0c;其安全问题直接关系到人民群众的生命财产安全。因此&#xff0c;必须加强对大坝水库的安全管理&#xff0c;对水库除险加固和运行管护要消除存量隐患&#xff0c;实现常态化管理&#xff0c;同时要配套完善重点小型水…

在Linux上编译gdal3.1.2指南

作者:朱金灿 来源:clever101的专栏 为什么大多数人学不会人工智能编程?>>> 以Ubuntu 18编译gdal3.1.2为例,编译gdal3.1.2需要先编译proj库和geos库(可选)。我选择的proj库版本为proj-7.1.0,编译proj-7.1.0需要先编译tiff库和sqlite3。我选择的sqlite3的版本为…

高性能消息中间件 - Kafka3.x(三)

文章目录 高性能消息中间件 - Kafka3.x&#xff08;三&#xff09;Kafka Broker ⭐Kafka Broker概念Zookeeper&#xff08;新版本可以不使用zk了&#xff09;⭐Zookeeper的作用 Kafka的选举1&#xff1a;Broker选举Leader⭐Broker核心参数⭐案例&#xff1a;服役新节点和退役旧…

SaaS可配置性设计要点

1 引言 考虑到系统SaaS需求&#xff0c;就成熟的SaaS应用而言&#xff0c;元数据服务是为用户提供定制和配置应用、满足其特定需求的主要手段。 可配置能力主要反映在这4个方面&#xff1a;1 程序外观&#xff1b;2 工作流程与业务规则&#xff1b;3 数据模型&#xff1b…

微信便利签怎么弄?微信中有便捷操作的便签小程序吗

微信在日常办公及生活中比较重要的作用就是&#xff1a;聊天、视频会议、语音会议等&#xff0c;这是大家认知中的微信。除了这些功能以外&#xff0c;微信中还有很多小程序&#xff0c;小程序也能够辅助大家日常的办公。 比如&#xff0c;工作中我们需要制定工作计划&#xf…

vscode开启emmet语法

需要在setting.json中添加配置 首先进入设置&#xff0c;然后点击右上角 Vue项目添加如下配置 "emmet.syntaxProfiles": { "vue-html": "html", "vue": "html" },React项目添加如下配置 "emmet.includeLanguages&quo…

一体化模型图像去雨+图像去噪+图像去模糊(图像处理-图像复原-代码+部署运行教程)

本文主要讲述了一体化模型进行去噪、去雨、去模糊&#xff0c;也就是说&#xff0c;一个模型就可以完成上述三个任务。实现了良好的图像复原功能&#xff01; 先来看一下美女复原.jpg 具体的&#xff1a; 在图像恢复任务中&#xff0c;需要在恢复图像的过程中保持空间细节…