Redis源码分析 t_zset.c
在 Redis 源码库中，跳跃表的实现可以在 "server.h" 和 "t_zset.c" 文件中找到。
数据结构分析
server.h: 这个文件定义了跳跃表节点和跳跃表数据结构。跳跃表结构包括头指针、尾指针、长度和层级。跳跃表节点包括键、分数、向前指针和向后指针。 链接 在 server.h 中，跳跃表的定义部分如下：
typedef struct zskiplistNode {
robj *obj; // 节点的对象
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;
上述代码中，zskiplistNode 结构体表示跳跃表的节点，包含了节点的成员对象和分值，以及前进指针、后退指针和跨度。跳跃表的层数是动态生成的，因此 level 是一个柔性数组，用于存储节点的前进指针和跨度信息。zskiplist 结构体表示跳跃表，包含了头节点、尾节点、节点数量和最大层数等信息。
跳跃表的节点按照分值从小到大排序，因此在插入和删除节点时需要保证跳跃表的有序性。跳跃表的节点和层数是动态生成的，因此跳跃表的性能非常优秀，在实现 Redis 的有序集合等功能时，跳跃表是一个非常重要的数据结构。
+-----------------------+
header ->| zskiplistNode |<-+
|-----------------------| |
| ele | |
| score | |
| backward ------+ |
| zskiplistLevel[0] | |
|-----------------------| |
| ele | |
| score | |
| backward ------+ |
| zskiplistLevel[1] | |
|-----------------------| |
| ... | |
+-----------------------+ |
| | |
| | |
| | |
| | |
|-----------------------| |
| zskiplistNode |<-+
tail ->|-----------------------|
| ele |
| score |
| backward -------|
| zskiplistLevel[0] |
|-----------------------|
| ele |
| score |
| backward -------|
| zskiplistLevel[1] |
|-----------------------|
| ... |
+-----------------------+
zskiplist data structure
其中，zskiplistNode 表示跳跃表的节点结构体，包含元素（ele）、分值（score）、后退指针（backward）和多层前进指针（level）。zskiplist 则表示整个跳跃表的数据结构，包含表头（header）、表尾（tail）、表长度（length）和跳跃表的层数（level）。在跳跃表中，节点之间的关系由前进指针和后退指针来维护，而多层前进指针使得跳跃表的查询、插入和删除操作都具有 O(log n) 的时间复杂度。
下面是一个基于上述跳跃表结构的范例，其中包含了若干个节点，每个节点包含一个字符串类型的元素和一个浮点数类型的分值：
+-----------------------+
| zskiplistNode 1 |------------------------------+
|-----------------------| |
| "hello" | |
| 3.14 | |
| backward ----> NULL | |
| level[0] ---->----------------------------------+
| forward ----> NULL |
| span ----> 0 |
| level[1] ----> NULL |
| forward ----> NULL |
| span ----> 0 |
| level[2] ----> NULL |
| forward ----> NULL |
| span ----> 0 |
+-----------------------+
+-----------------------+
| zskiplistNode 2 |-------------------------------------------------------+
|-----------------------| |
| "world" | |
| 5.67 | |
| backward ----> zskiplistNode 1 |
| level[0] ---->-----------------------------------------------------------+
| forward ----> zskiplistNode 3 |
| span ----> 2 |
| level[1] ---->-----------------------------------------------------------+
| forward ----> zskiplistNode 3 |
| span ----> 2 |
| level[2] ---->-----------------------------------------------------------+
| forward ----> NULL |
| span ----> 0 |
+-----------------------+
+-----------------------+
| zskiplistNode 3 |---------------------------------------+
|-----------------------| |
| "foo" | |
| 2.5 | |
| backward ----> zskiplistNode 2 |
| level[0] ---->-------------------------------------------+
| forward ----> zskiplistNode 4 |
| span ----> 1 |
| level[1] ---->-------------------------------------------+
| forward ----> zskiplistNode 4 |
| span ----> 1 |
| level[2] ---->-------------------------------------------+
| forward ----> zskiplistNode 5 |
| span ----> 2 |
+-----------------------+
+-----------------------+
| zskiplistNode 4 |--------------------------------+
|-----------------------| |
| "bar" | |
| 6.78 | |
| backward ----> zskiplistNode 3 |
| level[0] ---->------------------------------------+
| forward ----> zskiplistNode 5 |
| span ----> 2 |
| level[1] ---->------------------------------------+
| forward ----> NULL |
| span ----> 0 |
| level[2] ---->------------------------------------+
| forward ----> NULL |
| span ----> 0 |
+-----------------------+
+-----------------------+
| zskiplistNode 5 |---------------------------------------+
|-----------------------| |
| "baz" | |
| 1.23 | |
| backward ----> zskiplistNode 4 |
| level[0] ---->-------------------------------------------+
| forward ----> NULL |
| span ----> 0 |
| level
在上面的跳跃表示例中，我们可以通过 forward 指针和 span 跨度值来快速定位到目标节点。以查找节点 "bar" 为例，查找的过程如下：
- 从跳跃表的最高层开始，从表头开始遍历跳跃表，直到找到一个节点的 forward 指针指向的节点分值大于等于 "bar" 的分值为止。在示例中，最高层的第一个节点 "hello" 的分值小于 "bar" 的分值，因此我们需要继续往右移动，直到找到一个节点的分值大于等于 "bar" 的分值。
- 在第一层中，我们可以找到分值大于等于 "bar" 的第一个节点是节点 "foo"，而节点 "foo" 的 forward 指针指向节点 "bar"。因此，我们可以从节点 "foo" 的 forward 指针和 span 跨度值计算出节点 "bar" 的位置，从而找到了目标节点。
实现细节
Redis 中跳跃表的实现非常复杂，包括节点的插入、删除、查找等操作，还包括跳跃表层数的动态调整等。
以下是相关源代码文件的摘要和链接：
t_zset.c: 这个文件包含了跳跃表的各种操作，如插入、删除、查找等。t_zset.c 在 t_zset.c 中，你可以找到以下跳跃表操作的实现：
zslCreate (创建跳跃表) 在 Redis 中，zslCreate 函数用于创建一个新的跳跃表。这个函数会为跳跃表分配内存，并且会初始化跳跃表的一些基本属性，例如头节点、尾节点、长度和层数等。根据默认值，跳跃表的层数为 32。
因为跳跃表中的每个节点都包含一个 level 数组，而这个数组的大小是根据跳跃表的层数确定的，因此跳跃表的大小会随着层数的增加而增加。具体而言，如果我们使用默认的层数 32，那么跳跃表的每个节点就会包含一个大小为 32 的 level 数组，这个数组的大小是固定的。假设每个指针大小为 8 字节，跨度大小为 4 字节，而每个节点中还包含一个指向字符串对象的指针和一个 double 类型的分值，那么每个节点的大小大约为 128 字节。因此，如果跳跃表中包含 1 千万个节点，那么跳跃表的总大小约为 1.2 GB 左右。
zslFree (释放跳跃表)
zslInsert (插入节点)
zslDelete (删除节点)
zslFind (查找节点)
zslGetRank (获取节点的排名)
zslDeleteRangeByScore (根据分数范围删除节点)
zslDeleteRangeByRank (根据排名范围删除节点)
跨度和随机生成层数
Redis 中跳跃表的节点除了包含指向上下左右节点的指针外，还包含了跨度信息。跨度是指当前节点到下一个节点之间的节点数量，用于优化跳跃表的查询性能。另外，Redis 中跳跃表的层数是动态生成的，需要根据节点数量和分值范围动态调整。需要关注跨度和层数的生成和使用方式。
跳跃表的应用场景
Redis 中跳跃表的主要应用场景是实现有序集合。需要理解有序集合的数据结构和功能，以便于理解跳跃表在 Redis 中的应用。同时，需要关注跳跃表在其他场景中的应用，以便于理解和分析跳跃表的实现原理。
为什么说最大容纳是2^64个元素呢
简单来说，假设我们有一个最大容量为 N 的跳跃表，那么它最多可以容纳 N 个元素。而跳跃表的高度（即最大层数）可以通过以下公式计算： ZSKIPLIST_MAXLEVEL = log(N) / log(2) 其中 log(N) 表示以 2 为底数的 N 的对数，也就是 N 的二进制位数。因为每一层的节点数量是从下往上依次减半的，所以我们可以通过向上取整来得到最大的层数，使得每一层的节点数都小于等于上一层的节点数的一半。 当 N 等于 2 的 64 次方时，它的二进制位数为 64，因此我们可以得到： ZSKIPLIST_MAXLEVEL = log(2^64) / log(2) = 64 因此，如果使用默认的 ZSKIPLIST_MAXLEVEL 值（即 32），跳跃表最多可以容纳 2 的 64 次方个元素，因为它是根据上述公式计算得到的。