【专栏简介】

随着数据需求的迅猛增长，持久化和数据查询技术的重要性日益凸显。关系型数据库已不再是唯一选择，数据的处理方式正变得日益多样化。在众多新兴的解决方案与工具中，Redis 凭借其独特的优势脱颖而出。

【技术大纲】

为何 Redis 备受瞩目？原因在于其学习曲线平缓，短时间内便能对 Redis 有初步了解。同时，Redis 在处理特定问题时展现出卓越的通用性，专注于其擅长的领域。深入了解 Redis 后，您将能够明确哪些任务适合由 Redis 承担，哪些则不适宜。这一经验对开发人员来说是一笔宝贵的财富。

在这个专栏中，我们将专注于 Redis 的 6.2 版本进行深入分析和介绍。Redis 6.2 不仅是我个人特别偏爱的一个版本，而且在实际应用中也被广泛认为是稳定性和性能表现都相当出色的版本。

【专栏目标】

本专栏深入浅出地传授 Redis 的基础知识，旨在助力读者掌握其核心概念与技能。深入剖析了 Redis 的大多数功能以及全部多机功能的实现原理，详细展示了这些功能的核心数据结构和关键算法思想。读者将能够快速且有效地理解 Redis 的内部构造和运作机制，这些知识将助力读者更好地运用 Redis，提升其使用效率。

将聚焦于 Redis 的五大数据结构，深入剖析各种数据建模方法，并分享关键的管理细节与调试技巧。

【目标人群】

Redis 技术进阶之路专栏：目标人群与受众对象，对于希望深入了解 Redis 实现原理底层细节的人群。

1. Redis 爱好者与社区成员

Redis 技术有浓厚兴趣，经常参与社区讨论，希望深入研究 Redis 内部机制、性能优化和扩展性的读者。

2. 后端开发和系统架构师

在日常工作中经常使用 Redis 作为数据存储和缓存工具，他们在项目中需要利用 Redis 进行数据存储、缓存、消息队列等操作时，此专栏将为他们提供有力的技术支撑。

3. 计算机专业的本科生及研究生

对于学习计算机科学、软件工程、数据分析等相关专业的在校学生，以及对 Redis 技术感兴趣的教育工作者，此专栏可以作为他们的学习资料和教学参考。

无论是初学者还是资深专家，无论是从业者还是学生，只要对 Redis 技术感兴趣并希望深入了解其原理和实践，都是此专栏的目标人群和受众对象。

让我们携手踏上学习 Redis 的旅程，探索其无尽的可能性！

跳跃表

跳表（Skiplist）是一种特殊的有序数据结构，其设计精髓在于通过在各个节点中存储多个指向其他节点的指针，从而实现了高效的节点访问机制，数据结构的逻辑模型如下图所示：

刚才，我为大家展示了通过（1->2->3->4）的步骤，详细地勾勒出寻找特定元素的整个流程。此外，这种数据结构还具备强大的数据处理能力，可以轻易地返回特定范围内的数据信息。它的精妙之处在于巧妙地平衡了查询速度与内存开销之间的关系，从而在实际应用中展现出了出色的性能。

跳跃表的性能

在平均情况下，该数据结构能以 O(log W)的复杂度迅速找到目标节点，即便在最不利的情况下，其查找复杂度也仅为 O(W)，这足以证明其高效性与稳定性。

在多数场景中，跳跃表的表现足以与平衡树相媲美，甚至在效率上不相上下。更值得一提的是，相较于平衡树的复杂实现，跳跃表的实现更为简洁明了，这使得许多程序选择采用跳跃表作为平衡树的替代方案。

Redis 的有序集合

Redis 选择跳跃表作为其有序集合（Sorted Set /ZSet）的底层实现方式之一，有序集合继承了集合的基本特性，同时增加了对元素权重的支持，并可以根据这些权重对元素进行排序。

权重和范围数据检索

• 【范围检索】：ZRANGEBYSCORE 命令能够根据元素权重返回指定范围内的元素，这为我们提供了一种高效的数据检索方式。

// 获取5-15范围内的数据集合ZRANGE dataSet 5 15 WITHSCORES

• 【排序权重】：ZSCORE 命令则可以返回某个特定元素的权重值，让我们能够轻松地获取元素的权重信息。

// 查询dataSet中的element数据的权重值ZSCORE dataSet element

这些特性使得有序集合在实际应用中具有广泛的用途，比如实现排行榜、成绩单等功能。

具体来说，当有序集合中包含的元素数量较多，或者有序集合中的元素成员为较长的字符串时，Redis 会倾向于采用跳跃表作为底层数据结构，这是因为跳跃表在处理大量数据或复杂数据时，能够展现出优秀的查询和访问性能，从而确保 Redis 在这些场景下依然能够保持高效和稳定的工作状态。

Redis 有序集合 — 跳跃表的实现

Redis 的跳跃表在源码中：server.h/zskiplistNode和server.h/zskiplist两个结构进行定义，其中zskiplistNode结构专门用来表征跳跃表中的节点，而zskiplist结构则用于存储关于跳跃表节点的相关元数据，如节点的总数、指向表头节点和表尾节点的指针等。

在 server.h 文件中基本定义的源码如下：

/* ZSETs use a specialized version of Skiplists */typedef struct zskiplistNode {    sds ele;    double score;    struct zskiplistNode *backward;    struct zskiplistLevel {        struct zskiplistNode *forward;        unsigned long span;    } level[];} zskiplistNode;
typedef struct zskiplist {    struct zskiplistNode *header, *tail;    unsigned long length;    int level;} zskiplist;
typedef struct zset {    dict *dict;    zskiplist *zsl;} zset;

• 对应的源码地址：https://github.com/redis/redis/blob/unstable/src/server.h

这种设计使得跳跃表在 Redis 内部得以高效且有序地管理数据，为有序集合和集群节点等功能的实现提供了坚实的基础。

zskiplistNode

在上面的 zskiplist 结构的展示了 6 个 zskiplistNode 结构的实例，下面便是对应的源码定义：

/* ZSETs use a specialized version of Skiplists */typedef struct zskiplistNode {    // sorted set 中的元素    sds ele;    // 元素权重    double score;    // 后向指针（为了便于从跳表的尾节点倒序查找）    struct zskiplistNode *backward;    // 节点的 level 数组    struct zskiplistLevel {        // 每层上的前向指针        struct zskiplistNode *forward;        // 跨度，记录节点在某一层 *forward 指针和该节点，跨越了 level0 上的几个节点        unsigned long span;    } level[];} zskiplistNode;

每个节点都具备以下关键属性：

• 层级（Level）：节点中的 L1、L2、L3 等标记代表了节点的不同层级，其中 L1 代表第一层，L2 代表第二层，依此类推。

每一层都包含两个核心属性：前进指针和跨度（span）。

在图中，前进指针用于指向表尾方向的下一个节点，而跨度则记录了当前节点与前进指针所指节点之间的元素数量。

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

当程序需要从表头遍历至表尾时，会沿着各层的前进指针进行。

• 后退（Backward）指针：在节点中，BW 标记即为后退指针，它指向当前节点的前一个节点。这一指针在程序需要从表尾遍历至表头时发挥着关键作用。

  
  这样的设计使得跳跃表能够在不同的遍历方向上保持高效，无论是从表头到表尾，还是从表尾到表头，都能快速定位并访问相应的节点。

• 分值（score）：节点的分值（score 属性）是 double 类型的浮点数，用于标识跳跃表中各节点所保存的值。节点依据分值大小进行排序，确保整个跳跃表按照分值从小到大的顺序排列，从而维护了有序性。

• 成员对象（obj）：节点的成员对象（obj 属性)是一个指针，它指向一个字符申对象，而字符串对象则保存着一个 SDS 值。

层级（Level）

跳跃表节点的 Level 数组可以包含多个元素，每个元素均指向其他节点，程序正是通过这些层来加速对其他节点的访问。一般而言，层的数量越多，访问其他节点的速度便越快。

下图展示了 4 个不同高度的节点，它们的层数分别为 2 层、1 层和 2 层、1 层。

在创建新的跳跃表节点时，程序会根据幂次定律（即数值越大，其出现的概率越小）随机生成一个介于 1 和 32 之间的数值，作为 level 数组的大小，这个大小即为层的“高度”。

遍历搜索处理

1）首先访问跳跃表的起始点——表头节点，随后通过第 1 层的指针迅速跃迁到第 2 个节点。

2）到第 2 个节点后，程序并未继续向上层跃迁，而是选择沿着第 2 层的指针稳步前进，顺利到达第 4 个节点。

3）到第 4 个节点处，程序继续沿用相同的策略，对比之后，退回到即第 2 个节点沿着第 5 层的前进指针，平稳地转移至第 4 个节点。

4）当程序尝试从第 4 个节点继续沿着前进指针移动时，到了第 5 个节点。

注意，由于 C 语言的数组索引是从 0 开始的，因此节点的第一层对应的是 level[0]，第二层对应的是 level[1]，以此类推。这样的设计使得跳跃表在保持数据有序性的同时，能够高效地执行插入、删除和查找等操作。

跨度（Span）

层的跨度是用来记录相邻节点间的距离度量：当两个节点之间的跨度值越大，表明它们相隔的物理位置越远。跨度的主要作用在于计算节点的排位（rank）。在查找特定节点的过程中，程序会累加所经过各层的跨度值，最终得到的结果便是目标节点在跳跃表中的确切排位。

可以看到上面的图，可以得出第一个节点的 Span=0，第二个 span=（1），第三个节点的 span=（1+1），第四个节点的 span=（1+2），以此类推即可。

注意，所有指向NULL的前进指针的跨度均被设定为 0，因为它们并未指向任何有效的节点。

后退指针（backward）

节点的后退指针（backward属性）在从跳跃表尾部向头部方向进行节点访问时发挥着关键作用。

每个节点仅配有一个后退指针，因此每次只能逐步后退至紧邻的前一个节点，从跳跃表尾部逆向遍历至头部的节点路径。

借助跳跃表的tail指针快速定位到表尾节点，随后利用该节点的后退指针访问其前一个节点，即倒数第二个节点。接着，继续沿着后退指针逐步访问。

zskiplist

多个跳跃表节点就可以组成一个跳跃表，通过使用 zskiplist 结构来管理这些节点，程序能够更高效地处理整个跳跃表。这一结构不仅使得程序能够迅速访问跳跃表的表头节点和表尾节点，还能迅速获取跳跃表中节点的数量（即跳跃表的长度）等关键信息。

下图为 zskiplist 结构。

该结构包含以下核心属性：

typedef struct zskiplist {    struct zskiplistNode *header, *tail;    unsigned long length;    int level;} zskiplist;

• header：一个指向跳跃表表头节点的指针，用于快速定位跳跃表的起始位置。

• tail：一个指向跳跃表表尾节点的指针，便于从尾部对跳跃表进行操作或遍历。

• level：记录当前跳跃表中层数最多的节点的层数。

• length：表示跳跃表的长度，即跳跃表当前包含的节点数量。

最终总结

跳跃表是有序集合的底层实现机制之一，Redis 的跳跃表实现精巧地由 zskiplist 和 zskiplistNode 两个结构共同构成。其中，zskiplist 结构负责保存整个跳跃表的关键信息，如表头节点、表尾节点以及长度等，而 zskiplistNode 结构则用于具体表示跳跃表中的每一个节点。

跳跃表节点

每个跳跃表节点的层高并非固定，而是根据幂次定律随机生成的介于 1 至 32 之间的数值。这种设计既保证了跳跃表的灵活性，又能在一定程度上优化查找效率。在同一个跳跃表中，虽然多个节点可能包含相同的分值，但每个节点的成员对象必须保持唯一性，这确保了数据的准确性和一致性。

跳跃表链表

跳跃表中的节点严格按照分值大小进行排序。当分值相同时，节点则会根据成员对象的大小进一步排序，这种精细化的排序机制确保了跳跃表在处理复杂数据时依然能够保持高效和有序。

header 和 tail 指针

• header 和 tail 指针分别精准地指向跳跃表的起始和结束节点，这一设计确保了程序能够在 O(1)复杂度内迅速定位到表头节点和表尾节点，极大提高了处理效率。

• length 属性精确记录跳跃表中节点的数量，使得程序在 O(1)复杂度内就能轻松获取跳跃表的长度。

• level 属性则负责在 O(1)复杂度内迅速提供跳跃表中层高最大节点的层数信息，