专栏首页golang+phpredis源码之zset结构的实现

redis源码之zset结构的实现

zset为有序的,自动去重的集合数据类型,zset数据结构底层实现为字典(dict)+跳表(skiplist)当数据比较少时,用ziplist编码数据结构存储,当满足以下条件之一时,则采用字典+跳表来存储

zset-max-ziplist-entries 128 //元素个数超过128,将用skiplist编码 zset-max-ziplist-value 64 //单个元素大小超过64byte,将用skiplist编码

typedef struct zset {
    dict *dict;
    zskiplist *zsl;
} zset;

对于字典(dict)的数据结构来说,可以用O(1)的复杂度拿到对应元素 比如zscore命令 zscore key value 就可以拿到以key为键,value的对应的分值,这个就是在字典(dict)的数据结构中取的,字典(dict)数据结构主要用于判断值是否存在以及拿对应的分值,这个不是我们文章阐述的重点,重点看一下跳跃表(skiplist)的数据结构,看看它是如何实现排序的

skiplist的实现

首先我们来看一看链表的数据结构示意图

链表的话查找我们所需的元素的时间复杂度为O(n),显然这是我们不能接受的,所以需要对链表进行一步改造

我们每隔两个元素给加一层,然后我们查询从索引层开始查询,遇到了比目标元素大的元素再返回,前往数据层来查询,这样速度会快一些,但是这样速度快的不明显,大概也就快了一半左右,于是我们便想到了加高层数

其实按照上图我们可以计算一下 元素的总个数为N 那么在上图的所以第一层,元素的个数为n/2 index: 1 n/2

那么在上图的所以第二层,元素的个数为n/2^2 index: 2 n/2^2

那么在上图的所以第三层,元素的个数为n/2^3 index: 3 n/2^3

那么在上图的所以第K层,元素的个数为n/2^k index: k n/2^k

比如顶层为2个节点 2 = n/2^k 也就是说 2^k = n/2 ----> k=log2(n-1) 加上数据层的话 k = log2 n 所以我们的层高是 log2 n 查找的时候的时间复杂度是log n

我们可以来看一下skiplist的源码

// zskiplistNode包含了数据和索引,也就是跳表中的一列
typedef struct zskiplistNode {
    sds ele;  //元素
    double score; //分数
    struct zskiplistNode *backward; //往前指的指针
    struct zskiplistLevel {
        struct zskiplistNode *forward;//往后指的指针
        unsigned long span; // 从当前节点到下一个节点的跨度
    } level[];
} zskiplistNode;


typedef struct zskiplist {
    struct zskiplistNode *header, *tail;   //header和tail是方便双向遍历
    unsigned long length; //当前数据包含元素个数
    int level;  // 层高
} zskiplist;

skiplist.png

如何确定索引层的层高

索引层的层高是由一个随机函数,幂次定律实现的

int zslRandomLevel(void) { //幂次定律,随机生成层高,越高的层出现概率越低
    int level = 1;
    while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF))
        level += 1;
    return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}

本文分享自微信公众号 - 程序员养成日记(programmer_grow),作者:程序员养成日记

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-10-13

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • php运行生命周期--模块初始化php_module_startup

    函数的前半部分主要还是对SG宏的成员变量进行初始化。后半部分先是调用了sapi_module_struct内部实现的activate函数,又调用了input_f...

    程序员养成日记
  • redis源码之list结构的实现

    关于redis的list的常用命令就不多说了 常用的命令lpush,rpush,lpop,rpop,lrangge等,这个不错过多的演示,相信研究源码的同学应该...

    程序员养成日记
  • https详解

    HTTP是属于应用层的协议,它是基于TCP/IP的,所以它只是规定一些要传输的内容,以及头部信息,然后通过TCP协议进行传输,依靠IP协议进行寻址,通过一幅最简...

    程序员养成日记
  • 空洞卷积(dilated convolution)深入详解——优点与缺点

    三、空洞卷积的拯救之路:Dilated Convolution to the Rescue

    小草AI
  • 反编译一款小说阅读软件 android逆向(三)

    用户1127566
  • 个人电脑也做做宏基因组玩玩

    宏基因组分析,首先需要的结果是获得物种分类信息,前面我们提到,宏基因组有两种分析方式分别是基于序列比对和组装的,组装对电脑硬件的要求是超级高的,不过比对,就轻松...

    用户1075469
  • 独家解读 | 新闻分析数据哪家强?

    数据是量化投资的根本,传统的量价数据、基本面数据已经被玩坏的时候,越来越多的机构意识到另类数据的重要性。说到另类数据,卫星数据、GPS数据、航运数据等另类数据届...

    量化投资与机器学习微信公众号
  • Python调用autoit

    1. 安装pywin32模块,地址:http://sourceforge.net/projects/pywin32/  选择对应的版本下载

    py3study
  • 新闻客户端就这样吃上大数据

    近日网易新闻客户端在广州发布了“解码城市态度”数据报告,基于大数据挖掘,从文化、商业、生活等五个维度给大家呈现了广州这座城市。这一活动还将陆续在青岛、成都、上海...

    罗超频道
  • PyQt 编程入门(一)

    下面的程序会显示一个简单的窗口,可以最大化,最小化,调整大小以及关闭它。程序的风格是面向过程式编程。

    用户6021899

扫码关注云+社区

领取腾讯云代金券