前言

如果Redis面试有什么必问的面试题，那么Zset的底层原理一定是排名前三的。

在上篇文章中我们提到ZSET的底层实现是ziplist压缩列表 和skiplist 跳跃表。

这篇文章我们就详细讲解：

• zset是什么
• zset怎么用
• zset的原理是什么。

让你轻松秒杀面试官，获得Offer。

Zset是什么

Redis ZSET(Sorted Set) 有序集合，ZSET中的成员是有序排列的。

它和 set 集合的相同之处在于：

• 集合中的每一个成员都是字符串类型，并且不允许重复

而它们最大区别是：

• zset 是有序的
• set 是无序的

这是因为有序集合中每个成员都会关联一个 double64（双精度浮点数）类型的 score (分数值)，Redis 正是通过 score 实现了对集合成员的排序。

zset 是 Redis 常用数据类型之一，它适用于排行榜类型的业务场景。

Redis 使用以下命令创建一个有序集合：

1

127.0.0.1:6379> ZADD key score member [score member ...]  

• key：指定一个键名；
• score：分数值，用来描述 member，它是实现排序的关键；
• member：要添加的成员（元素）。

也就是，一个ZSET里面有多个 <score, member> 的pair，通过member的score来排序，最终你就得到了一个有序的member列表。

比如：member是用户ID，score是这个用户ID的战力值。那么你使用ZSET很容易得到一个排行榜，以score排好序的member列表

当 key 不存在时，将会创建一个新的有序集合，并把分数/成员（score/member）添加到有序集合中；当 key 存在时，但 key 并非 zset 类型，此时就不能完成添加成员的操作，同时会返回一个错误提示。

在有序集合中，成员是唯一存在的，但是分数（score）却可以重复。有序集合的最大的成员数为 2^32 - 1 (大约 40 多亿个)。

**注意：**score使用的是double64，精度只有53bit。所以如果使用int64作为score的请注意，不要超过53位，否则会截断，导致排序不符合你的预期。

官网页面有描述精度问题：Redis ZAdd

ZSET怎么用

最简单的增删改查，统计数量，范围查找，交集并集等等都是很方便的支持的。完成的命令可以查看官网文档：sorted-set

几个最简单的例子：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

# key: fighting_rank, member: ana, score: 100000
127.0.0.1:6379> ZADD fighting_rank 100000 "ana"

# 取排行榜前三名
127.0.0.1:6379> ZREVRANGE fighting_rank 0 2
1) "fff"
2) "eee"
3) "ddd"

# zset长度
127.0.0.1:6379> ZCARD fighting_rank
4

# 取某一个member的score
127.0.0.1:6379> ZSCORE fighting_rank "aaa"
100000.0

你也可以自己在线测试Redis的命令来熟悉。https://try.redis.io/

ZSET底层实现

我们讲了ZSET是什么，以及ZSET怎么用，相信你已经在脑海中对Redis ZSET有了初步的概念。那下一步我们就要讲解ZSET的核心，底层是怎么实现的。让你了解这个数据结构的设计有多优秀。

上面我们说过，ZSET底层使用ziplist和skiplist实现。

并不是两个都会用到，而是二选一的。在满足以下条件的时候会使用ziplist：

• 保存元素（member）数量小于128
• 每个元素（member）长度小于64字节

注意：这两个参数可以通过redis.conf里面的zset-max-ziplist-entries 选项和 zset-max-ziplist-value 进行修改。

1
2
3
4
5

# Similarly to hashes and lists, sorted sets are also specially encoded in
# order to save a lot of space. This encoding is only used when the length and
# elements of a sorted set are below the following limits:
zset-max-ziplist-entries 128
zset-max-ziplist-value 64

1. ziplist 压缩列表

压缩列表（ziplist）是Redis为了节省内存而开发的，是由一系列特殊编码的连续内存块组成的顺序型数据结构，一个压缩列表可以包含任意多个节点（entry）。ziplist就是为了节省内存redis会用时间换空间的典型例子。

解决问题

• 内存紧凑型列表，节省内存空间、提升内存使用率

存在问题

• 查询效率O(n)
• 内存重分配
• 连锁更新

当 ziplist 保存的元素过多时，查找中间数据的复杂度就增加了。更糟糕的是，如果 ziplist 里面保存的是字符串，ziplist 在查找某个元素时，还需要逐一判断元素的每个字符，这样又进一步增加了复杂度。查询效率O(n)。

所以Redis zset使用ziplist要限制元素的总数量和每个元素的长度上限。因为超过这个值之后使用ziplist的优势就没有了，就会自动切换成skiplist。

这里你应该明白了，为什么在数据量和长度比较小的时候使用ziplist了，因为Redis的瓶颈之一就是内存，所以Redis的设计极致的考虑了内存的使用。在数据量较少的时候，ziplist充分体现了它内存的优势，又不会影响整体的查询效率。

zset中entry的添加

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

unsigned char *zzlInsertAt(unsigned char *zl, unsigned char *eptr, sds ele, double score) {
    // some code hide here
    // ...

    /* Keep offset relative to zl, as it might be re-allocated. */
    offset = eptr-zl;
    zl = ziplistInsert(zl,eptr,(unsigned char*)ele,sdslen(ele));
    eptr = zl+offset;

    /* Insert score after the element. */
    serverAssert((sptr = ziplistNext(zl,eptr)) != NULL);
    zl = ziplistInsert(zl,sptr,(unsigned char*)scorebuf,scorelen);

    return zl;
}

自动转换编码格式

如果发现满足ziplist的规则（长度小于等于128且最大的元素的长度小于等于64）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

/* Convert the sorted set object into a ziplist if it is not already a ziplist
 * and if the number of elements and the maximum element size is within the
 * expected ranges. */
void zsetConvertToZiplistIfNeeded(robj *zobj, size_t maxelelen) {
    if (zobj->encoding == OBJ_ENCODING_ZIPLIST) return;
    zset *zset = zobj->ptr;

    if (zset->zsl->length <= server.zset_max_ziplist_entries &&
        maxelelen <= server.zset_max_ziplist_value)
            zsetConvert(zobj,OBJ_ENCODING_ZIPLIST);
}

可以看到，在作为zset实现的时候，每当插入一个<member, score> pair，就insert了两个连续的entry，第一个为member，第二个为score。

总结

ziplist是为节省内存空间而生的。 ziplist是一个为Redis专门提供的底层数据结构之一，本身可以有序也可以无序。当作为list和hash的底层实现时，节点之间没有顺序；当作为zset的底层实现时，节点之间会按照大小顺序排列。 如果长度变化的时候会检查是否满足规则，底层结构会在ziplist和skiplist之间转换。

2. skiplist 跳跃表

概念

跳跃表是一种有序的数据结构，它通过在每个节点中维持多个指向其它节点的指针，从而达到快速访问节点的目的。

跳跃表支持平均O(logN)复杂度的节点查找，还可以通过顺序性操作来批量处理节点。

如果任意一个条件不满足，就会Convert为SKIPLIST底层实现。

1
2
3
4
5
6
7

/* Optimize: check if the element is too large or the list
 * becomes too long *before* executing zzlInsert. */
zobj->ptr = zzlInsert(zobj->ptr,ele,score);
if (zzlLength(zobj->ptr) > server.zset_max_ziplist_entries)
    zsetConvert(zobj,OBJ_ENCODING_SKIPLIST);
if (sdslen(ele) > server.zset_max_ziplist_value)
    zsetConvert(zobj,OBJ_ENCODING_SKIPLIST);

这里的OBJ_ENCODING_SKIPLIST，实际上是skiplist(跳跃表)+dict（字典）。

为什么要这么设计呢？我们知道数据量大的时候才会使用skiplist，skiplist的查询时间复杂度为O(logN)。

dict保存着member到score的映射，这样就可以使用O(1)的复杂度来查找member对应的score值。虽然同时使用两种结构，但它们会通过指针来共享相同元素的 member 和 score，因此不会浪费额外的内存。

1
2
3

tmp = zuiNewSdsFromValue(&zval);
znode = zslInsert(dstzset->zsl,score,tmp);
dictAdd(dstzset->dict,tmp,&znode->score);

就是为了性能而做的考虑。

为什么使用跳跃表（skiplist）而不使用平衡树

Redis使用SkipList而不是用平衡树的主要原因有：

1. 平衡树不适合范围查找。需要中序遍历继续寻找其它节点。而Skiplist就非常简单了，使用lv1的指针进行向右遍历即可。
2. 平衡树的插入和删除引发子树调整，逻辑复杂，SkipList相对简单很多
3. 平衡树每个节点包含两个指针，SkipList平均不到2个指针，内存上更有优势。
4. 从算法实现难度上来比较，Skiplist 比平衡树要简单得多。

结论

看了Redis ZSET的实现，不得不感叹，Redis的设计真的优秀，每个细节都考虑到了，对内存的使用有着完美的执着。这也就是为什么Redis能火，成为互联网公司必使用的技术之一。也是程序员面试的必面类型之一。了解Redis不仅能让你轻松通过面试，也能让你掌握更多知识，轻松应付工作中的各种需求。

<全文完>