Redis 有序集合（Sorted Set）的压缩列表（`ziplist`）与跳跃表（`skiplist`）编码选择 - 智猿学院-前后端，数据库，人工智能，云计算等领域前沿技术讲座

Redis 有序集合：压缩列表 vs. 跳跃表，一场速度与激情的较量！🚀

大家好！欢迎来到今天的“Redis 奇妙夜”！🌃 今晚我们要聊聊 Redis 中一个非常有趣的数据结构：有序集合（Sorted Set）。这玩意儿，就好比班里的学霸排行榜，既要按成绩排序，又要能快速找到指定名字的同学。

但是！学霸榜也有不同的实现方式，Redis 给了我们两个选择：压缩列表（ziplist）和跳跃表（skiplist）。这两兄弟，一个身材娇小，追求极致的存储效率；另一个身手矫健，擅长高速的查找操作。那么问题来了，到底什么时候该选谁呢？别急，今天我们就来一场酣畅淋漓的 PK 赛，让它们一较高下！🥊

第一回合：身世揭秘，知己知彼才能百战不殆！

1. 压缩列表（ziplist）：小身材，大能量！💪

想象一下，你有一个小小的储物柜，里面要塞进各种尺寸的物品。为了充分利用空间，你会怎么做？当然是尽量把它们紧凑地排列在一起！压缩列表就是这样的一个“储物柜”。它是一种特殊的、为了节省内存而设计的连续内存块。

特点：
- 紧凑存储： 所有元素都存储在一块连续的内存中，没有额外的指针开销。这就像把所有的东西都打包成一个整体，节省了大量的空间。
- 变长编码： 为了更进一步节省空间，压缩列表会根据元素的大小，采用不同的编码方式。就像给不同大小的衣服穿上不同尺寸的包装袋，杜绝浪费。
- 链式结构： 虽然是连续内存块，但压缩列表内部通过记录每个元素的长度和偏移量，实现了类似于链表的结构。这使得我们可以在列表内部进行遍历和查找。
结构示意图：
```
zlbytes | zltail | zllen | entry1 | entry2 | ... | entryN | zlend
```
- zlbytes: 整个压缩列表占用的字节数。
- zltail: 列表尾节点的偏移量。
- zllen: 列表包含的节点数量。
- entryX: 实际存储的元素节点。
- zlend: 列表结束标识。

2. 跳跃表（skiplist）：高富帅的逆袭！🤴

如果说压缩列表是精打细算的小家碧玉，那么跳跃表就是挥金如土的霸道总裁！它是一种概率型数据结构，通过维护多个层级的链表，实现了快速的查找操作。

特点：
- 多层链表： 跳跃表维护了多个层级的链表，每个层级的节点都是下一层级的子集。这就像一个电梯，可以跳过中间的楼层，直达目标楼层。
- 概率提升： 每个节点都有一定的概率被提升到更高的层级。这使得跳跃表在查找时，可以跳过大量的节点，大大提高查找效率。
- 空间换时间： 跳跃表需要额外的空间来维护多个层级的链表。这就好比为了提高速度，我们需要修建更多更宽的道路。

结构示意图：

+---+---+---+---+---+---+
|Head|-->| 1 |-->| 3 |-->| 7 |-->| NULL|  // 最高层
+---+---+---+---+---+---+
    |       |       |       |
    v       v       v       v
+---+---+---+---+---+---+---+
|Head|-->| 0 |-->| 1 |-->| 3 |-->| 6 |-->| 7 |-->| NULL|  // 中间层
+---+---+---+---+---+---+---+
    |       |       |       |       |       |
    v       v       v       v       v       v
+---+---+---+---+---+---+---+---+---+
|Head|-->| 0 |-->| 1 |-->| 2 |-->| 3 |-->| 4 |-->| 6 |-->| 7 |-->| NULL|  // 最底层
+---+---+---+---+---+---+---+---+---+

Head: 指向跳跃表头节点的指针。
每一层都是一个有序链表。
层级越高，节点越少，查找速度越快。

第二回合：性能大比拼，是骡子是马拉出来溜溜！

既然是 PK 赛，当然要拿出真本事！我们来分别看看这两种编码方式在不同场景下的性能表现。

操作	压缩列表 (`ziplist`)	跳跃表 (`skiplist`)
插入	相对较慢 (O(N))	较快 (O(log N))
删除	相对较慢 (O(N))	较快 (O(log N))
查找	相对较慢 (O(N))	较快 (O(log N))
空间占用	较小	较大
范围查找	较快 (局部性原理)	较快

插入和删除：
- ziplist: 由于需要移动大量的元素，插入和删除操作的复杂度是 O(N)。这就像在拥挤的地铁里插队或者下车，非常费劲！
- skiplist: 通过多层链表的快速定位，插入和删除操作的复杂度是 O(log N)。这就像坐电梯，可以快速到达目标楼层，无需一层一层地爬楼梯。
查找：
- ziplist: 需要遍历整个列表才能找到目标元素，复杂度是 O(N)。这就像在一堆杂物中寻找东西，非常耗时。
- skiplist: 可以通过多层链表进行快速查找，复杂度是 O(log N)。这就像使用搜索引擎，可以快速找到目标信息。
空间占用：
- ziplist: 由于紧凑存储，空间占用非常小。这就像把东西都塞进一个箱子里，节省了大量的空间。
- skiplist: 需要额外的空间来维护多层链表，空间占用相对较大。这就像修建更多更宽的道路，需要占用更多的土地。
范围查找：
- ziplist: 由于数据存储的局部性原理，范围查找的性能较好。这就像从书架上取一本书，相邻的书更容易被找到。
- skiplist: 范围查找的性能也很不错，可以通过跳跃表快速定位到范围的起始位置，然后进行遍历。

第三回合：选择困难症？Redis 来帮你！

看到这里，你可能已经开始纠结了：到底该选谁呢？别担心，Redis 早已为你考虑周全！

Redis 会根据以下两个条件，自动选择使用 ziplist 还是 skiplist：

元素数量： 当有序集合的元素数量较少时，Redis 会选择使用 ziplist。
元素大小： 当有序集合中所有元素的长度都较小时，Redis 也会选择使用 ziplist。

这两个条件由 redis.conf 文件中的以下两个参数控制：

zset-max-ziplist-entries: 指定使用 ziplist 编码的有序集合最多可以包含的元素数量，默认为 128。
zset-max-ziplist-value: 指定使用 ziplist 编码的有序集合中，每个元素的最大长度，默认为 64 字节。

也就是说，当有序集合的元素数量超过 zset-max-ziplist-entries，或者其中某个元素的长度超过 zset-max-ziplist-value 时，Redis 会自动将 ziplist 编码转换为 skiplist 编码。

为什么 Redis 要这么做呢？

因为 ziplist 在元素数量较少、元素长度较小时，可以节省大量的内存空间。但是，当元素数量较多、元素长度较大时，ziplist 的插入、删除和查找操作的性能会急剧下降。此时，使用 skiplist 可以提高性能，牺牲一些空间来换取速度。

第四回合：源码剖析，探秘底层实现！ 🕵️‍♀️

光说不练假把式！为了更深入地理解这两种编码方式，我们来简单地看一下 Redis 的源码。

1. ziplist 相关源码：

ziplist 的相关源码主要集中在 ziplist.c 文件中。

ziplistNew(): 创建一个新的 ziplist。
ziplistInsert(): 向 ziplist 中插入一个元素。
ziplistDelete(): 从 ziplist 中删除一个元素。
ziplistFind(): 在 ziplist 中查找一个元素。

2. skiplist 相关源码：

skiplist 的相关源码主要集中在 t_zset.c 文件中。

zslCreate(): 创建一个新的 skiplist。
zslInsert(): 向 skiplist 中插入一个元素。
zslDelete(): 从 skiplist 中删除一个元素。
zslGetElementByRank(): 根据排名获取 skiplist 中的元素。
zslGetRank(): 获取 skiplist 中指定元素的排名。

由于源码比较复杂，这里就不展开讲解了。感兴趣的同学可以自行阅读 Redis 的源码，相信会有更深刻的理解。

总结：选择适合自己的才是最好的！ 🏆

经过一番激烈的 PK，相信大家对 Redis 有序集合的两种编码方式：ziplist 和 skiplist，有了更深入的了解。

ziplist 适用于元素数量较少、元素长度较小的场景，可以节省大量的内存空间。
skiplist 适用于元素数量较多、元素长度较大的场景，可以提高插入、删除和查找操作的性能。

Redis 会根据实际情况，自动选择使用哪种编码方式。我们作为开发者，只需要了解它们的特点，就可以更好地利用 Redis 来构建高性能的应用。

最后，送给大家一句鸡汤：

没有最好的数据结构，只有最适合的数据结构！选择适合自己的，才能成就更好的自己！ 💪

希望今天的分享对大家有所帮助！感谢大家的收听，我们下次再见！ 👋😊