【高阶篇】3.7 Redis之底层数据结构跳表(SkipList)_redis底层跳表

0.前言

上个篇章回顾，我们上个章节我们学习了《Redis从入门到精通【高阶篇】之底层数据结构整数集(IntSet)详解》，我们从源码层了解整数集由一个头部和多个数据块组成。头部中存储了整数集的元素个数、编码方式和数据块的起始地址等信息。数据块中存储了实际的整型数据，当一个集合只包含整数值元素，并且这个集合的元素数量不多时，Redis 就会使用整数集合作为集合键的底层实现。IntSet的设计目标是尽可能地节省内存空间，同时保证高效的操作性能。它可以存储三种类型的整数：8位整数、16位整数和32位整数。。

本章节，我们详细了解一下在Redis又一个底层数据结构跳表(SkipList)，它是一种基于链表的数据结构，用于快速地插入、删除和查找元素。跳表通过多层级的指针数组来实现快速的操作，时间复杂度为O(log n)，其中n为跳表中元素的个数。Redis中的有序集合（Sorted Set 也叫ZSet 它们讲的是同一个）就是通过跳表来实现的。。

1.跳表(SkipList)基本详解

跳表中的每个节点包含一个键值对，其中键用于排序元素，值用于存储具体的数据。跳表的每个节点都有多个指针，用于指向下一个节点。多个指针可以穿过一些节点，形成多层级的结构，从而实现快速的操作。

Redis中的有序集合（Sorted Set）使用的底层数据结构之一就是跳表（Skip List）。跳表是一种基于链表的数据结构，它通过添加多级索引来加速查找操作，从而在某些场景下可以提供比普通链表更高效的查找性能。

Redis 中zset利用跳表底层数据结构可以实现如下几个场景，这些场景可能你在其他的文章中也会提到，但是本次我们要深入的通过源码层进行解析。

• 排行榜：跳表可以很好地支持排行榜功能，例如在游戏中记录玩家的积分排名。由于跳表在插入、删除和查找操作上的平均时间复杂度为O(log n)，因此可以快速地进行排名的更新和查询。
• 范围查询：跳表可以用于支持范围查询，例如在社交网络中按照用户的年龄范围或者地理位置范围来查找用户。跳表通过多级索引可以快速定位到指定范围的节点，从而高效地进行范围查询。
• 实时统计：跳表可以用于实时统计数据的功能，例如统计某个时间段内的用户活跃数、订单数量等。通过跳表的插入操作，可以将数据按照时间顺序有序地存储在跳表中，并且通过多级索引可以快速定位到指定时间段的数据，从而实现实时统计的需求。

需要注意的是，跳表并不适用于所有场景，它的优势在于某些特定的读取操作，而在写入操作上相对较慢。因此，在选择使用跳表时需要根据具体的业务场景和需求来进行权衡和选择。

2. 源码解析

说了在多理论的概念和举例都略显单薄，很多同学可能在想"talk is cheap, show me code"。那么接下来我们进行一下源码解读。
在Redis的GitHub仓库中，IntSet的代码文件位于以下路径：
server.h：https://github.com/redis/redis/blob/6.0/src/server.h
t_zset.c：https://github.com/redis/redis/blob/6.0/src/t_zset.c#L90
6.0分支是Redis6的分支，包含了最新的代码修改和功能更新。所以如果有同学想详细的了解一下，也可以在该分支下找到最新的ZSkipList代码文件，如果对Redis7的源码也想了解，只需要在上面切换一下分支即可。参考代码实现来深入了解ZSkipList的数据结构和操作还是相比上节事有点复杂的。
记住这块代码的定义，我们后面的代码分析过程中会用到

注：如果你对C也算是了解的话，可能下面的内容就不必再看了，点击我上面的源码地址，扫一遍这两个文件基本上就一目了然。
如果你是C小白，请继续。
上面截图中

server.h：细心的同学会发现，这次的源码文件为什么不是zset.h 和zeset.c了。其实这是因为在server.h文件中定义zskiplistNode结构体，是因为跳表节点它是跳表的基本组成部分，它包含了跳表中的元素值、分值等属性。作者将跳表节点的定义放在server.h文件中，可以使得其他源码文件（如src/t_zset.c）能够直接引用和操作跳表节点，方便对跳表进行插入、删除、查找等操作。

t_zset.c：t_zset.c是Redis中有序集合功能的源码文件，它包含了有序集合的各种操作的实现，如创建有序集合、插入元素、删除元素、修改元素、查询元素等。。

从上面的源码截图我们可以看出来IntSet的定义如下：

// 表示跳表中的节点的结构体
typedef struct zskiplistNode {
// 节点存储的元素值（=Redis SDS 这也是Redis的字符串的底层数据结构，简单动态字符串，如果不了解，可以看我的历史的讲解内容）
    sds ele; 
    double score; // 与元素关联的分值
    struct zskiplistNode *backward; // 指向前一个节点的指针
    struct zskiplistLevel {
        struct zskiplistNode *forward; // 指向下一个节点的指针
        unsigned long span; // 到下一个节点的跨度
    } level[]; // 灵活数组，表示节点的层级
} zskiplistNode;

// 表示整个跳表的结构体
typedef struct zskiplist {
    struct zskiplistNode *header; // 指向跳表的头节点
    struct zskiplistNode *tail; // 指向跳表的尾节点
    unsigned long length; // 跳表中节点的数量
    int level; // 跳表的最大层级
} zskiplist;

// 表示有序集合的结构体
typedef struct zset {
    dict *dict; // 使用字典实现的有序集合
    zskiplist *zsl; // 使用跳表实现的有序集合
} zset;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

3.总结

在实际的Redis应用中，整数集被广泛应用于集合等数据结构的实现。通过使用整数集，Redis可以在保证高效的操作性能的同时，减少内存的浪费，提高内存利用率。可以用于存储大量的整数值，并支持快速的插入、删除和查找操作。如果您需要存储大量的整数值，可以考虑使用IntSet来优化存储空间和操作性能。

4.思考题

应一位网友的建议，在每个章节后面留个思考题，供大家继续学习。下次分享来揭晓答案。本次的思考题只有一道。
1. Redis6是如何使用IntSet来实现集合和有序集合？

5. Redis从入门到精通系列文章

《Redis从入门到精通【高阶篇】之底层数据结构字典(Dictionary)详解》
《Redis从入门到精通【高阶篇】之底层数据结构快表QuickList详解》
《Redis从入门到精通【高阶篇】之底层数据结构简单动态字符串(SDS)详解》
《Redis从入门到精通【高阶篇】之底层数据结构压缩列表(ZipList)详解》
《Redis从入门到精通【进阶篇】之数据类型Stream详解和使用示例》

大家好，我是冰点，今天的Redis从入门到精通【高阶篇】之底层数据结构整数集(IntSet)详解，全部内容就是这些。如果你有疑问或见解可以在评论区留言。