Redis数据类型--ZSet类型详解及应用

weixin_42118323

2022人浏览 · 2024-02-28 09:30:00

weixin_42118323 · 2024-02-28 09:30:00 发布

数据结构

Redis无论什么数据类型，存储的时候都是以键值对key-value形势存储，并且所有的key都是String类型，本文讨论的数据类型是value的数据类型。

ZSet集合

概述：ZSet集合是一种有序不重复的数据结构，对比Set集合多了一个排序属性（分数：score），集合的元素按分数递增的顺序排序，分数相同则按字典顺序排序，这里的不重复指的是成员不重复，分数可以重复。

ZSet常用命令：

命令	描述
zadd key score1 value1 score2 value2 …	将一个或者多个成员添加到键为key的集合中
zcard key	统计键为key的集合中元素的数量
zcount key min max	返回键为kye的分数为min到max直接的元素数量
zincrby key increment member	给键为key的集合中的元素member分数加一
zrem key member1 member2 …	移除一个或多个元素
zrank key member	把元素按从小到大的顺序进行排序
zrevrank key member	把元素按从大到小的顺序进行排序
zremrangebyrank key start stop	移除指定的排名区间的所有元素
zremrangebyscore key min max	移除指定的分数区间的所有元素
zinterstore desKey nurnkeys key1 key2 key3 …	求多个有序集合的交集，结果保存在desKey中，nurnkeys 表示一共有多少个集合
zunionstore desKey numKeys key1 key2 key3 key4 …	求多个有序集合的并集，结果保存在desKey中，nurnkeys 表示一共有多少个集合

注意观察上面所有的命令都是以 Z开头，表示操作的是ZSet集合。

ZSet底层数据结构：
Zset底层数据结构是由压缩列表zipList和跳表skipList实现的：

如果元素的个数小于128个，并且每个元素的值小于64 byte的时候，ZSet会使用ziplist作为底层数据结构，。
不满足上述两个条件，则会使用skiplist作为ZSet的底层数据结构。
Redis 7.0 中，压缩列表数据结构已经废弃了，交由 listpack 数据结构来实现了。

skiplist： skiplist是一种可以快速查找的有序数据结构，其本质还是链表，它通过维护多级索引来实现快速查找，跳表的查找复杂度就是 O(logN)。

skiplist结构示意图：
在这里插入图片描述

ZSet源码分析：

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

dict：dict的作用是保存元素和到分数score映射，保证元素的唯一性，可以通过元素找到相应的score值。
zsl：按照分值从小到大保存了集合的所有元素，如果分值一样则按照元素字典排序，是一个跳表结构，每个节点都包含元素值和分数score。

注意：同时使用字典和跳表并不会浪费内存，因为可以通过指针共享元素和分值，并不会把一个元素存储多份。

zskiplist 源码分析：

typedef struct zskiplist {
    struct zskiplistNode *header, *tail;  
    unsigned long length;  
    int level; 
} zskiplist;

zskiplistNode： header，跳跃表的表头节点，tail，跳跃表的表尾节点。
length：记录跳跃表的元素长度（表头节点不计算在内）。
level：记录跳跃表的最大层数（表头节点的层数不计算在内）。

zskiplistNode 源码分析：

typedef struct zskiplistNode {
    sds ele;  
    double score;  
    struct zskiplistNode *backward; 
    struct zskiplistLevel {
        struct zskiplistNode *forward; 
        unsigned long span;
    } level[];
} zskiplistNode;

sds：SDS动态字符串结构，用来存储数据。
score：节点的分值，在跳跃表中，节点按各自所保存的分值从小到大排列。
backward：指向上一个节点的指针，回退指针，回退指针在程序从表尾向表头遍历时使用。
zskiplistLevel：包含两个字段，一个是forward，前进指针，指向该层下个能跳到的节点，span记录距离下一个节点的距离，数组结构表示每个节点都可能是多层结构。
level[]：一个节点的元素可以拥有多个层，数组中的每一个元素代表跳表的一层，通过不同层级的指针来选择最快捷的路径提升访问速度，比如 leve[0] 就表示第一层，leve[1] 就表示第二层。

平衡树，跳表，hash之间的对比?

类型	性能	优点	缺点
平衡树	查询、插入时间复杂度O(logn)	数据有序	平衡树的插入和删除操作可能引发子树的调整
skiplist	查询、插入时间复杂度O(logn)	实现简单、数据有序、支持范围查询	比平衡树性能略差
hash	查询插入性能都较好，时间复杂度O(1)	实现简单	存在哈希碰撞，数据无序，无法做范围查询

为什么使用跳表而不使用平衡树?

跳表内存占用比平衡树少一些，平衡树每个节点包含2个指针，而跳表每个节点包含的指针平均为 1/(1-p)，具体取决于参数 p 的大小，Redis里p=1/4，那理论上平均每个节点包含 1.33 个指针，比平衡树更少。
范围查找的时，跳表比平衡树更有优势。
跳表比平衡树更容易维护，平衡树在插入和删除的时候可能会导致子树分裂调整，逻辑复杂，而跳表的插入和删除只需要修改相邻节点的指针，操作简单。

ZSet的应用场景：
ZSet最好用最常用的场景就是各种排行榜。

如有不正确的地方请各位指出纠正。