Redis zset 底层结构

   概要

   在 Redis 的五种主要数据类型中，zset（有序集合）类型可能是最复杂，但也是最强大的一种。zset 不仅可以存储键值对，还可以为每个元素分配一个分数，然后根据这个分数进行排序。这使得 Zset 非常适合用于实现排行榜、时间线等功能。

   一、Zset底层结构

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

   1. 什么时候使用压缩链表，什么时候使用跳表呢 ？

   这主要取决于两个配置参数：zset-max-ziplist-entries （默认值为128 单位：个） 和 zset-max-ziplist-value （默认值为64，单位：字节）。

   使用压缩列表：当 zset 存储的元素数量小于 zset-max-ziplist-entries 的值，且所有元素的最大长度小于 zset-max-ziplist-value 的值时，Redis会选择使用压缩列表作为底层实现。压缩列表占用的内存较少，但是在需要修改数据时，可能需要对整个压缩列表进行重写，性能较低。

   使用跳跃表：当 zset 存储的元素数量超过 zset-max-ziplist-entries 的值，或者任何元素的长度超过 zset-max-ziplist-value 的值时，Redis 会将底层结构从压缩列表转换为跳跃表。跳跃表的查找和修改数据的性能较高，但是占用的内存也较多。

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

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

   3. 跳跃表 skiplist

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

   一个zset结构同时包含一个字典和一个跳跃表。跳跃表按score从小到大保存所有集合元素。而字典则保存着从member到score的映射，这样就可以用O(1)的复杂度来查找member对应的score值。虽然同时使用两种结构，但它们会通过指针来共享相同元素的member和score，因此不会浪费额外的内存。

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

 1 typedef struct zskiplistNode {
 2     robj *obj;
 3     double score;
 4     struct zskiplistNode *backward;
 5     struct zskiplistLevel {
 6         struct zskiplistNode *forward;
 7         unsigned int span;
 8     } level[];
 9 } zskiplistNode;
10 
11 typedef struct zskiplist {
12     struct zskiplistNode *header, *tail;
13     unsigned long length;
14     int level;
15 } zskiplist;

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

   zskiplist 结构体表示一个跳跃表，包含头节点（header）、尾节点（tail）、跳跃表中的节点数量（length）和当前跳跃表的最大层数（level）

   4. 小结

   当数据较少时：zset是由一个压缩链表来实现的

   当数据较多时：zset是由一个 字典+跳表 来实现的。简单来讲，dict用来查询数据到分数的对应关系，而skiplist用来根据分数查询数据（可能是范围查找）

   第1层链表不是一个单向链表，而是一个双向链表，这是为了方便以倒序方式获取一个范围内的元素。

   二、Redis跳表与MySQL B+树
   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的瓶颈，所以跳表层数的耗时可以忽略不计，而且插入数据时不需要开销以平衡数据结构（写多）。

   参考链接：https://juejin.cn/post/7114672722981945375