Redis 底层 ZSet 跳表是如何设计与实现的

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

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

Redis 底层 ZSet 跳表设计与实现

Redis 中的有序集合（ZSet）是一种复合数据结构，它结合了哈希表和跳表（Skip List）来保证数据的有序性和高效的访问性能。在这里，我们将重点讨论跳表的设计与实现，它是 ZSet 实现中的关键部分。

跳表（Skip List）简介

跳表是一种概率性数据结构，它通过在多个层上添加前进指针来提高链表的查找效率。跳表的效率可以与平衡树相媲美，即在平均情况下，跳表的查找、插入和删除操作的时间复杂度都是 O(log n)。

跳表的结构

跳表由多层链表组成，每一层都是一个有序的链表。最底层（Level 0）包含所有的元素。每一层都是下一层的一个 “ 子集 “，其中包含的元素通过一个随机过程选取。一个元素在跳表中的层数是通过一个随机化过程决定的，通常是通过抛硬币的方式来决定是否提升层级。

基本元素：

  • 节点（Node）：每个节点包含了数据和多个指向其他节点的指针（每一层一个）。
  • 头节点（Header）：跳表的开始节点，它的指针指向各层的第一个实际节点。
  • 尾节点（NIL）：标记跳表的结束，所有层的最后一个节点都指向 NIL。

Redis 中跳表的实现

在 Redis 中，跳表的实现是通过以下几个关键的结构体来定义的：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
typedef struct zskiplistNode {
    sds ele; // 元素值
    double score; // 分数，用于排序
    struct zskiplistNode *backward; // 后退指针
    struct zskiplistLevel {
        struct zskiplistNode *forward; // 前进指针
        unsigned int span; // 跨度
    } level[];
} zskiplistNode;

typedef struct zskiplist {
    struct zskiplistNode *header, *tail; // 头尾节点
    unsigned long length; // 节点数量
    int level; // 层数
} zskiplist;

关键点：

  • ele：存储元素的值，Redis 中通常是字符串。
  • score：元素的分数，用于在有序集合中进行排序。
  • backward：指向前一个节点，用于从尾部向头部遍历。
  • level：一个动态大小的数组，包含前进指针和跨度。跨度表示当前节点到下一个节点的间隔。
  • header：指向跳表的头节点。
  • tail：指向跳表的尾节点。
  • length：表示跳表的长度，即节点的数量。
  • level：表示跳表的当前层数。

跳表的操作

插入操作

插入操作首先需要确定新节点的层数，然后从最高层开始搜索，直到找到每一层的插入位置。在找到插入位置后，需要调整指针并更新跨度。

删除操作

删除操作需要找到要删除的节点，并在每一层中删除它，同时更新指针和跨度。

查找操作

查找操作从最高层开始，逐层向下搜索，直到找到目标节点或确定目标不存在。

总结

Redis 中的跳表是 ZSet 实现的核心，它通过多层链表结构实现了高效的插入、删除和查找操作。跳表的随机化层级和前进指针使得它在维护有序元素集合时，能够提供与平衡树相似的性能，同时保持了链表的灵活性。