关于redis:Redis-系列redis-学习十四sortedset-初步探究梳理

sorted_set 是什么？

sorted_set 就是 zset ，是 redis 外面的数据之一，有序汇合

有序汇合是汇合的一部分，有序汇合给每个元素多设置了一个分数，相当于多了一个维度，redis 也是利用这个维度进行排序的

理论利用

redis-cli 连贯上 redis-server ，应用 help @sorted_set 查看有序联合反对的命令

# redis-cli -p 6379
127.0.0.1:6379> ping
PONG
127.0.0.1:6379>
127.0.0.1:6379> help @sorted_set

  BZPOPMAX key [key ...] timeout
  summary: Remove and return the member with the highest score from one or more sorted sets, or block until one is available
  since: 5.0.0
....

• summary

对这个命令的概括

• since

这个命令从 redis 哪一个版本就开始提供了

举个例子

在 sorted_set 中增加一个 key，这个key 外面有 3 个成员 ，3 个成员对应的分支如下：

127.0.0.1:6379> zadd k1 9 pig 2 dog 6 cat
(integer) 3

获取有序汇合的所有值，默认是依照无效到大的形式来展现，因为数据存入到 redis 内存中，物理内存的后果是从左到右，一一递增的

127.0.0.1:6379> ZRANGE k1 0 -1
1) "dog"
2) "cat"
3) "pig"

获取排名从小到大的前 2 位怎么做？

127.0.0.1:6379> ZRANGE k1 0 1 withscores
1) "dog"
2) "2"
3) "cat"
4) "6"

获取从大到小的排名前 2 位呢？

上面这个是正确的，应用 ZrevRANGE 来获取

127.0.0.1:6379> ZrevRANGE k1 0 1 withscores
1) "pig"
2) "9"
3) "cat"
4) "6"

上面这个是谬误的

127.0.0.1:6379> ZRANGE k1 -2 -1 withscores
1) "cat"
2) "6"
3) "pig"
4) "9"

例子2

咱们对以下几个学生设置分数，依照权重来做一个排名

127.0.0.1:6379> flushall
OK
127.0.0.1:6379> zadd k1 90 xiaoming 40 zhangsan 60 lisi
(integer) 3
127.0.0.1:6379> zadd k2 30 xiaohong 70 zhangsan 50 wangwu
(integer) 3
127.0.0.1:6379> ZUNIONSTORE unkey 2 k1 k2 weights 0.5 1
(integer) 5

依照权重来排序，k1 占比 0.5 ， k2 占比 1，计算排名，理论例子能够用来计算依照权重的总分

127.0.0.1:6379> ZUNIONSTORE unkey 2 k1 k2 weights 0.5 1
(integer) 5
127.0.0.1:6379> Zrange unkey 0 -1 withscores
 1) "lisi"
 2) "30"
 3) "xiaohong"
 4) "30"
 5) "xiaoming"
 6) "45"
 7) "wangwu"
 8) "50"
 9) "zhangsan"
10) "90"

k1 和 k1 取成员的最大值来进行排名，理论例子能够是多个科目问题的最高分进行排名

127.0.0.1:6379> ZUNIONSTORE unkey2 2 k1 k2 aggregate max
(integer) 5
127.0.0.1:6379> zrange unkey2 0 -1 withscores
 1) "xiaohong"
 2) "30"
 3) "wangwu"
 4) "50"
 5) "lisi"
 6) "60"
 7) "zhangsan"
 8) "70"
 9) "xiaoming"
10) "90"

那么咱们思考一下，sorted_set 的排序是如何实现的呢？

sorted_set 排序实现原理

排序是通过 skiplist 跳表来实现的，skiplist 是一个类均衡树

skiplist 实质上也是一种查找构造，用于解决算法中的查找问题

Redis外部数据结构详解 这本书中有说到，查找问题的解法有如下 2 类：

• 基于各种均衡树
• 基于哈希表

skiplist 跳表 不属于上述任何一个，他能够说是一个 类均衡树

咱们来举个例子：

例如有如下跳表，总共有 3 层

当初要将 15 这个数字插入这个跳表

用 15 去第一层看，比 2 大，那么往下走

15 比 23 小且比 2 大，那么往下走

15 比 23 小，比 8 大，那么 15 就插入这里了

插入这里，第三层 8 的指针 指向 15, 23的指针也指向 15

第二层 2 的指针 指向 15，15 指向 23

第三层 2 的指针也指向 15， 15 指向 NULL

依据下面这个例子，咱们能够明确，skiplist 就是一个非凡的链表，叫做跳表，或者是跳跃表

咱们还发现，这么多层链表，就是最上面这一层的链表元素是最全的，其余层都是稠密的链表，这些链表外面的指针成心跳过了一些节点（越高层的链表跳过的节点越多）

这就使得咱们在查找数据的时候可能先在高层的链表中进行查找，而后逐层升高，最终降到第一层链表来准确地确定数据地位

这种形式过程中是跳过了很多节点的，因而也就放慢了咱们的查找速度

无论是增删改查，都是须要先查问的，先明确查找到须要操作的地位，再进行操作

skiplist和均衡树、哈希表的比拟

咱们查看到 redis src/server.h 中有对 skiplist 的构造定义

/* ZSETs use a specialized version of Skiplists */
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;
    unsigned long length;
    int level;
} zskiplist;

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

zskiplist ，跳跃表

zskiplist 定义了真正的skiplist构造：

• 头指针header和尾指针tail。

• 链表长度length，即链表蕴含的节点总数

  这里须要留神一点：

  新创建的 skiplist 蕴含一个空的头指针，这个头指针不蕴含在 length 计数中

• level示意skiplist的总层数，就是所有节点层数的最大值

zskiplistNode ， 跳跃表的节点

zskiplistNode 定义了 skiplist 的节点构造：

• 寄存的是sds，zadd命令在将数据插入到skiplist外面之前先进行了解码，这样做的目标应该是为了不便在查找的时候对数据进行字典序的比拟
• score 字段是数据对应的分数
• backward 字段是指向链表前一个节点的指针（前向指针），每一个节点只有1个前向指针，所以只有第1层链表是一个双向链表。

• level[] 寄存指向各层链表后一个节点的指针（后向指针）

  每层对应1个后向指针，用forward字段示意。

• span值 ，是每个后向指针还对应了一个 span，它示意以后的指针逾越了多少个节点span用于计算元素排名(rank)

对于 redis 源码中，创立节点，插入节点，删除节点的源码都在 src/t_zset.c 外面，具体的源码流程感兴趣的能够细细品读一下，还在品读中

参考资料：

• redis_doc
• reids 源码 src/t_zset.c 和 src/server.h

欢-迎点赞，关注，珍藏

敌人们，你的反对和激励，是我保持分享，提高质量的能源

好了，本次就到这里

技术是凋谢的，咱们的心态，更应是凋谢的。拥抱变动，背阴而生，致力向前行。

我是小魔童哪吒，欢送点赞关注珍藏，下次见~