Sorted Set是什么，其底层是如何实现的

Redis的Sorted Set（有序集合），通常也称为ZSet，是Redis中一种非常重要且功能强大的数据类型。它与普通的Set（集合）类似，都存储不重复的字符串元素（成员，member），但其核心区别在于，Sorted Set中的每个成员都会关联一个double类型的浮点数分数（score）。Redis正是通过这个分数来为集合中的成员进行排序的。

Sorted Set的主要特性：

  1. 有序性：

    • 集合中的成员是根据其关联的分数进行升序排列的。这意味着你可以很方便地获取到按分数排序的成员列表。
    • 如果多个成员拥有相同的分数，则它们会按照字典序（lexicographical order）进行排序（具体是字节序比较）。

  2. 唯一性：

    • 与普通Set一样，Sorted Set中的成员（member）是唯一的，不允许重复。如果尝试添加一个已存在的成员，但分数不同，则会更新该成员的分数，并重新调整其在集合中的位置。

  3. 成员与分数的关联：

    • 每个成员都唯一对应一个分数。这个分数使得Sorted Set不仅仅是一个简单的有序列表，更像是一个“排名表”或“带权重的集合”。

底层实现：

Redis Sorted Set的底层实现是一个非常精巧的设计，它会根据存储元素的数量和大小动态选择不同的编码方式，以在时间和空间效率上达到平衡。主要有两种编码方式：

  1. 压缩列表（Ziplist）：

    • 当Sorted Set中包含的元素数量较少，并且每个元素（成员和分数）本身也较小（例如，成员是短字符串，分数是可以用整数表示的小浮点数）时，Redis会采用压缩列表（ziplist）作为其底层实现。
    • 在ziplist中，每个Sorted Set的元素（成员和分数对）会作为一个entry紧凑地存储。为了保持有序，插入新元素时，会找到合适的位置插入，这可能涉及移动后续元素。
    • 成员和分数是连续存储的，通常是成员在前，分数在后。
    • 优点：内存占用极小，非常节省空间。
    • 缺点：当元素数量增多或单个元素变大时，插入和删除操作的性能会下降，因为可能需要移动大量数据或触发连锁更新。查找操作也需要遍历。

  2. 跳跃表（Skip List）和字典（Dictionary/Hash Table）的组合：

    • 当Sorted Set中的元素数量超过一定阈值（由zset-max-ziplist-entries配置，默认为128），或者任何一个成员的长度超过一定阈值（由zset-max-ziplist-value配置，默认为64字节）时，Redis会自动将底层编码从ziplist转换为跳跃表和字典的组合。

    • 这种组合结构是Sorted Set更通用的、性能更优的实现方式：

      • 跳跃表（Skip List）：
        • 作用：用于按照分数对成员进行排序和范围查找。
        • 结构：跳跃表是一种有序的、多层链表结构。每个节点存储了成员（member）和其对应的分数（score）。节点之间通过多级指针连接，使得查找、插入、删除的平均时间复杂度可以达到O(log N)。跳跃表中的节点是按分数排序的，分数相同则按成员的字典序排序。
        • 每个跳跃表节点（zskiplistNode）包含：
          • 成员（ele）：一个指向实际成员字符串（SDS）的指针。
          • 分数（score）：double类型。
          • 后退指针（backward）：指向前一个节点的指针，用于从表尾向前遍历。
          • 层级数组（level[]）：包含多个层级，每个层级（zskiplistLevel）包含：
            • 前进指针（forward）：指向同一层级的下一个节点。
            • 跨度（span）：表示该前进指针跨越了多少个节点。用于快速计算排名。
      • 字典（Dictionary/Hash Table）：
        • 作用：用于以O(1)的平均时间复杂度快速查找指定成员的分数。
        • 结构：字典的键是成员（member，SDS类型），值是该成员的分数（score，double类型）。
        • 这样，当需要更新某个成员的分数，或者查询某个成员的分数时，可以通过字典快速定位，而不需要遍历跳跃表。

    • 两者如何协同工作：

      • 跳跃表和字典共享成员的字符串对象（SDS），以节省内存。即，跳跃表节点中的成员指针和字典键中的成员指针指向同一个SDS对象。
      • 当对Sorted Set进行操作时（如ZADD, ZREM, ZSCORE等），Redis会同时更新跳跃表和字典，以保持两者数据的一致性。
      • 例如，执行ZADD添加一个新成员时：
        1. 先在字典中查找该成员是否存在。
        2. 如果不存在或分数需要更新，则在字典中添加/更新该成员及其分数。
        3. 同时，在跳跃表中插入/更新包含该成员和分数的新节点（如果分数变化，可能需要先删除旧节点再插入新节点以维持顺序）。
      • 通过这种组合，Sorted Set既能高效地进行按成员查找（通过字典），也能高效地进行按分数排序、范围查找和排名查询（通过跳跃表）。

总结底层实现的关键点： * Redis Sorted Set采用动态编码，会根据元素数量和大小选择使用ziplist或跳跃表+字典的组合。 * Ziplist编码：适用于小数据量、小元素的场景，极致节省内存。 * 跳跃表+字典编码：适用于大数据量或大元素的场景，提供了优秀的综合性能。 * 字典保证了按成员名查找分数的O(1)效率。 * 跳跃表保证了按分数排序以及范围查询、排名查询的O(log N)效率。 * 两者共享成员数据以节约内存。