专栏首页兜兜毛毛Redis ZSet (5)

Redis ZSet (5)

存储类型

ZSet集合基本与Set相同,只是多了一个数值类型属性score,score相同时,按照Key的ASC码排序。

数据结构对比

数据结构

是否允许重复

是否有序

有序实现方式

List

索引下标

Set

ZSet

score属性

# 无序插入
127.0.0.1:6379> zadd lzset 20 c 30 d 10 b 1 a
(integer) 4

# 获取数据是有序的
127.0.0.1:6379> zrange lzset 0 -1 withscores
1) "a"
2) "1"
3) "b"
4) "10"
5) "c"
6) "20"
7) "d"
8) "30"

存储(实现)原理

同时满足以下条件时使用ziplist编码:

  • 元素数量小于128个
  • 所有member的长度都小于64字节

在ziplist的内部,按照score排序递增来存储。插入的时候要移动之后的数据。

redis.conf配置

zset-max-ziplist-entries 128
zset-max-ziplist-value 64

超过阈值之后,使用skiplist+dict存储。

什么是skiplist?

下边是普通的有序列表

在这样一个链表中,如果我们要查找某个数据,那么需要从头开始逐个进行比较,直到找到包含数据的那个节点,或者找到第一个比给定数据大的节点为止(没找到)。也就是说,时间复杂度为O(n)。同样,当我们要插入新数据的时候,也要经历同样的查找过程,从而确定插入位置。

而二分查找法只适用于有序数组,不适用于链表。

假如我们每相邻两个节点增加一个指针(或者理解为有三个元素进入了第二层),让指针指向下下个节点。

这样所有新增加的指针连成了一个新的链表,但它包含的节点个数只有原来的一半(上图中是6,18,40)。在插入一个数据的时候,决定要放到那一层,取决于一个算法(在redis中t_zset.c有一个zslRandomLevel这个方法)。

现在当我们想查找数据的时候,可以先沿着这个新链表进行查找。当碰到比待查数据大的节点时,再回到原来的链表中的下一层进行查找。比如,我们想查找34,查找的路径是沿着下图中标红的指针所指向的方向进行的:

  1. 34首先和6(lev2)比较,再和18比较,比它们都大,继续向后比较。
  2. 但34和40比较的时候,比40要小,因此回到下面的链表(原链表lev1),与23比较。
  3. 34比23要大,沿下面的指针继续向后和40比较。34比40小,说明待查数据34在原链表中不存在

在这个查找过程中,由于新增加的指针,我们不再需要与链表中每个节点逐个进行比较了。需要比较的节点数大概只有原来的一半。这就是跳跃表。

为什么不用AVL树或者红黑树?因为skiplist更加简洁。
/* ZSETs use a specialized version of Skiplists */
typedef struct zskiplistNode {
    sds ele; /*zset的元素*/
    double score; /*分值*/
    struct zskiplistNode *backward;/*后退指针*/
    struct zskiplistLevel {
        struct zskiplistNode *forward;/*前进指针,对应level的下一个节点*/
        unsigned long span;/*从当前节点到下一个节点的跨度(跨越的节点数)*/
    } level[];/* 层 */
} zskiplistNode;

typedef struct zskiplist {
    struct zskiplistNode *header, *tail;/*指向跳跃表的头节点和尾节点*/
    unsigned long length;/*跳跃表的节点数*/
    int level;/*最大的层数*/
} zskiplist;

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

随机获取层数的函数:(源码:t_zset.c)

/* Returns a random level for the new skiplist node we are going to create.
 * The return value of this function is between 1 and ZSKIPLIST_MAXLEVEL
 * (both inclusive), with a powerlaw-alike distribution where higher
 * levels are less likely to be returned. */
int zslRandomLevel(void) {
    int level = 1;
    while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF))
        level += 1;
    return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}

适用于做排行榜,或者做简单队列优先级

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • MySQL 索引(3)

    索引是对数据库表中一列或多列的值进行排序的一种结构,使用索引可快速访问数据库表中的特定信息。

    兜兜毛毛
  • MySQL 事务(4)

    数据库事务( transaction)是访问并可能操作各种数据项的一个数据库操作序列,这些操作要么全部执行,要么全部不执行,是一个不可分割的工作单位。事务由事务...

    兜兜毛毛
  • 【项目记录】数据传输服务

    本人所在公司是做saas软件服务的,在做一个大客户专项时遇到集团企业需要管控子公司,希望可以夸租户管理。

    兜兜毛毛
  • Simple TPU的设计和性能评估

    在TPU中的脉动阵列及其实现中介绍了矩阵/卷积计算中的主要计算单元——乘加阵列(上图4),完成了该部分的硬件代码并进行了简单的验证;在 神经网络中的归一...

    sea-wind
  • 英伟达又出新卡皇TITAN Xp(下一代可能是TITAN Vista)

    问耕 发自 凹非寺 量子位 报道 | 公众号 QbitAI ? 简单通知一下,英伟达再次发布了TITAN Xp,接替了之前大概属于1080 Ti的“卡皇”地位。...

    量子位
  • 收藏 | 什么是设计?

    前段时间和拉钩网合作,让我来聊聊面试求职者的过程中喜欢问的问题和自己对这个问题的理解。由于我自己本身就是设计从业者,所以在面试求职者的过程中,除了会聊具体项目中...

    宇相
  • PySpark︱pyspark.ml 相关模型实践

    官方案例来源:https://spark.apache.org/docs/latest/api/python/pyspark.ml.html#pyspark.m...

    素质
  • 超实用!手把手教你从头构建UI设计系统

    以下内容由摹客团队翻译整理,仅供学习交流。摹客Mockplus是快速的原型设计工具。摹客iDoc是高效的在线协作设计平台。

    奔跑的小鹿
  • WGAN与WAE

    这种定义方式可以理解为所谓的“伪造者”,“判断者”用博弈论的方式理解,也可以视为分布拟合,窃以为后一种理解方式更为通用。接下来就可以进入主题看看WGAN的优化目...

    用户1908973
  • 使用多个网页工具预测MiRNA–mRNA相互作用

    所以大家如果也有miRNA列表,就可以使用它,肯定有人会以为我来图文并茂的讲解这个网页工具如何使用,那你错了,我不会做这么low的事情,麻烦走开。

    生信技能树

扫码关注云+社区

领取腾讯云代金券