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/4
    while ((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/4
    while ((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;
    else
        zsl->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. 更新跳跃表高度与长度。

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

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

音视频技术开发周刊 | 317

音视频技术开发周刊 | 317

每周一期&#xff0c;纵览音视频技术领域的干货。 新闻投稿&#xff1a;contributelivevideostack.com。 MIT惊人再证大语言模型是世界模型&#xff01;LLM能分清真理和谎言&#xff0c;还能被人类洗脑 MIT等学者的「世界模型」第二弹来了&#xff01;这次&#xff0c;他们证明…
阅读更多...
谁知道腾讯云轻量服务器“月流量”是什么意思？

谁知道腾讯云轻量服务器“月流量”是什么意思？

腾讯云轻量服务器月流量什么意思&#xff1f;月流量是指轻量服务器限制每月流量的意思&#xff0c;不能肆无忌惮地使用公网&#xff0c;流量超额需要另外支付流量费&#xff0c;上海/广州/北京等地域的轻量服务器月流量不够用超额部分按照0.8元/GB的价格支付流量费。阿腾云aten…
阅读更多...
【SpringMVC篇】讲解RESTful相关知识

【SpringMVC篇】讲解RESTful相关知识

&#x1f38a;专栏【SpringMVC】 &#x1f354;喜欢的诗句&#xff1a;天行健&#xff0c;君子以自强不息。 &#x1f386;音乐分享【如愿】 &#x1f384;欢迎并且感谢大家指出小吉的问题&#x1f970; 文章目录 &#x1f384;REST简介&#x1f33a;RESTful入门案例⭐案例一⭐…
阅读更多...
【Java数据结构重点知识】第一节：认识数据结构与算法、集合框架

【Java数据结构重点知识】第一节：认识数据结构与算法、集合框架

一&#xff1a;数据结构与算法 1.数据结构 数据结构是计算机存储、组织数据的方式&#xff0c;指相互之间存在一种或多种特定关系的数据元素的集合 2.算法 算法就是定义良好的计算过程。他取一个或一组的值为输入&#xff0c;并产生一个或一组作为输出。简单来说就是一系列的…
阅读更多...
前端开发必备技能！用简单CSS代码绘制三角形，提升用户体验

前端开发必备技能！用简单CSS代码绘制三角形，提升用户体验

&#x1f3ac; 江城开朗的豌豆&#xff1a;个人主页 &#x1f525; 个人专栏 :《 VUE 》 《 javaScript 》 &#x1f4dd; 个人网站 :《 江城开朗的豌豆&#x1fadb; 》 ⛺️ 生活的理想&#xff0c;就是为了理想的生活 ! 目录 ⭐ 专栏简介 &#x1f4d8; 文章引言 一、前…
阅读更多...
AdaBins:使用自适应bins进行深度估计

AdaBins:使用自适应bins进行深度估计

论文&#xff1a;https://arxiv.org/abs/2011.14141 代码&#xff1a;https://github.com/open-mmlab/mmsegmentation/tree/main/projects/Adabins 0、摘要 本文主要解决了从单个RGB输入图像估计高质量密集深度图的问题。我们从一个baseline的encoder-decoder CNN结构出发&…
阅读更多...
cocos tilemap的setTileGIDAt方法不实时更新

cocos tilemap的setTileGIDAt方法不实时更新

需要取消勾选 Enable Culling。同时代码添加&#xff1a;markForUpdateRenderData函数。 floor.setTileGIDAt(102427,newP.x,newP.y,0); //中心 floor.markForUpdateRenderData(); 具体问题参考官网说明&#xff1a; Cocos Creator 3.2 手册 - 项目设置
阅读更多...
将数据文件，控制文件，日志文件分别放在不同的目录下，且数据库正常启动

将数据文件，控制文件，日志文件分别放在不同的目录下，且数据库正常启动

一、定位数据文件、控制文件、日志文件的位置 注意&#xff1a;后序需要用到这些文件的位置&#xff0c;可以在查询完毕之后先截图保存 1.以管理员身份登录数据库 sqlplus / as sysdba2.查找数据文件位置 SELECT name FROM v$datafile;3.查找控制文件位置 SELECT name FROM …
阅读更多...
Python算法练习 10.30

Python算法练习 10.30

leetcode 841 钥匙和房间 有 n 个房间&#xff0c;房间按从 0 到 n - 1 编号。最初&#xff0c;除 0 号房间外的其余所有房间都被锁住。你的目标是进入所有的房间。然而&#xff0c;你不能在没有获得钥匙的时候进入锁住的房间。 当你进入一个房间&#xff0c;你可能会在里面找…
阅读更多...
使用ControlNet生成视频(Pose2Pose)

使用ControlNet生成视频(Pose2Pose)

目录 ControlNet 介绍 ControlNet 14种模型分别是用来做什么的 ControlNet 运行环境搭建 用到的相关模型地址 ControlNet 介绍 ControlNet 是一种用于控制扩散模型的神经网络结构&#xff0c;可以通过添加额外的条件来实现对图像生成的控制。它通过将神经网络块的权重复制到…
阅读更多...
LeetCode 2742.给墙壁刷油漆

LeetCode 2742.给墙壁刷油漆

思路 dp(u,count)为当前再考虑下标为1-u的墙面&#xff0c;并且还有count免费工次的最小代价 主要是递归边界的选择&#xff1a; u1<count return 0; if(u-1&&count<0)return 0x3f3f3f3f; if(u-1&&count0)retrun 0; 这三个可以合并成 if(u<count) …
阅读更多...
C文件操作

C文件操作

目录 1. 什么是文件 2. 为什么要有文件 3. 文件名 4. 文件类型 5. 文件指针 6. 文件的打开和关闭 7. 文件的顺序读写 7.1. fgetc 7.2. fputc 7.3. fgets 7.4. fputs 7.5. fscanf 7.6. fprintf 7.8. sscanf 7.9. sprintf 7.9. fread 7.10. fwrite 8. 文件的随…
阅读更多...
drawio特性

drawio特性

drawio的特性 drawio是领先的基于Web技术的草图和图表功能功能的应用。 保证数据的安全 集成了各种不同的平台&#xff0c;和提供了在线的免费编辑器&#xff0c;可以使用app.diagrams.net来方案&#xff0c;drawio本身不会存储用户的数据。 随着互联网时代的发展&#xff0…
阅读更多...
【Java笔试强训】Day7（WY22 Fibonacci数列、CM46 合法括号序列判断）

【Java笔试强训】Day7（WY22 Fibonacci数列、CM46 合法括号序列判断）

Fibonacci数列 链接&#xff1a;Fibonacci数列 题目&#xff1a; Fibonacci数列是这样定义的&#xff1a; F[0] 0 F[1] 1 for each i ≥ 2: F[i] F[i-1] F[i-2] 因此&#xff0c;Fibonacci数列就形如&#xff1a;0, 1, 1, 2, 3, 5, 8, 13, …&#xff0c;在Fibonacci数列…
阅读更多...
Ant Design Vue

Ant Design Vue

官网 vue2 全局引入 项目为vue2时(安装指定版本) npm i --save ant-design-vue1.7.2main.js引入 import Antd from ant-design-vue; import ant-design-vue/dist/antd.css; Vue.use(Antd);局部引入 npm install ant-design-vue --save第一步&#xff1a;在src内创建一个资…
阅读更多...
oracle （8）Managing Tablespace Data File

oracle （8）Managing Tablespace Data File

Managing Tablespace & Data File &#xff08;维护表空间和数据文件&#xff09; 目标&#xff1a; 定义表空间和数据文件的用途创建表空间管理表空间学会使用甲骨文托管文件(OMF) 创建和管理表空间&#xff08;不是重点&#xff09;获取表空间信息 一、基础知识 1、表…
阅读更多...
故障诊断模型 | Maltab实现BiLSTM双向长短期记忆神经网络故障诊断

故障诊断模型 | Maltab实现BiLSTM双向长短期记忆神经网络故障诊断

文章目录 效果一览文章概述模型描述源码设计参考资料效果一览 文章概述 故障诊断模型 | Maltab实现BiLSTM双向长短期记忆神经网络故障诊断 模型描述 利用各种检查和测试方法，发现系统和设备是否存在故障的过程是故障检测；而进一步确定故障所在大致部位的过程是故障定位。故障…
阅读更多...
网络安全（黑客）—小白自学路线

网络安全（黑客）—小白自学路线

1.网络安全是什么 网络安全可以基于攻击和防御视角来分类&#xff0c;我们经常听到的 “红队”、“渗透测试” 等就是研究攻击技术&#xff0c;而“蓝队”、“安全运营”、“安全运维”则研究防御技术。 2.网络安全市场 一、是市场需求量高&#xff1b; 二、则是发展相对成熟…
阅读更多...
新恶意软件使用 MSIX 软件包来感染 Windows

新恶意软件使用 MSIX 软件包来感染 Windows

人们发现&#xff0c;一种新的网络攻击活动正在使用 MSIX&#xff08;一种 Windows 应用程序打包格式&#xff09;来感染 Windows PC&#xff0c;并通过将隐秘的恶意软件加载程序放入受害者的 PC 中来逃避检测。 Elastic Security Labs 的研究人员发现&#xff0c;开发人员通常…
阅读更多...
【Linux】centos安装配置及远程连接工具的使用

【Linux】centos安装配置及远程连接工具的使用

&#x1f389;&#x1f389;欢迎来到我的CSDN主页&#xff01;&#x1f389;&#x1f389; &#x1f3c5;我是Java方文山&#xff0c;一个在CSDN分享笔记的博主。&#x1f4da;&#x1f4da; &#x1f31f;推荐给大家我的专栏《微信小程序开发实战》。&#x1f3af;&#x1f3a…
阅读更多...
最新文章

Copyright @ 2022~2023