Redis ZSet （5）

存储类型

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

数据结构对比

数据结构

是否允许重复

是否有序

有序实现方式

List

是

索引下标

Set

否

无

ZSet

否

是

score属性

1# 无序插入
2127.0.0.1:6379> zadd lzset 20 c 30 d 10 b 1 a
3(integer) 4
4
5# 获取数据是有序的
6127.0.0.1:6379> zrange lzset 0 -1 withscores
71) "a"
82) "1"
93) "b"
104) "10"
115) "c"
126) "20"
137) "d"
148) "30"

存储（实现）原理

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

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

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

1redis.conf配置
2
3zset-max-ziplist-entries 128
4zset-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更加简洁。

1/* ZSETs use a specialized version of Skiplists */
2typedef struct zskiplistNode {
3    sds ele; /*zset的元素*/
4    double score; /*分值*/
5    struct zskiplistNode *backward;/*后退指针*/
6    struct zskiplistLevel {
7        struct zskiplistNode *forward;/*前进指针，对应level的下一个节点*/
8        unsigned long span;/*从当前节点到下一个节点的跨度（跨越的节点数）*/
9    } level[];/* 层 */
10} zskiplistNode;
11
12typedef struct zskiplist {
13    struct zskiplistNode *header, *tail;/*指向跳跃表的头节点和尾节点*/
14    unsigned long length;/*跳跃表的节点数*/
15    int level;/*最大的层数*/
16} zskiplist;
17
18typedef struct zset {
19    dict *dict;
20    zskiplist *zsl;
21} zset;

随机获取层数的函数：（源码：t_zset.c）

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

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