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

川长思鸟来 2023-10-15 11:19 42阅读 0赞

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

--------------------

### 文章目录 ###

*   *   *   *  1、Zset数据类型
             *   *  1.1、Zset类型简介
                 *  1.2、Zset应用场景
             *  3、Zset底层结构
             *   *  3.1、Zset底层结构介绍
                 *  3.2、压缩列表（ziplist）
                 *  3.3、跳跃表（skiplist）
                 *  3.4、Redis跳表与MySQLB+树
         *  3、ZSet 常用命令
         *   *   *  2.1、添加操作
                 *  2.2、返回指定成员分数
                 *  2.3、返回指定成员排名
                 *  2.4、其他Zset命令

--------------------

#### 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 会选择使用压缩列表作为底层实现。

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

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

<table> 
 <thead> 
  <tr> 
   <th align="center">属性</th> 
   <th align="center">说明</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="center">“zlbytes”</td> 
   <td align="center">一个 4 字节的整数，表示整个压缩列表占用的字节数量，包括 <code>&lt;zlbytes&gt;</code> 自身的大小。</td> 
  </tr> 
  <tr> 
   <td align="center">“zltail”</td> 
   <td align="center">一个 4 字节的整数，表示压缩列表中最后一个元素的偏移量。这个偏移量是相对于整个压缩列表的起始地址的。</td> 
  </tr> 
  <tr> 
   <td align="center">“zllen”</td> 
   <td align="center">一个 2 字节的整数，表示压缩列表中的元素数量。如果元素数量超过 65535，那么这个值就会被设定为 65535，需要遍历整个压缩列表才能获取到实际的元素数量。</td> 
  </tr> 
  <tr> 
   <td align="center">“entry”</td> 
   <td align="center">压缩列表中的元素，每个元素都由一个或多个字节组成。每个元素的第一个字节（又称为"entry header"）用于表示这个元素的长度以及编码方式。</td> 
  </tr> 
  <tr> 
   <td align="center">“zlend”</td> 
   <td align="center">一个字节，值为 255，表示压缩列表的结束。</td> 
  </tr> 
 </tbody> 
</table>

在 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 次

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

![image-20230813003024371][]

一次索引，遍历 5 个节点![image-20230813003046618][]

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

![image-20230813003139323][]

二索引，遍历 5 个节点

![image-20230813003238511][]

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

##### 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 的官方文档。

[image-20230813003024371]: https://img-blog.csdnimg.cn/img_convert/18a94498a02911aec66bf084800ffa13.png
[image-20230813003046618]: https://img-blog.csdnimg.cn/img_convert/2b7fbcec4b46b811988b095aefb70cf0.png
[image-20230813003139323]: https://img-blog.csdnimg.cn/img_convert/4fa452cfce84f59e16266f5d69cc3a85.png
[image-20230813003238511]: https://img-blog.csdnimg.cn/img_convert/c0e811743a701266ac0d3711b7978d9e.png