Redis数据结构：Zset类型全面解析

Redis，作为一种高性能的键值对数据库，因其丰富的数据类型和高效的性能而受到了广泛的关注和使用。在 Redis 的五种主要数据类型中，Zset（有序集合）类型可能是最复杂，但也是最强大的一种。Zset 不仅可以存储键值对，还可以为每个元素分配一个分数，然后根据这个分数进行排序。这使得 Zset 非常适合用于实现排行榜、时间线等功能。 在这篇文章中，我们将全面解析 Redis 的 Zset 类型。我们将从 Zset 的基本概念和特性开始，然后深入到它的内部实现和性能优化。我们还将通过实际的示例来展示如何在实际应用中使用 Zset。无论你是刚接触 Redis，还是已经有一定经验的开发者，我相信你都能从这篇文章中学到一些有用的知识。

1、Zset数据类型

1.1、Zset类型简介

Zset，即有序集合（Sorted Set），是 Redis 提供的一种复杂数据类型。Zset 是 set 的升级版，它在 set 的基础上增加了一个权重参数 score，使得集合中的元素能够按 score 进行有序排列。

在 Zset 中，集合元素的添加、删除和查找的时间复杂度都是 O(1)。这得益于 Redis 使用的是一种叫做跳跃列表（skiplist）的数据结构来实现 Zset。

Zset 的主要特性包括：

1. 唯一性：和 set 类型一样，Zset 中的元素也是唯一的，也就是说，同一个元素在同一个 Zset 中只能出现一次。
2. 排序：Zset 中的元素是有序的，它们按照 score 的值从小到大排列。如果多个元素有相同的 score，那么它们会按照字典序进行排序。
3. 自动更新排序：当你修改 Zset 中的元素的 score 值时，元素的位置会自动按新的 score 值进行调整。

1.2、Zset应用场景

Redis 的 Zset（有序集合）类型在许多场景中都非常有用，以下是一些常见的应用场景：

1. 排行榜：Zset 非常适合用于实现各种排行榜。例如，你可以将用户的 ID 作为元素，用户的分数作为分数，然后使用 Zset 来存储和排序所有用户的分数。你可以很容易地获取到分数最高的用户，或者获取到任何用户的排名。
2. 时间线：你可以使用 Zset 来实现时间线功能。例如，你可以将发布的消息作为元素，消息的发布时间作为分数，然后使用 Zset 来存储和排序所有的消息。你可以很容易地获取到最新的消息，或者获取到任何时间段内的消息。
3. 带权重的队列：Zset 可以用于实现带权重的队列。例如，你可以将任务作为元素，任务的优先级作为分数，然后使用 Zset 来存储和排序所有的任务。你可以很容易地获取到优先级最高的任务，或者按优先级顺序执行任务。
4. 延时队列：你可以将需要延时处理的任务作为元素，任务的执行时间作为分数，然后使用 Zset 来存储和排序所有的任务。你可以定期扫描 Zset，处理已经到达执行时间的任务。

以上只是 Zset 的一些常见应用场景，实际上，Zset 的应用非常广泛，只要是需要排序和排名功能的场景，都可以考虑使用 Zset。

3、Zset底层结构

3.1、Zset底层结构介绍

Redis 的 Zset（有序集合）类型的底层实现会根据实际情况选择使用压缩列表（ziplist）或者跳跃表（skiplist）。Redis 会根据实际情况动态地在这两种底层结构之间切换，以在内存使用和性能之间找到一个平衡。

这主要取决于两个配置参数：zset-max-ziplist-entries 和 zset-max-ziplist-value。

1. 使用压缩列表：当 Zset 存储的元素数量小于 zset-max-ziplist-entries 的值，且所有元素的最大长度小于 zset-max-ziplist-value 的值时，Redis 会选择使用压缩列表作为底层实现。压缩列表占用的内存较少，但是在需要修改数据时，可能需要对整个压缩列表进行重写，性能较低。
2. 使用跳跃表：当 Zset 存储的元素数量超过 zset-max-ziplist-entries 的值，或者任何元素的长度超过 zset-max-ziplist-value 的值时，Redis 会将底层结构从压缩列表转换为跳跃表。跳跃表的查找和修改数据的性能较高，但是占用的内存也较多。

这两个参数都可以在 Redis 的配置文件中进行设置。通过调整这两个参数，你可以根据自己的应用特性，选择更倾向于节省内存，还是更倾向于提高性能。

3.2、压缩列表（ziplist）

压缩列表是一种为节省内存而设计的特殊编码结构，它将所有的元素和分数紧凑地存储在一起。这种方式的优点是占用内存少，但是在需要修改数据时，可能需要对整个压缩列表进行重写，性能较低。当 Zset 存储的元素数量较少，且元素的字符串长度较短时，Redis 会选择使用压缩列表作为底层实现。

一个压缩列表的结构如下：

+---------+---------+--------+---------+---------+---------+--------+
| zlbytes | zltail  | zllen  | entry_1 | entry_2 |  ...    | zlend  |
+---------+---------+--------+---------+---------+---------+--------+

Ps：在 Redis 的源代码中，压缩列表（ziplist）的结构并没有直接定义为一个 C 结构体，而是通过一系列的宏和函数来操作一段连续的内存。

在 Zset 中，每个元素和它的分数都会作为一个独立的元素存储在压缩列表中，元素和分数会交替存储，即第一个元素是成员，第二个元素是分数，第三个元素是成员，第四个元素是分数，以此类推。

压缩列表的优点是占用内存少，但是在需要修改数据时，可能需要对整个压缩列表进行重写，性能较低。

3.3、跳跃表（skiplist）

跳跃表是一种可以进行快速查找的有序数据结构，它通过维护多级索引来实现快速查找。这种方式的优点是查找和修改数据的性能较高，但是占用的内存也较多。当 Zset 存储的元素数量较多，或者元素的字符串长度较长时，Redis 会选择使用跳跃表作为底层实现。

跳跃表（skiplist）是一种可以进行快速查找的有序数据结构，它通过维护多级索引来实现快速查找。

在 Redis 的源代码中，跳跃表的结构定义如下：

typedef struct zskiplistNode {
    robj *obj;
    double score;
    struct zskiplistNode *backward;
    struct zskiplistLevel {
        struct zskiplistNode *forward;
        unsigned int span;
    } level[];
} zskiplistNode;

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

其中：

• zskiplistNode 结构体表示跳跃表中的一个节点，包含元素对象（obj）、分数（score）、指向前一个节点的指针（backward）和一个包含多个层的数组（level）。每一层都包含一个指向下一个节点的指针（forward）和一个表示当前节点到下一个节点的跨度（span）。
• zskiplist 结构体表示一个跳跃表，包含头节点（header）、尾节点（tail）、跳跃表中的节点数量（length）和当前跳跃表的最大层数（level）。

跳跃表的查找、插入和删除操作的时间复杂度都是 O(logN)，其中 N 是跳跃表中的元素数量。这使得跳跃表在处理大量数据时具有很高的性能。

跳表在链表的基础上增加了多级索引，通过多级索引位置的专跳，实现了快速查找元素

比如下面，查找 27 ，需要遍历 6 次

一级索引（每间隔一个元素）：

一次索引，遍历 5 个节点

二级索引（一次索引基础上，每间隔一个元素）：

二索引，遍历 5 个节点

本身利用的思想类似于二分法

3.4、Redis跳表与MySQLB+树

MySQL 的 B+ 树和 Redis 的跳表都是用于存储有序数据的数据结构，但它们有一些关键的区别，使得它们在不同的场景和用途中各有优势。

1. 结构差异：B+ 树是一种多路搜索树，每个节点可以有多个子节点，而跳表是一种基于链表的数据结构，每个节点只有一个下一个节点，但可以有多个快速通道指向后面的节点。
2. 空间利用率：B+ 树的磁盘读写操作是以页（通常是 4KB）为单位的，每个节点存储多个键值对，可以更好地利用磁盘空间，减少 I/O 操作。而跳表的空间利用率相对较低。
3. 插入和删除操作：跳表的插入和删除操作相对简单，时间复杂度为 O(logN)，并且不需要像 B+ 树那样进行复杂的节点分裂和合并操作。
4. 范围查询：B+ 树的所有叶子节点形成了一个有序链表，因此非常适合进行范围查询。而跳表虽然也可以进行范围查询，但效率相对较低。

因此，B+ 树和跳表不能简单地相互替换。在需要大量进行磁盘 I/O 操作和范围查询的场景（如数据库索引）中，B+ 树可能是更好的选择。而在主要进行内存操作，且需要频繁进行插入和删除操作的场景（如 Redis）中，跳表可能更有优势。

Mysql 为什么使用 B +树，而不是跳表？

Mysql 数据库是持久化数据库，即是存储到磁盘上的，因此查询时要求更少磁盘 IO，且 Mysql 是读多写少的场景较多，显然 B+ 树更加适合M ysql。

Redis 的 ZSet 为什么使用跳表而不是B+树

Redis 是内存存储，不存在 IO 的瓶颈，所以跳表的层数的耗时可以忽略不计，而且插入数据时不需要开销以平衡数据结构（写多）。

3、ZSet 常用命令

2.1、添加操作

在 Redis 中，ZADD 命令用于向有序集合（Zset）中添加一个或多个成员，或者更新已存在成员的分数。它的基本语法如下：

ZADD key score member [score member ...]

其中，key 是有序集合的名称，score 是成员的分数，member 是成员的值。你可以一次添加一个或多个成员。

例如，你可以使用以下命令向名为 myzset 的有序集合中添加一个成员 one，其分数为 1：

ZADD myzset 1 one

如果你想要一次添加多个成员，可以在命令后面依次列出它们的分数和值，例如：

ZADD myzset 1 one 2 two 3 three

这个命令会向 myzset 集合中添加三个成员，它们的分数分别为 1、2 和 3。

如果添加的成员在有序集合中已经存在，那么它的分数会被更新为新的值，同时该成员在集合中的位置也会相应地发生变化。

2.2、返回指定成员分数

在 Redis 中，ZSCORE 命令用于返回有序集合（Zset）中，指定成员的分数。它的基本语法如下：

ZSCORE key member

其中，key 是有序集合的名称，member 是要查询分数的成员。

例如，你可以使用以下命令查询名为 myzset 的有序集合中，成员 one 的分数：

ZSCORE myzset one

如果指定的成员存在于有序集合中，那么命令会返回该成员的分数。如果指定的成员不存在于有序集合中，那么命令会返回 nil。

需要注意的是，ZSCORE 命令返回的分数是字符串形式的浮点数。

2.3、返回指定成员排名

在 Redis 中，ZRANK 命令用于返回有序集合（Zset）中指定成员的排名，其中分数值从低到高排序。它的基本语法如下：

ZRANK key member

其中，key 是有序集合的名称，member 是要查询排名的成员。

例如，你可以使用以下命令查询名为 myzset 的有序集合中，成员 one 的排名：

ZRANK myzset one

如果指定的成员存在于有序集合中，那么命令会返回该成员的排名。排名以 0 为底，也就是说，分数最低的成员排名为 0。

如果指定的成员不存在于有序集合中，那么命令会返回 nil。

需要注意的是，ZRANK 命令返回的排名是字符串形式的整数。

2.4、其他Zset命令

Redis 中 Zset 其他的一些常用命令还有：

1. ZREVRANK key member：返回有序集合中指定成员的索引，分数值从高到低排序。
2. ZRANGE key start stop [WITHSCORES]：返回有序集中，指定区间内的成员。
3. ZREVRANGE key start stop [WITHSCORES]：返回有序集中，指定区间内的成员，通过索引，分数值从高到低。
4. ZREM key member [member …]：移除有序集合中的一个或多个成员。
5. ZCARD key：获取有序集合的成员数。
6. ZCOUNT key min max：计算在有序集合中指定区间分数的成员数。
7. ZINCRBY key increment member：为有序集合中的成员添加增量。

以上只是 Zse 其他 Hash 命令的一些常用命令，更多的命令和详细的使用方法，可以查阅 Redis 的官方文档。