1、概述

Redis的Sorted Set是一种有序集合，它不仅存储唯一的元素，还为每个元素关联一个分数（score），用于对元素进行排序。为了在保证高效性能的同时节省内存，Redis对Sorted Set 的底层实现进行了多种优化。特别是通过使用跳跃表（skip list）和压缩列表（ziplist）两种不同的数据结构来适应不同场景下的需求。

2、跳跃表（Skip List）

当Sorted Set中的元素数量较多时，Redis使用跳跃表（skip list）来存储和管理元素。跳跃表是一种高效的有序数据结构，能够提供O(log n)的查找、插入和删除操作。与传统的平衡树相比，跳跃表具有更好的并发访问性能，并且更容易实现。

（1）、什么是跳跃表？

跳跃表（skip list）是一种高效的有序数据结构，能够提供O(log n)的查找、插入和删除操作。跳跃表的核心思想是通过多层链表来加速查找过程，每一层链表都包含一部分元素，形成一个稀疏索引。

跳跃表示例如：

为了确保跳跃表的性能和平衡性，Redis在构建跳跃表时遵循了一套严格的逻辑去控制层级以及层级的元素。
如上图所示，第一列为头结点是相互关联的。如果要查找4这个节点。
1、先查最上层的S2链表，查询到5时已经超过4，所以就会沿着5的关联直接向下走到S1层链表的5这个节点。
2、在S1层级链表中会向前查找，找到3这个节点时，发现小于目标4，就会沿着3的关联向下直接走到S0层的3这个节点。
3、然后接着S0的3这个节点，往后查找，找到了4这个节点。
注：
如果在高层找到目标后就会直接返回，如果没有找到就会沿着关联依次往下层去查找，直到找到目标或者查到最后一层没有发现目标为止。

1、跳跃表的层级结构

跳跃表由多个层次的链表组成，每个层次的链表包含一部分元素。
具体来说：
（1）、最底层链表：第0层链表包含所有元素，并且这些元素是按分数（score）有序排列的。
（2）、上层链表：第1 层及以上的链表，只包含部分元素。上层链表中的元素是从下层链表中随机选择的。
（3）、头节点和尾节点：每层链表都有一个头节点（head）和一个尾节点（tail），用于快速访问链表的起始和结束位置。
（4）、指针：每个节点包含多个指针，指向同一层的下一个节点以及下一层的相同元素。通过这些指针，Redis可以在不同层次的链表之间快速导航。

2、层级的选择逻辑

Redis使用了一种概率性的方法来决定每个元素是否进入更高层次的链表。具体来说，Redis 使用了一个随机数生成器 来决定每个元素是否进入上一层链表。

随机数生成器的工作原理：
- 概率分布：对于每个新插入的元素，Redis会生成一个随机数，并根据这个随机数决定该元素是否进入上一层链表。Redis使用的是一个指数分布，即每个元素进入上一层链表的概率为50%。
- 递归决策：如果一个元素被选中进入上一层链表，Redis会继续为该元素生成新的随机数，决定它是否进入更上一层链表。这个过程会递归进行，直到某个随机数不再满足条件，或者达到了最大层数限制。
- 最大层数限制：Redis对跳跃表的最大层数进行了限制，以防止层数过多导致内存浪费。默认情况下，Redis的跳跃表最大层数为32层（可以通过配置参数 skiplist-maxlevel 进行调整）。
实现和结果：
Redis使用了一个简单的随机函数randomLevel()来决定每个元素的层数。
最终结果，第0层链表包含所有元素，第1层链表大约包含一半的元素，第2层链表大约包含四分之一的元素，依此类推。

3、跳跃表的查找过程

跳跃表的查找过程从最高层链表开始，逐层向下查找，直到找到目标元素或确定元素不存在。具体步骤如下：
（1）、从最高层开始：查找操作从跳跃表的最高层链表开始，沿着该层链表向右移动，直到找到第一个大于目标元素的节点。
（2）、逐层向下：当到达最高层链表的末尾或找到第一个大于目标元素的节点时，跳转到下一层链表的相同节点上，再重复上述过程。（注：跳行后，不是从头查询，是接着上一行的节点继续在新行的该节点上开始查询）
（3）、最终定位：当到达第0层链表时，继续移动查找，直到找到目标元素或确定元素不存在。

通过这种多层索引结构，跳跃表能够在O(log n)的时间复杂度内完成查找操作，显著提高了查找效率。

4、跳跃表的插入和删除过程

（1）、插入操作
- 确定层数：当向跳跃表中插入新元素时，Redis会使用randomLevel()函数随机决定该元素的层数。然后，Redis会在每一层链表中为该元素创建相应的节点，并更新指针。
- 维护指针：插入新元素后，Redis会更新相关节点的指针，确保跳跃表的结构仍然保持有序。具体来说，Redis会更新每一层链表中相邻节点的指针，使得新元素能够正确地插入到链表中。

（2）、删除操作
- 逐层删除：当从跳跃表中删除元素时，Redis会从最高层链表开始，逐层向下查找并删除该元素。具体来说，Redis会遍历每一层链表，找到对应的节点并将其从链表中移除。
- 维护指针：删除元素后，Redis会更新相关节点的指针，确保跳跃表的结构仍然保持有序。具体来说，Redis会更新每一层链表中相邻节点的指针，使得删除操作不会破坏链表的连贯性。

5、跳跃表的平衡性

Redis的跳跃表通过概率性的方法来决定每个元素的层数，确保了跳跃表的平衡性。

- 期望高度：在理想情况下，跳跃表的期望高度为O(log n)，其中n是跳跃表中的元素数量。这意味着跳跃表的高度不会无限增长，而是随着元素数量的增加而逐渐增加。
- 期望层数：对于每个元素，进入上一层链表的概率为50%，因此平均每两个元素中只有一个元素会进入上一层链表。这使得跳跃表的每一层的元素数量大致呈指数衰减，确保了跳跃表的平衡性。
- 最坏情况：虽然跳跃表的期望高度为O(log n)，但在极端情况下（例如随机数生成器失效），跳跃表的高度可能会达到O(n)。然而，这种情况发生的概率极低，Redis通过使用高质量的随机数生成器来避免这种情况的发生。

6、跳跃表总结

Redis使用了一种概率性的方法来决定每个元素是否进入更高层次的链表。具体来说，每个元素进入上一层链表的概率为 50%，并且这个过程是递归进行的，直到某个随机数不再满足条件，或者达到了最大层数限制。
通过这种方式，Redis确保了跳跃表的层级结构是动态构建的，并且每一层的元素数量大致呈指数衰减。这不仅保证了跳跃表的平衡性，还使得跳跃表能够在O(log n)的时间复杂度内完成查找、插入和删除操作。

（2）、跳跃表和二叉树的区别

跳跃表（Skip List）和树结构（如平衡二叉搜索树、B+树等）都是用于实现有序集合的数据结构，它们都能提供高效的查找、插入和删除操作。然而，它们在设计、性能特点、内存使用、并发支持等方面存在显著差异。
详细对比：

1、数据结构的设计

（1）、跳跃表：

• 多层链表：跳跃表由多个层次的链表组成，每个层次的链表包含一部分元素，形成一个稀疏索引。最底层链表包含所有元素，上层链表只包含部分元素。
• 指针：每个节点包含多个指针，指向同一层的下一个节点以及下一层的相同元素。通过这些指针，可以在不同层次的链表之间快速导航。
• 随机性：跳跃表的层级是通过概率性方法动态构建的，每个元素进入上一层链表的概率为50%。这使得跳跃表的层级结构是动态的，且每一层的元素数量大致呈指数衰减。

（2）、树结构：

• 节点关系：树结构由节点组成，每个节点包含一个或多个键值对，并且每个节点有指向其子节点的指针。常见的树结构包括平衡二叉搜索树（如AVL树、红黑树）、B+树等。
• 平衡性：为了保证查找、插入和删除操作的时间复杂度为O(log n)，树结构通常需要保持平衡。例如，AVL树通过旋转操作来维持平衡，而B+树通过分裂和合并操作来保持平衡。
• 固定高度：树的高度通常是固定的，取决于元素的数量。例如，一棵包含n个元素的平衡二叉搜索树的高度为 O(log n)。

2、时间复杂度

（1）、跳跃表：

• 查找：O(log n)。跳跃表通过多层链表加速查找过程，查找操作从最高层开始，逐层向下查找，直到找到目标元素或确定元素不存在。
• 插入：O(log n)。插入操作首先进行查找，找到合适的插入位置，然后在每一层链表中为新元素创建相应的节点，并更新指针。
• 删除：O(log n)。删除操作从最高层开始，逐层向下查找并删除目标元素，同时更新相关节点的指针。

（2）、树结构：

• 查找：O(log n)。在平衡二叉搜索树中，查找操作从根节点开始，沿着树的路径向左或向右移动，直到找到目标节点或到达叶子节点。
• 插入：O(log n)。插入操作首先进行查找，找到合适的插入位置，然后将新节点插入到树中，并通过旋转或其他操作保持树的平衡。
• 删除：O(log n)。删除操作首先进行查找，找到目标节点，然后根据节点的子节点情况选择不同的删除策略（如替换、旋转等），并保持树的平衡。

3、内存使用

（1）、跳跃表：

• 指针开销：跳跃表中的每个节点包含多个指针，指向同一层的下一个节点以及下一层的相同元素。虽然跳跃表的指针开销比树结构略大，但通过概率性方法控制层数，避免了过多的指针浪费。
• 内存碎片：跳跃表的节点是动态分配的，可能会导致一定的内存碎片。然而，Redis的跳跃表通过渐进式rehash和惰性释放机制减少了内存碎片的影响。

（2）、树结构：

• 指针开销：树结构中的每个节点通常只需要两个指针（左子节点和右子节点），因此指针开销相对较小。对于B+树等多路树结构，每个节点可能包含多个键值对和多个子节点指针，但总体来说，树结构的指针开销比跳跃表更小。
• 内存碎片：树结构的节点通常是静态分配的，特别是在B+树中，节点的大小是固定的，因此内存碎片问题较少。然而，频繁的插入和删除操作可能会导致树的分裂和合并，增加内存管理的复杂性。

4、并发支持

（1）、跳跃表：

• 并发友好：跳跃表允许多个线程同时访问不同的层次，减少了锁争用。Redis的跳跃表在rehash期间可以同时访问两个跳跃表（旧表和新表），确保了高并发环境下的性能稳定性。
• 渐进式rehash：当跳跃表需要扩容时，Redis使用渐进式rehash来分摊rehash的工作量，避免一次性迁移所有元素导致的长时间阻塞。这使得跳跃表在高并发环境下仍然能够保持良好的性能。

（2）、树结构：

• 并发支持较差：树结构的并发支持相对较差，特别是在平衡二叉搜索树中，插入和删除操作需要频繁地调整树的结构（如旋转、分裂等），这会导致大量的锁争用。虽然有一些并发版本的树结构（如并发哈希映射），但它们的实现复杂度较高，且性能不如跳跃表。
• 锁粒度较大：在树结构中，插入和删除操作通常需要锁定整棵树或部分子树，以确保树的平衡性和一致性。这会导致较高的锁争用，影响并发性能。

5、实现复杂度

（1）、跳跃表：

• 实现简单：跳跃表的实现相对简单，主要涉及链表的操作和随机数生成器的使用。由于跳跃表的层级是动态构建的，不需要复杂的平衡操作，因此实现难度较低。
• 易于调试：跳跃表的结构直观，容易理解和调试。相比于树结构中的旋转、分裂等复杂操作，跳跃表的逻辑更加清晰。

（2）、树结构：

• 实现复杂：树结构的实现相对复杂，特别是平衡二叉搜索树（如 AVL 树、红黑树）需要维护树的平衡性，涉及大量的旋转操作。B+树的实现更加复杂，涉及到节点的分裂、合并等操作。
• 调试困难：树结构的调试难度较大，特别是在处理平衡性问题时，容易出现错误。例如，旋转操作如果实现不当，可能会导致树的不平衡，进而影响性能。

6、应用场景

（1）、跳跃表：

• 高并发场景：跳跃表特别适合高并发场景，因为它允许多个线程同时访问不同的层次，减少了锁争用。Redis的Sorted Set就是基于跳跃表实现的，能够在高并发环境下提供稳定的性能。
• 内存敏感场景：跳跃表的内存使用相对灵活，特别是在Redis中，跳跃表结合压缩列表（ziplist）使用，能够在小规模数据集下节省内存。

（2）、树结构：

• 磁盘存储：B+树广泛应用于数据库和文件系统中，特别是在磁盘存储场景下，B+树的顺序访问性能较好，且能够有效地减少磁盘I/O操作。
• 内存索引：平衡二叉搜索树（如红黑树）常用于内存中的索引结构，特别是在需要频繁插入和删除操作的场景下，平衡二叉搜索树能够提供较好的性能。

7、跳跃表和树对比总结

（3）、跳跃表的特点

-多层索引：跳跃表由多个层次的链表组成，每个层次的链表包含一部分元素。最底层的链表包含所有元素，而上层的链表只包含部分元素，所有层级一起形成了一个稀疏索引。通过这种多层索引结构，跳跃表可以在O(log n)的时间复杂度内完成查找、插入和删除操作。
-有序性：跳跃表中的元素是按分数（score）有序排列的，确保了Sorted Set的语义要求。
-无重复元素：跳跃表保证集合中没有重复元素，符合Sorted Set的语义要求。
-并发友好：跳跃表允许多个线程同时访问不同的层次，减少了锁争用，提高了并发性能。
-动态调整：跳跃表会根据元素的数量和分布情况动态调整层次结构，确保在不同规模的数据集下都能保持高效的性能。

（4）、跳跃表的工作原理

-插入操作：当向跳跃表中插入新元素时，Redis会首先确定该元素应该插入的位置。然后，它会随机决定该元素是否需要添加到更高层次的链表中，以维持跳跃表的稀疏索引结构。插入操作的时间复杂度为O(log n)。
-查找操作：查找操作从最高层次的链表开始，逐层向下查找，直到找到目标元素或确定元素不存在。由于每层链表都是有序的，查找操作可以通过二分查找来加速，时间复杂度为 O(log n)。
-删除操作：删除操作类似于查找操作，先找到目标元素，然后将其从所有层次的链表中移除。删除操作的时间复杂度也为O(log n)。

list_141">3、压缩列表（Ziplist）

当Sorted Set中的元素数量较少时，Redis会使用压缩列表（ziplist）来存储Sorted Set。在Redis6.2版本后是Listpack。压缩列表是一种紧凑的内存表示形式，能够将多个键值对打包到一个连续的内存块中，减少了指针开销和内存碎片。

（1）、压缩列表的特点

-紧凑存储：压缩列表将多个键值对（即元素及其对应的分数）打包到一个连续的内存块中，避免了指针开销。每个键值对的存储空间根据其实际大小动态调整，支持变长编码。
-有序性：压缩列表中的元素是按分数有序排列的，确保了Sorted Set的语义要求。
-无重复元素：压缩列表保证集合中没有重复元素，符合Sorted Set的语义要求。
-内存高效：由于压缩列表是紧凑的数组结构，它减少了内存碎片，并且不需要额外的指针开销。这使得压缩列表在处理小规模数据时具有很高的内存利用率。

（2）、压缩列表的工作原理

-变长编码：压缩列表使用变长编码来存储元素和分数。例如，小整数可以使用较少的字节来表示，而大整数则使用更多的字节。这种变长编码方式减少了不必要的内存浪费。
-前缀压缩：对于相邻的字符串元素，压缩列表会使用前缀压缩技术来减少重复字符串的存储空间。如果两个相邻的字符串有相同的前缀，压缩列表只会存储一次前缀，并在后续的字符串中引用该前缀。
-局部重排：当插入或删除元素时，压缩列表会尽量保持数据的紧凑性，避免频繁的内存分配和释放。它通过局部重排（即将新元素插入到合适的位置，并调整相邻元素的存储位置）来减少内存碎片。

（3）、压缩列表的内存优化

-减少内存碎片：压缩列表通过紧凑的数组结构减少了内存碎片，特别适合处理小规模数据。它避免了传统链表中常见的内存碎片问题，提高了内存利用率。
-缓存友好：由于压缩列表中的元素是连续存储的，访问这些元素时可以充分利用CPU缓存，减少缓存未命中的次数。这有助于提升性能。

4、混合结构，自动转换

Redis的Sorted Set实现了一个智能的混合结构，能够在压缩列表（ziplist）和跳跃表（skip list） 之间自动转换，以适应不同的应用场景。

（1）、自动转换原理

-初始状态：当Sorted Set中的元素数量较少时，Redis 使用压缩列表（ziplist）来存储这些元素。此时，Sorted Set具有最高的内存利用率和操作效率。
-自动升级：当Sorted Set中的元素数量超过某个阈值，或者元素的大小超过一定限制时，Redis 会立即将压缩列表转换为跳跃表。这个转换过程是一次性的，不会影响后续的操作。
-不会反向转换：Redis不会将跳跃表转换回压缩列表，因为一旦Sorted Set的规模较大，跳跃表已经能够高效地处理这些元素。

（2）、自动转换的条件

-元素数量：当Sorted Set中的元素数量超过某个阈值时，Redis会自动将压缩列表转换为跳跃表。这个阈值可以通过配置参数zset-max-ziplist-entries来调整，默认值为128。
-元素大小：即使Sorted Set 中的元素数量较少，但如果某个元素的大小超过一定限制，Redis 也会将压缩列表转换为跳跃表。这个大小限制可以通过配置参数zset-max-ziplist-value来调整，默认值为64字节。

5、内存优化的其他技术

除了压缩列表和跳跃表的结合使用，Redis还采用了其他一些内存优化技术来进一步提升Sorted Set的性能和内存利用率：

-渐进式rehash：当跳跃表需要扩容时，Redis会使用渐进式rehash来分摊rehash的工作量，避免一次性迁移所有元素导致的性能下降。这确保了在高并发环境下，Sorted Set的操作性能仍然保持稳定。
-惰性释放：当Sorted Set中的元素被删除时，Redis不会立即回收多余的内存，而是保留下来用于后续可能的增长。这减少了频繁的内存分配和释放操作，提升了性能。
-前缀压缩：对于相邻的字符串元素，Redis使用前缀压缩技术来减少重复字符串的存储空间。这在处理大量相似的字符串时特别有效，能够显著节省内存。
-变长编码：Redis使用变长编码来存储整数和浮点数，减少了不必要的内存浪费。例如，小整数可以使用较少的字节来表示，而大整数则使用更多的字节。

6、总结

Redis的Sorted Set通过结合压缩列表（ziplist）和跳跃表（skip list）两种不同的数据结构，实现了高效的内存优化。当Sorted Set中的元素数量较少且较短时，Redis使用压缩列表来存储这些元素。当Sorted Set 中的元素数量较多时，Redis使用跳跃表来存储Sorted Set。当Sorted Set中的元素数量超过某个阈值，或者元素的大小超过一定限制时，压缩列表会自动转换为跳跃表。但是升级后是不可逆的。

学海无涯苦作舟！！！