Redis 底层 ZSet 实现压缩列表和跳表如何选择

有的时候博客内容会有变动，首发博客是最新的，其他博客地址可能会未同步, 认准 https://blog.zysicyj.top

全网最细面试题手册，支持艾宾浩斯记忆法。这是一份最全面、最详细、最高质量的 java 面试题，不建议你死记硬背，只要每天复习一遍，有个大概印象就行了。https://store.amazingmemo.com/chapterDetail/1685324709017001`

Redis 底层 ZSet 实现：压缩列表和跳表选择机制

Redis 的有序集合（ZSet）是一种复合数据结构，它主要由两种数据结构实现： 压缩列表 （ziplist）和 跳表（skiplist）。这两种数据结构的选择取决于有序集合中元素的数量和元素的大小。

压缩列表（Ziplist）

压缩列表是一种为了节省空间而设计的紧凑的顺序数据结构。它将所有元素紧密地排列在一起，没有任何间隙。压缩列表适用于存储小的字符串列表，尤其是当列表中的元素个数较少，且每个元素的大小也较小的时候。

优点:

  • 空间效率高：由于紧凑的存储方式，压缩列表可以节省大量的内存空间。
  • 适合小数据集：对于小数据集的操作，压缩列表的性能通常很好。

缺点:

  • 性能问题：随着元素数量的增加，插入和删除操作的性能会下降，因为这些操作可能需要重新分配内存和移动大量的数据。

跳表（Skiplist）

跳表是一种概率平衡的数据结构，它允许快速的搜索、插入、删除和有序遍历操作。跳表通过多层的链表来实现，每一层都是下一层的一个子集，顶层的链表包含所有元素。

优点:

  • 快速操作：跳表提供了对数级别的时间复杂度（O(logN)）来进行搜索、插入和删除操作。
  • 动态扩展：跳表可以在不重新分配整个数据结构的情况下动态地添加更多的层级。

缺点:

  • 空间消耗：由于需要存储额外的指针，跳表通常会消耗比压缩列表更多的内存。

选择机制

Redis 在选择使用压缩列表还是跳表时，会根据以下两个配置参数来决定：

  1. zset-max-ziplist-entries：这个参数指定了 ZSet 中元素的最大数量，超过这个数量，ZSet 将从压缩列表转换为跳表。
  2. zset-max-ziplist-value：这个参数指定了 ZSet 中元素值的最大长度，超过这个长度，ZSet 将从压缩列表转换为跳表。

当 ZSet 中的元素数量和元素值的大小都没有超过上述两个参数的限制时，Redis 会使用压缩列表来存储 ZSet。一旦任一条件被违反，Redis 就会将数据结构从压缩列表转换为跳表。

示例:

1
2
3
4
5
6
7
8
9
# 假设配置如下：
zset-max-ziplist-entries 128
zset-max-ziplist-value 64

# 当 ZSet 满足以下条件时，将使用压缩列表：
- 元素数量 <= 128
- 每个元素的值的长度 <= 64 字节

# 一旦 ZSet 超出以上任一条件，将使用跳表。

总结来说，Redis 通过这种灵活的数据结构选择机制，能够在保证性能的同时，尽可能地节省内存空间。开发者可以根据实际应用场景的数据特点，调整这两个参数，以优化 Redis 的性能和内存使用。