Redis ZSet （5）

兜兜毛毛

发布于 2020-03-19 10:24:52

3580

发布于 2020-03-19 10:24:52

文章被收录于专栏：兜兜毛毛兜兜毛毛

存储类型

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，查找的路径是沿着下图中标红的指针所指向的方向进行的：

34首先和6(lev2)比较，再和18比较，比它们都大，继续向后比较。
但34和40比较的时候，比40要小，因此回到下面的链表（原链表lev1），与23比较。
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;
}

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

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法