聊聊redis中的有序集合

写在文章开头

有序集合(sorted set)是redis中比较常见的数据库结构，它不仅支持O(logN)界别的有序的范围查询，同时也支持O(1)级别的单元素查询，基于此问题，本文就将从redis源码的角度分析一下有序集合的设计与实现。

在这里插入图片描述

Hi，我是 sharkChili ，是个不断在硬核技术上作死的 java coder ，是 CSDN的博客专家 ，也是开源项目 Java Guide 的维护者之一，熟悉 Java 也会一点 Go ，偶尔也会在 C源码 边缘徘徊。写过很多有意思的技术博客，也还在研究并输出技术的路上，希望我的文章对你有帮助，非常欢迎你关注我的公众号： 写代码的SharkChili 。

因为近期收到很多读者的私信，所以也专门创建了一个交流群，感兴趣的读者可以通过上方的公众号获取笔者的联系方式完成好友添加，点击备注 “加群” 即可和笔者和笔者的朋友们进行深入交流。

在这里插入图片描述

详解redis中的有序集合

基本结构介绍

有序集合的实现可以说是集大成于一身，它之所以支持单元素查询和范围查询，是字典(dict)和跳表(skipList)的组合结果，它将带有权重的元素指针分别交给字典和跳表进行管理。

关于跳表的介绍，笔者之前也写过一篇关于跳表的设计与实现思路的文章，感兴趣的可以移步JavaGuide官网:

Redis为什么用跳表实现有序集合

当我们需要通过元素名称定位其权重时，我们可以通过哈希算法到字典中定位到对应的元素，以下图为例，若我们希望定位到apple这个元素的权重时，可以直接计算apple的哈希值结合哈希算法即可实现O(1)级别的元素定位。

当我们希望进行范围查询时，很明显哈希表算法的无序性很难快速做到这一点，对应的我们可以直接通过跳表的索引快速定位到指定范围，以下图为例，假设我们希望查询权重在20到30之间的元素，对应的跳表的查询路径为:

  1. apple节点的2级索引。
  2. apple节点的1级索引。
  3. 通过banana的2级索引锁定范围。

这种通过多级索引的方式使得跳表范围查询的时间复杂度为O(logN)级别非常之高效。

在这里插入图片描述

关于有序集合的源码定义，因为该数据结构是组合而非自实现，所以其定义在redis.h这个头文件中：

typedef struct zset {
	//字典
    dict *dict;
    //跳表
    zskiplist *zsl;
} zset;

有序集合的初始化和保存操作

假设我们键入如下指令插入一个权重为1的元素:

ZADD runoobkey 1 dskadjksldksdjsdjskdjksldklsdjlksdjklsadjksladjklsdjksldjksladjskaldjskdjsalkdlksadksdklsadjklsadklsaddkslkadsakdjdlkjsdlkjdlkadjlksadjklsajlksjdjsakldjksadjklsdjlsakdjlsadadasdjsakdljskaldjlksdjlksdjlksajdklsdjksladjklsadjklsajdlksadjlksajdksajdskldjaslkdjsalkdjslkajdskadjlksadjksladjklsadskadjlskajdksajdksaldjksldjkldjsalkdjklsadjlksajdlkadjksajdksladjksladjsdjslakdjlksadjsakldjlksajdlksajdlksajdlksajdlksajdlksajdsladjladskdjlsakjdlksajdlkajdlsakdj

redis服务端收并解出zadd命令后就会调用zaddGenericCommand初始化字典和跳表，再进行元素的保存操作，对应的源码如下，这里笔者省去了有序集合为压缩列表时元素维护的逻辑，可以看到当插入的元素值的长度若大于64字节，则创建的有序集合是由跳表和字典构成。
完成初始化之后，无论是更新还是插入操作，有序集合都会基于该元素的指针将其分别维护到跳表和字典中:

void zaddGenericCommand(redisClient *c, int incr) {
   	//......
   	//判断有序集合是否存在
    zobj = lookupKeyWrite(c->db,key);
    //若为空则当前元素长度大于zset_max_ziplist_value(默认为64)则创建上文所说的有序集合
    if (zobj == NULL) {
        if (server.zset_max_ziplist_entries == 0 ||
            server.zset_max_ziplist_value < sdslen(c->argv[3]->ptr))
        {
        	//创建通过字典和跳表组合实现的有序集合
            zobj = createZsetObject();
        } else {
            zobj = createZsetZiplistObject();
        }
        //将有序集合存入键值对中
        dbAdd(c->db,key,zobj);
    } else {
       //......
    }
	
	//
    for (j = 0; j < elements; j++) {
        score = scores[j];
		//有序集合为压缩列表的逻辑
        if (zobj->encoding == REDIS_ENCODING_ZIPLIST) {
           //......
        } else if (zobj->encoding == REDIS_ENCODING_SKIPLIST) {
            zset *zs = zobj->ptr;
            zskiplistNode *znode;
            dictEntry *de;

            ele = c->argv[3+j*2] = tryObjectEncoding(c->argv[3+j*2]);
            //到哈希表中定位元素并完成保存或者更新操作
            de = dictFind(zs->dict,ele);
            if (de != NULL) {
               //更新操作
            } else {
            	//插入操作，先将其元素插入到跳表
                znode = zslInsert(zs->zsl,score,ele);
               	//......
                //再将元素的指针同时维护到字典中
                redisAssertWithInfo(c,NULL,dictAdd(zs->dict,ele,&znode->score) == DICT_OK);
              	//......
            }
        } else {
            redisPanic("Unknown sorted set encoding");
        }
    }
  //......
}

利用字典完成单值查询

有了这样一个组合的数据结构，不同的查询操作就变得非常方便，例如我们使用Zrank 查询对应有序集合zset的element-1的权重：

 Zrank  zsets element-1

redis解析该字符串后走到zrankCommand方法，其内部调用zrankGenericCommand，直接通过当前传入的元素的名称到字典中快速定位元素权重并返回:

void zrankCommand(redisClient *c) {
	//调用zrankGenericCommand完成O(1)级别的查询
    zrankGenericCommand(c, 0);
}


void zrankGenericCommand(redisClient *c, int reverse) {
	//获取参数中的key和要查询的元素
    robj *key = c->argv[1];
    robj *ele = c->argv[2];
    robj *zobj;
    unsigned long llen;
    unsigned long rank;

   //......

    redisAssertWithInfo(c,ele,sdsEncodedObject(ele));
	//有序集合为跳表的逻辑，不重要所以直接跳过
    if (zobj->encoding == REDIS_ENCODING_ZIPLIST) {
        //......
    } else if (zobj->encoding == REDIS_ENCODING_SKIPLIST) {
	    //......
	    //通过有序集合的字典快速定位元素并返回
        de = dictFind(zs->dict,ele);
        if (de != NULL) {
            //获取score
            score = *(double*)dictGetVal(de);
            //从跳表中获得对应等级
            rank = zslGetRank(zsl,score,ele);
           //......
           //将结果写出去
            if (reverse)
                addReplyLongLong(c,llen-rank);
            else
                addReplyLongLong(c,rank-1);
        } else {
            addReply(c,shared.nullbulk);
        }
    } else {
        redisPanic("Unknown sorted set encoding");
    }
}

利用跳表完成范围查询

对应的假如我们通过ZRANGE 指令查询索引2到3范围以内的元素：

ZRANGE zsets 2 3 WITHSCORES

该操作对应有序集合中时，会算得我们要获取的是第3、4个元素，此时有序集合就会通过跳表完成这一查询，如下图所示，我们以红色标识为路径即可知晓，因为多级索引的存在，范围查询过程为:

  1. 由2 3算的我们要查询的长度为(3-2)+1即2个元素。
  2. 头节点apple的3级索引，其span为2代表跨越两个节点，加上自己本身相当于跨了3个节点定位到了目标元素的起始位置。
  3. 因为我们的查询长度为2，所以orange元素的指针向后1步即可拿到所有元素。
  4. 自此我们拿到元素orange和pear，并将score一并写出。

在这里插入图片描述

对应的命令就会走到t_zset.c的zrangeCommand的逻辑，可以看到其内部本质就是对zrangeGenericCommand的调用，这其中0表示按照升序查询:

void zrangeCommand(redisClient *c) {
	//调用zrangeGenericCommand到跳表获取范围结果
    zrangeGenericCommand(c,0);
}

我们继续步入这段逻辑即可看到跳表整体逻辑，先计算索引的查询范围，然后继续该范围通过跳表定位到第一个符合要求的元素，再基于该元素的指针继续往后查询：

void zrangeGenericCommand(redisClient *c, int reverse) {
    robj *key = c->argv[1];
    robj *zobj;
    int withscores = 0;
    long start;
    long end;
    int llen;
    int rangelen;

   //......

	//根据传入的范围计算本次范围查询的长度rangelen 
    llen = zsetLength(zobj);
    //边界判断
    if (start < 0) start = llen+start;
    if (end < 0) end = llen+end;
    if (start < 0) start = 0;

   //......
    if (end >= llen) end = llen-1;
    //计算查询范围
    rangelen = (end-start)+1;

    //......
    if (zobj->encoding == REDIS_ENCODING_ZIPLIST) {
      //......

    } else if (zobj->encoding == REDIS_ENCODING_SKIPLIST) {//跳表的逻辑
    
        zset *zs = zobj->ptr;
        zskiplist *zsl = zs->zsl;
        zskiplistNode *ln;
        robj *ele;

       
        if (reverse) {//倒叙查找元素
            ln = zsl->tail;
            if (start > 0)
                ln = zslGetElementByRank(zsl,llen-start);
        } else {
        	//升序查询第一个符合要求的元素
            ln = zsl->header->level[0].forward;
            if (start > 0)
                ln = zslGetElementByRank(zsl,start+1);
        }
		//根据范围长度rangelen通过ln的next指针开始不断遍历截取对应个数的元素
        while(rangelen--) {
            redisAssertWithInfo(c,zobj,ln != NULL);
            ele = ln->obj;
            addReplyBulk(c,ele);
            if (withscores)
                addReplyDouble(c,ln->score);
             //基于最底层的叶子节点的forward前进获取后续的元素
            ln = reverse ? ln->backward : ln->level[0].forward;
        }
    } else {
        redisPanic("Unknown sorted set encoding");
    }
}

这里我们重点查看zslGetElementByRank，该函数会传入要查询的第一个元素的编号rank(该值为索引号+1)，和我们图解的逻辑基本一致，从跳表首元素的索引开始累加查看span是否等于rank，一旦等于rank就说明当前节点就是我们的要查询范围的第一个元素，有序集合就会将该元素的指针返回:

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--) {
    	//查看当前元素是否还有前驱节点且当亲累加结果是否小于rank，若都符合要求则说明当前还没到到达要查询的第一个元素的位置，进入该循环，不断向前或者向下跨span
        while (x->level[i].forward && (traversed + x->level[i].span) <= rank)
        {
            traversed += x->level[i].span;
            x = x->level[i].forward;
        }
        //经过的节点长度traversed 等于第一个元素的编号rank时将该指针返回
        if (traversed == rank) {
            return x;
        }
    }
    return NULL;
}

小结

自此我们就将redis中有序集合的最核心的思想和设计都分析完成了，希望对你有帮助。

我是 sharkchili ，CSDN Java 领域博客专家，开源项目—JavaGuide contributor，我想写一些有意思的东西，希望对你有帮助，如果你想实时收到我写的硬核的文章也欢迎你关注我的公众号： 写代码的SharkChili 。
因为近期收到很多读者的私信，所以也专门创建了一个交流群，感兴趣的读者可以通过上方的公众号获取笔者的联系方式完成好友添加，点击备注 “加群” 即可和笔者和笔者的朋友们进行深入交流。

在这里插入图片描述

参考

《redis设计与实现》

Redis 有序集合(sorted set):https://www.runoob.com/redis/redis-sorted-sets.html

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

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

相关文章

Vue3【二十二】Vue 路由模式的嵌套路由和用query给组件的RouterLink传参

Vue3【二十二】Vue 路由模式的嵌套路由和用query给组件的RouterLink传参

Vue3【二十二】Vue 路由模式的嵌套路由和用query给组件传参 Vue3【二十二】Vue 路由模式的嵌套路由和用query给组件传参 RouterLink 的两种传参方法 RouterView 案例截图 目录结构 代码 index.ts // 创建一个路由器&#xff0c;并暴漏出去// 第一步&#xff1a;引入createRou…
阅读更多...
ATA-4011C高压功率放大器在亥姆霍兹线圈中的作用介绍

ATA-4011C高压功率放大器在亥姆霍兹线圈中的作用介绍

高压功率放大器在亥姆霍兹线圈中的作用是为亥姆霍兹线圈提供稳定的高功率电流信号&#xff0c;从而产生强大的磁场。亥姆霍兹线圈是一种用于产生均匀磁场的设备&#xff0c;在物理实验、医学成像和工业领域中得到广泛应用。下面安泰电子官网将从以下几个方面详细介绍高压功率放…
阅读更多...
推荐阅读:车载测试新纪元，智能座舱的全面解读

推荐阅读:车载测试新纪元，智能座舱的全面解读

前段时间给自己定了一个计划&#xff0c;决定来学一下车载测试的相关内容&#xff0c;既然车载测试被大家说的这么火&#xff0c;作为一个测试人员&#xff0c;不去了解一下怎么行呢&#xff1f;当然&#xff0c;目前的行业还可以咯&#xff0c;但是给自己适当的投资充电&#…
阅读更多...
国际荐酒师携手各国际荐酒师专业委员会深化2024年度合作

国际荐酒师携手各国际荐酒师专业委员会深化2024年度合作

国际荐酒师&#xff08;香港&#xff09;协会携手广东海上丝绸之路文化促进会及广东省城镇化发展研究会&#xff0c;深化2024年度合作&#xff0c;共同打造品荐与传播大师班培养荐酒师专业人材 近日&#xff0c;国际荐酒师&#xff08;香港&#xff09;协会、广东海上丝绸之路…
阅读更多...
『Z-Weekly Feed 08』加密资产观 | FHE应用前景 | OPAL协议

『Z-Weekly Feed 08』加密资产观 | FHE应用前景 | OPAL协议

一位机构投资者的加密资产观 作者&#xff1a;Hongbo 01 &#x1f4a1;TL;DR 在加密投资领域如何找到真正的“价值”&#xff1a;Crypto 作为一种新兴资产&#xff0c;应该找到一种区别于传统公司股票资产的估值方法&#xff0c;本文重点阐述了加密货币作为新的资产类型与传统资…
阅读更多...
康谋分享 | 从CAN到CAN FD：ADTF在汽车网络中的应用

康谋分享 | 从CAN到CAN FD：ADTF在汽车网络中的应用

随着汽车电子技术的发展&#xff0c;车辆上配备了越来越多的电子装置&#xff0c;这些设备多采用点对点的方式通信&#xff0c;这也导致了车内存在庞大的线束。造成汽车制造和安装的困难并进一步降低汽车的配置空间&#xff0c;汽车总线逐步开始向网络化方向发展。 在此背景下…
阅读更多...
FANUC喷涂机器人P-350iA电机过热维修解决方案

FANUC喷涂机器人P-350iA电机过热维修解决方案

发那科喷涂机器人作为自动化喷涂生产线的重要组成部分&#xff0c;其性能稳定性和可靠性对于生产效率和产品质量具有重要影响。然而&#xff0c;在实际使用过程中&#xff0c;FANUC喷涂机器人P-350iA电机过热故障问题往往成为影响其正常运行的主要因素之一。 FANUC机器人M-100…
阅读更多...
第一百一十二节 Java面向对象设计 - Java异常处理

第一百一十二节 Java面向对象设计 - Java异常处理

Java面向对象设计 - Java异常处理 异常是在没有定义正常执行路径时在Java程序的执行期间可能出现的条件。 Java通过将执行操作的代码与处理错误的代码分离来处理错误。 当发生异常时&#xff0c;Java会创建一个包含有关异常的所有信息的对象&#xff0c;并将其传递给相应的异…
阅读更多...
阿里云ECS（CentOS/Alibaba Cloud Linux）安装最新 Docker 方法

阿里云ECS（CentOS/Alibaba Cloud Linux）安装最新 Docker 方法

最近&#xff08;6月份&#xff09;我发现 docker 官方无法正常访问&#xff0c;docker pull 命令也执行失败&#xff0c;用 TZ 也一样&#x1f614;。 以下步骤适用于 CentOS 7/8或Alibaba Cloud Linux 系统。 1. 更新系统包 首先&#xff0c;确保您的ECS实例系统软件包是最…
阅读更多...
Next.js开发中使用useRouter实现点击返回到上一页

Next.js开发中使用useRouter实现点击返回到上一页

在使用Next.js框架做前端页面开发时&#xff0c;如果想返回到上一页&#xff0c;可以利用useRouter钩子提供的back()方法&#xff0c;可以这样做: import {useRouter} from "next/navigation"; import {Space} from "antd"; import {ArrowLeftOutlined} f…
阅读更多...
tiaoshixitong

tiaoshixitong

data_interval : 当是ubus 时 重新赋值为 3&#xff1b;当是ws 时 重新赋值为 20&#xff1b; 1. 如何理解data_tik &#xff1f; 在函数can_packet_check_timer 定时can发送函数里面&#xff0c;data_tik 作为倒计时时间&#xff0c;当倒计时间到&#xff0c;则发送。…
阅读更多...
LCB模型引领机器人进入端到端新维度

LCB模型引领机器人进入端到端新维度

论文标题&#xff1a; From LLMs to Actions: Latent Codes as Bridges in Hierarchical Robot Control 论文作者&#xff1a; Yide Shentu&#xff0c;Philipp Wu&#xff0c;Aravind Rajeswaran&#xff0c;Pieter Abbeel 项目地址&#xff1a; https://fredshentu.gith…
阅读更多...
手把手！从头构建LLaMA3大模型（Python）

手把手！从头构建LLaMA3大模型（Python）

1. 前期准备 让我们先来想一想大概需要做什么。 首先是模型架构的选择。原工作用的是 GPT Neo 架构&#xff08;可以看他们的 config&#xff09;&#xff0c;这个算是很老的模型了&#xff0c;最初是 EleutherAI 用来复现追踪 GPT-3 的工作的&#xff0c;现在用的也比较少了…
阅读更多...
JavaScript运行原理和执行过程

JavaScript运行原理和执行过程

参考&#xff1a; https://www.cnblogs.com/hexrui/p/15939592.html 1、执行上下文栈&#xff08;调用栈&#xff09; GECGlobal Execution Context&#xff08;GEC&#xff09;被放入到ECS&#xff08;Execution Context Stack&#xff0c;简称ECS&#xff09;中 GEC开始执…
阅读更多...
走嵌入式方向有必要参加数模的比赛，涨一下见识吗？

走嵌入式方向有必要参加数模的比赛，涨一下见识吗？

在开始前刚好我有一些资料&#xff0c;是我根据网友给的问题精心整理了一份「嵌入式的资料从专业入门到高级教程」&#xff0c; 点个关注在评论区回复“888”之后私信回复“888”&#xff0c;全部无偿共享给大家&#xff01;&#xff01;&#xff01;参加数模&#xff08;数学…
阅读更多...
MYSQL 四、mysql进阶 3（存储引擎）

MYSQL 四、mysql进阶 3（存储引擎）

mysql中表使用了不同的存储引擎也就决定了我们底层文件系统中文件的相关物理结构。 为了管理方便&#xff0c;人们把连接管理、语法解析、查询优化这些并不涉及真实数据存储的功能划分为 Mysql Server的功能&#xff0c;把真实存取数据的功能划分为存储引擎的功能&…
阅读更多...
【Unity】实现分屏开发

【Unity】实现分屏开发

前言&#xff1a; 最近有个项目二期需要做分屏开发&#xff0c;今天恰好研究一下为后续的项目做个准备。 原理 整体的实现还是蛮简单的&#xff0c;主要是通过camera的一个targetDisplay属性进行设置 可以看到unity支持最多八个分屏 实现 场景搭建 &#xff0c;这里直接使…
阅读更多...
Linux mongodb安装及简单使用

Linux mongodb安装及简单使用

说明&#xff1a;本文章主要是对mongodb的单击安装 1.创建文件夹&#xff0c;准备安装包 cd /user/local mkdir tools 2.解压mongodb包 mkdir mongodb tar -xvf mongodb-linux-x86_64-rhel70-5.0.11.tgz -C mongodb 3.进入解压目录 cd mongodb cd mongodb-linux-x86_64-…
阅读更多...
别再全网找了，这四款良心软件，还你一个清爽的电脑桌面

别再全网找了，这四款良心软件，还你一个清爽的电脑桌面

现在电脑桌面上软件多得吓人。 要是不整理&#xff0c;看着就闹心&#xff1b;整理起来呢&#xff0c;又累得够呛。 所以&#xff0c;很多人干脆就不用那些“用着没意思&#xff0c;删了又觉得可惜”的软件了。 但不管你怎么删&#xff0c;有些软件还是得留着&#xff0c;就像…
阅读更多...
数据治理创新路：建设数据集市，强化数据报送一致性新实践

数据治理创新路：建设数据集市，强化数据报送一致性新实践

随着信息化和数字化的飞速发展&#xff0c;数据已经成为企业运营和决策的核心要素。然而&#xff0c;数据治理的复杂性和多样性给企业带来了不小的挑战。为了更好地应对这些挑战&#xff0c;许多企业开始探索数据治理的创新路径&#xff0c;其中建设数据集市和强化数据报送一致…
阅读更多...
最新文章

Copyright @ 2022~2023