Redis数据库笔记——ZSet的底层实现（跳表）

大家好，这里是Good Note，关注 公主号：Goodnote，专栏文章私信限时Free。本文详细介绍ZSet数据类型中跳表的底层实现，包括基本特点和常用操作。

文章目录

• • ZSet（有序集合）
  • • 概述
    • 基本特点
    • 底层实现
  • Skiplist跳表
  • • 概述
    • 结构
    • 跳表的基本操作
    • • 1. 查找操作：`Search`
      • 2. 插入操作：`Insert`
      • 3. 删除操作：`Delete`
      • 4. 排名计算：`ZRank`
  • 历史文章
  • • MySQL数据库
    • Redis

ZSet（有序集合）

概述

ZSet（Sorted Set，有序集合） 是 Redis 提供的一个非常强大的数据结构。它是一个 没有重复成员 且每个成员都关联着一个 分数（score） 的集合，Redis 会根据成员的分数对它们进行 自动排序。这个数据结构在许多需要有序数据的场景中非常有用，如排行榜、带有优先级的任务队列等。

ZSet 提供了非常高效的操作支持，如按排名查询、按分数查询、获取范围内的元素等，且在执行这些操作时有着较低的时间复杂度。

基本特点

• 成员唯一性：ZSet 中的每个元素都是唯一的（没有重复的成员）。
• 分数（score）：每个成员都有一个与之关联的分数，分数通常是浮动的数值，用于排序。Redis 会根据分数值对成员进行升序排序。
• 有序性：ZSet 内部元素会根据分数（score）进行自动排序，成员可以通过分数排名进行快速查找。
• 按分数查询：可以根据成员的分数进行范围查询（例如，获取某个分数范围内的成员），也可以获取某个成员的排名。

底层实现

Redis 的 ZSet 在实现上确实有根据数据量和元素大小的不同，采用不同的内存优化方式。具体来说：

1. 使用 ziplist（压缩链表）：

   • 元素数量小于 128：当 ZSet 中的元素数量较少时，使用 ziplist 来优化内存。因为 ziplist 对小规模数据结构的存储是高效的，尤其是在内存有限的情况下。
   • 每个元素的长度小于 64 字节：如果 ZSet 中的元素比较小（成员和分数的长度合计小于 64 字节），ziplist 的压缩效果会比较好，从而进一步节省内存空间。

   在 ziplist 中，成员和分数（score）是交替存储的，并且以压缩的方式存储，减少了内存的开销。

2. 使用 skiplist（跳跃链表）和 hash table（哈希表）：

   • 当 ZSet 中的元素数量超过 128 个，或者 元素的长度超过 64 字节，Redis 会自动转而使用 跳跃链表（skiplist）和哈希表（hash table） 的组合来实现 ZSet。这是默认的实现方式，主要是因为跳跃链表和哈希表的组合在查找、范围查询、排序等操作上具有更好的性能。

   • 跳跃链表（Skiplist）：

     • 用于维护 ZSet 中元素的有序性。跳跃链表是一种多层次链表，每一层都是一个有序的链表，层数根据概率进行分配。跳跃链表的查询、插入、删除操作时间复杂度为 O(log N)。
     • 跳跃链表提供了非常高效的范围查询（按分数范围查询、按排名查询等）支持，因此非常适合用于 ZSet。

   • 哈希表（Hash Table）：

     • 用于存储每个元素的 成员 → 分数 映射，使得可以通过 O(1) 时间复杂度快速查找一个成员的分数。
     • 哈希表提供快速查找、插入和删除操作。

Skiplist跳表

跳表（Skiplist）是一种概率型的数据结构，旨在提供与平衡二叉树类似的查找性能（O(log N)），但其实现相对更简单且更易于理解。跳表通过多层链表的方式，使用概率来决定每个元素出现在哪些层，从而加速查询、插入和删除操作。

Redis选择跳跃表而非红黑树作为有序集合实现方式的原因并非是基于并发上的考虑，因为redis是单线程的，选用跳跃表的原因仅仅是因为跳跃表的实现相较于红黑树更加简洁。

概述

跳表的核心思想是通过多级索引（层级链表）来加速元素的查找。每一层都是一个有序链表，跳表通过多层次的链表来进行索引，从而大大降低了查找时需要遍历的节点数量。

• 第0层：包含了所有的元素，是最基础的有序链表。
• 第1层：每隔一定数量的元素出现一个节点，可以认为是对第0层链表的索引。
• 第2层、第三层…：随着层数的增加，每一层的节点数量逐渐减少。

跳表的查找是通过从顶部层开始，每层尝试跳跃多个元素，直到找到目标元素或到达链表的末尾。插入和删除操作也利用类似的跳跃方式来维持跳表的有序性和层级结构。

结构

上图用a,b,c,d,e五种有序链表说明了跳跃表的过程。

• [a]单链表：查询时间复杂度O(n)
• [b]level-2单链表：每隔一个节点为一个level-2节点，每个level-2节点有2个后继指针，分别指向单链表中的下一个节点和下一个level-2节点。查询时间复杂度为O(n/2)
• [c]level-3单链表：每隔一个节点为一个level-2节点，每隔4个节点为一个level-3节点，查询时间复杂度O(n/4)
• [d]指数式单链表：每隔一个节点为一个level-2节点，每隔4个节点为一个level-3节点，每隔8个节点为一个level-4节点（每2^i个节点的level为i+1），查询时间复杂度为O(log2N)
• [e]跳跃表：各个level的节点个数同指数式单链表，但出现的位置随机，查询复杂度是O(logN)

跳跃表和指数式单链表的最大区别在于，跳跃表中各层节点的分布是 随机的，而不是按照固定的规律排列。这种随机性使得跳跃表非常灵活，且能够有效平衡性能。

• 查询操作：查询时，跳跃表根据层级结构，通过随机选择的高层节点来加速查找过程。虽然节点的分布是随机的，但由于层数与节点数的关系仍然保持对数增长，查询的时间复杂度保持为 O(log N)，这保证了跳跃表在查找操作上的高效性。

跳表的基本操作

1. 查找操作：Search

跳表的查找过程从 最高层 开始，尝试在当前层向右移动，直到找到目标元素或超出当前层。如果当前层不能继续向右移动，跳表会向下一层跳跃，继续查找。每一层都是有序的，因此可以通过跳跃来加速查找过程。

时间复杂度：O(log N)，因为每一层大约有一半的节点，跳跃过程中需要的查找次数会减少，类似于二分查找。

2. 插入操作：Insert

跳表的插入过程与查找类似。首先，查找目标位置，然后将新节点插入到该位置。如果需要提升节点到更高层级，插入操作会按概率决定是否在上一层创建一个新节点。具体步骤如下：

• 查找：首先，Redis 会根据 value 在 map 中查找对应的元素是否已经存在。如果存在，Redis 会删除旧的元素，并在跳跃表中找到对应节点删除。
• 插入：接下来，跳跃表的插入过程也使用 score 作为查询位置的依据。首先，跳跃表会通过 跳跃表查找 来找到要插入的位置。
  • 如果 score 相同，Redis 会按照成员对象的 value 进行二次排序。
  • 每次插入时，Redis 会更新跳跃表节点的层数，并且还要更新对应的 map 中的 value -> score 映射关系。
  • 随机决定是否在上一层插入该元素。如果需要，在上一层创建一个新节点，指向当前插入的节点。

时间复杂度：O(log N)，但是插入操作的时间复杂度可能随着随机升高层数的增加而变动，通常在常数倍数内。

3. 删除操作：Delete

删除操作与插入操作类似，首先查找目标节点的位置，并删除该节点。然后，需要在每一层中更新相应的指针，确保跳表的结构保持有序。

时间复杂度：O(log N)，删除操作与查找操作的复杂度相同。

4. 排名计算：ZRank

排名计算依赖跳跃表中的节点信息，特别是 Next 指针的 span。

• span 是指某个跳跃表节点能跨越的元素个数。例如，在查找排名时，跳跃表的查询路径中的每个节点都会携带一个 span 值，表示该节点能跳过多少元素。
• 当进行排名计算时，Redis 会将经过的每个节点的 span 值加起来，从而得到元素的 rank（排名）。

历史文章

MySQL数据库

1. MySQL数据库笔记——数据库三范式
2. MySQL数据库笔记——存储引擎（InnoDB、MyISAM、MEMORY、ARCHIVE）
3. MySQL数据库笔记——常见的几种锁分类
4. MySQL数据库笔记——索引介绍
5. MySQL数据库笔记——事务介绍
6. MySQL数据库笔记——索引结构之B+树
7. MySQL数据库笔记——索引潜规则（回表查询、索引覆盖、索引下推）
8. MySQL数据库笔记——索引潜规则（最左前缀原则）
9. MySQL数据库笔记——常见慢查询优化方式
10. MySQL数据库笔记——日志介绍
11. MySQL数据库笔记——多版本并发控制MVCC
12. MySQL数据库笔记——主从复制

Redis

1. Redis数据库笔记——数据结构类型
2. Redis数据库——Redis雪崩、穿透、击穿
3. Redis数据库——内存淘汰机制
4. Redis数据库笔记——内存分配器
5. Redis数据库笔记——内存预分配
6. Redis数据库笔记—— Hash（哈希）的扩容机制(rehash)