首页 > 数据库 >redis zset源码

redis zset源码

时间:2024-06-08 15:54:57浏览次数:26  
标签:ZSKIPLIST struct zset level redis zskiplistNode 源码 zsl

zset底层是由hash字典和跳表实现的,字典存储member->分数的映射关系,这样根据membe查询score的 时间复杂度O为1
跳表可以理解为多个层级的有序链表,每个节点可能在不同层级上,通过在不同层级的跳跃查找,把查询时间复杂度降低到 Olgn

1.随机层数,只有0.25的概率升级层数,最多64层
50%概率分配到第一层,25%概率分配到第二层。。
2.查找过程:
从最高层级开始查找,找到最后一个比查找元素小的节点,然后降一级,再次查找,直到找到改元素
例如,查找3
先从最高层开始找,发现4>3, 不满足,降低一层
从第二层开始找,发现2<3,满足,跨度=2,rank+=2;接着 2的下一个节点是4,4>3,不满足,降低一层,
从节点2的第一层开始找,3=3,满足,跨度=1,所以rank=3

  • 结构体定义
/* ZSETs use a specialized version of Skiplists */
typedef struct zskiplistNode {
    sds ele; // member
    double score; 
    struct zskiplistNode *backward; // 回溯指针,只有第一层才有值
    struct zskiplistLevel {
        struct zskiplistNode *forward;
        unsigned long span;
    } level[]; // 层级节点数组
} zskiplistNode;

typedef struct zskiplist {
    struct zskiplistNode *header, *tail; // 头尾指针
    unsigned long length; 
    int level; // 跳表层数
} zskiplist;

typedef struct zset {
    dict *dict; // 字典,member->score 映射关系
    zskiplist *zsl; // 跳表结构
} zset;
  • 方法列表

zskiplist *zslCreate(void) {
    int j;
    zskiplist *zsl;

    zsl = zmalloc(sizeof(*zsl));
    zsl->level = 1;
    zsl->length = 0;
    zsl->header = zslCreateNode(ZSKIPLIST_MAXLEVEL,0,NULL);

    // 初始化每一层,最多64层
    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;
}

#define ZSKIPLIST_MAXLEVEL 64 /* Should be enough for 2^64 elements */
#define ZSKIPLIST_P 0.25      /* Skiplist P = 1/4 */

// 生成随机层数
int zslRandomLevel(void) {
    int level = 1;
    while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF))
        level += 1;
    return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}

// 跳表插入元素
zskiplistNode *zslInsert(zskiplist *zsl, double score, sds ele)

// 查找某个元素的排名
unsigned long zslGetRank(zskiplist *zsl, double score, sds ele) 


标签:ZSKIPLIST,struct,zset,level,redis,zskiplistNode,源码,zsl
From: https://www.cnblogs.com/gdut17code/p/18238682

相关文章

  • 使用Redis计算两点经纬度距离
    Redis的GEO特性允许您存储地理位置信息并执行地理空间查询。这其中包括了计算两个地理位置之间的距离。以下是如何使用Redis中的相关命令来执行这项任务的详细解释。案例:步骤1:添加地理位置数据使用GEOADD命令向Redis添加地理位置数据。例如,我们添加两个城市的经纬度:GEOAD......
  • 基于VHDL的倒车雷达项目(免费提供全部源码)
    下载地址如下:基于VHDL的倒车雷达项目(免费提供全部源码)资源-CSDN文库1.项目介绍基于VHDL的倒车雷达项目旨在开发一种高效、可靠的倒车辅助系统,利用VHDL(VHSICHardwareDescriptionLanguage)语言实现雷达的核心逻辑控制。该项目的背景源于车辆安全性需求的不断提升,尤其是在停......
  • 基于SpringBoot+Mybatis+Redis的问答社交网站项目(免费提供全部源码)
    下载地址如下:基于SpringBoot+Mybatis+Redis的问答社交网站项目(免费提供全部源码)资源-CSDN文库项目介绍项目背景随着互联网的普及和社交媒体的快速发展,用户对于在线交流和信息分享的需求不断增加。问答社交网站作为一种新型的社交平台,为用户提供了一个交流知识、解决问题和......
  • 基于Nagao的统计词频项目(免费提供全部源码)
    下载地址如下:基于Nagao的统计词频项目(免费提供全部源码)资源-CSDN文库项目介绍背景与起源在当今信息爆炸的时代,文本数据的增长速度前所未有。无论是社交媒体上的帖子、新闻文章,还是学术论文,文本数据的数量和多样性都在不断增加。如何有效地分析这些文本数据,提取有价值的信息,......
  • 【跌倒检测】HMM+SVM形状特征跌倒检测 (含准确率)【含Matlab源码 4624期】
    ✅博主简介:热爱科研的Matlab仿真开发者,修心和技术同步精进,Matlab项目合作可私信。......
  • 【Redis】Redis主从复制(一)————主从搭建
    目录背景主从复制主从复制的工作流程主从复制的优点配置redis主从结构复制配置文件,修改配置主从结构启动redis服务备注查看复制状态背景单节点服务器的问题问题:可用性:如果这个机器挂了,意味着服务就中断了.性能:支持的并发量也是比较有限的.解决思路:引入分布......
  • Springboot计算机毕业设计疫情社区报备小程序【附源码】开题+论文+mysql+程序+部署
    本系统(程序+源码)带文档lw万字以上 文末可获取一份本项目的java源码和数据库参考。系统程序文件列表开题报告内容研究背景随着新冠疫情的全球蔓延,社区成为疫情防控的第一道防线。传统的人工报备方式不仅效率低下,而且难以实时追踪居民的流动情况,给疫情防控带来了极大的挑战......
  • Springboot计算机毕业设计疫情蔬菜供给系统演示录像2022【附源码】开题+论文+mysql+程
    本系统(程序+源码)带文档lw万字以上 文末可获取一份本项目的java源码和数据库参考。系统程序文件列表开题报告内容研究背景2022年,全球仍受到新冠疫情的深远影响。在疫情期间,人们的生活方式和消费习惯发生了显著变化,尤其是在食品采购方面。蔬菜作为日常生活的必需品,其供给稳......
  • 从VS Code源码看清晰代码之美
    VSCode的产品做的很优秀,其源码也质量颇高,清晰、整洁、富有美感。下面是 src\vs\workbench\common\notifications.ts 文件中的两段代码,大家感受一下:getsticky():boolean{if(this._sticky){returntrue;//explicitlysticky}consthasAct......
  • Springboot计算机毕业设计疫情防控平台微信小程序【附源码】开题+论文+mysql+程序+部
    本系统(程序+源码)带文档lw万字以上 文末可获取一份本项目的java源码和数据库参考。系统程序文件列表开题报告内容研究背景:在当今全球化和信息化的时代背景下,疫情的快速传播对社会稳定和人民生命健康构成了严重威胁。特别是在移动互联网高度发达的今天,如何利用科技手段有效......