Redis内部数据结构

吹梦到西洲

Redis

发布于：Jun 19, 2020

次浏览

Redis 和其他很多key-value 数据库的不同之处在于，Redis 不仅支持简单的字符串键值对，它还提供了一系列数据结构类型值，比如列表、哈希、集合和有序集，并在这些数据结构类型上定义了一套强大的 API 。

通过对不同类型的值进行操作，Redis 可以很轻易地完成其他只支持字符串键值对的key-value 数据库很难(或者无法)完成的任务。

在 Redis 的内部，数据结构类型值由高效的数据结构和算法进行支持，并且在 Redis 自身的构建当中，也大量用到了这些数据结构。

1 简单动态字符串

Sds (Simple Dynamic String，简单动态字符串)是 Redis 底层所使用的字符串表示，它被用在几乎所有的 Redis 模块中。

1.1 SDS的用途

实现字符串对象(StringObject);
在 Redis 程序内部用作 char* 类型的替代品。

Redis 是一个键值对数据库(key-value DB)，数据库的值可以是字符串、集合、列表等多种类型的对象，而数据库的键则总是字符串对象。

对于那些包含字符串值的字符串对象来说，每个字符串对象都包含一个 sds 值。

Note: “包含字符串值的字符串对象” ，这种说法初听上去可能会有点奇怪，但是在 Redis 中，一个字符串对象除了可以保存字符串值之外，还可以保存 long 类型的值，所以为了严谨起见，这里需要强调一下:当字符串对象保存的是字符串时，它包含的才是 sds 值，否则的话，它就是一个 long 类型的值。

1.2 Redis中的字符串

在 C 语言中，字符串可以用一个 \0 结尾的 char 数组来表示。比如说，hello world 在 C 语言中就可以表示为 "hello world\0" 。

这种简单的字符串表示在大多数情况下都能满足要求，但是，它并不能高效地支持长度计算和追加(append)这两种操作:

每次计算字符串长度(strlen(s))的复杂度为 $\Theta(N)$
对字符串进行 N 次追加，必定需要对字符串进行 N 次内存重分配(realloc)。

考虑到这两个原因，Redis 使用 sds 类型替换了 C 语言的默认字符串表示:sds 既可以高效地实现追加和长度计算，并且它还是二进制安全的。

SDS的实现

typedef char *sds;
struct sdshdr {
    // buf 已占用长度 
    int len;
    // buf 剩余可用长度 
    int free;
    // 实际保存字符串数据的地方
    char buf[]; 
};

通过 len 属性，sdshdr 可以实现复杂度为 θ(1) 的长度计算操作。另一方面，通过对 buf 分配一些额外的空间，并使用 free 记录未使用空间的大小，sdshdr 可以让执行追加操作所需的内存重分配次数大大减少。

1.3 优化追加操作

sds.c/sdsMakeRoomFor 函数描述了 sdshdr 的这种内存预分配优化策略，以下是这个函数的Python伪代码版本:

def sdsMakeRoomFor(sdshdr, required_len):
	# 预分配空间足够，无须再进行空间分配
    if (sdshdr.free >= required_len):
        return sdshdr
    # 计算新字符串的总长度
    newlen = sdshdr.len + required_len
    # 如果新字符串的总长度小于 SDS_MAX_PREALLOC
	# 那么为字符串分配 2 倍于所需长度的空间
	# 否则就分配所需长度加上 SDS_MAX_PREALLOC 数量的空间
    if newlen < SDS_MAX_PREALLOC:
        newlen *= 2
    else:
        newlen += SDS_MAX_PREALLOC
    # 分配内存
    newsh = zrelloc(sdshdr, sizeof(struct sdshdr)+newlen+1)
    # 更新 free 属性
	newsh.free = newlen - sdshdr.len
	# 返回 
    return newsh

1.4 小结

Redis 的字符串表示为 sds ，而不是 C 字符串(以 \0 结尾的 char*)。
对比 C 字符串，sds 有以下特性:
- 可以高效地执行长度计算(strlen);
- 可以高效地执行追加操作(append);
- 二进制安全;
sds 会为追加操作进行优化: 加快追加操作的速度，并降低内存分配的次数，代价是多占用了一些内存，而且这些内存不会被主动释放。

2 双端链表

双端链表作为一种通用的数据结构，在 Redis 内部使用得非常多:它既是 Redis 列表结构的底层实现之一，还被大量 Redis 模块所使用，用于构建 Redis 的其他功能。

2.1 双端链表的应用

实现 Redis 的列表类型

双端链表还是 Redis 列表类型的底层实现之一，当对列表类型的键进行操作——比如执行 RPUSH 、LPOP 或 LLEN 等命令时，程序在底层操作的可能就是双端链表。

Note: Redis 列表使用三种数据结构作为底层实现:

双端链表

压缩列表

快表(Quick List, Redis 3.2 之后提供)

因为双端链表占用的内存比压缩列表要多，所以当创建新的列表键时，列表会优先考虑使用压缩列表作为底层实现，并且在有需要的时候，才从压缩列表实现转换到双端链表实现。

Redis 自身功能的构建

除了实现列表类型以外，双端链表还被很多 Redis 内部模块所应用:

事务模块使用双端链表来按顺序保存输入的命令;
服务器模块使用双端链表来保存多个客户端;
订阅/发送模块使用双端链表来保存订阅模式的多个客户端;
事件模块使用双端链表来保存时间事件(time event).

2.2 双端链表的实现

双端链表的实现由 listNode 和 list 两个数据结构构成，下图展示了由这两个结构组成的一个双端链表实例:

其中，listNode 是双端链表的节点:

typedef struct listNode {
    // 前驱节点
    struct listNode *prev;
    // 后继节点
    struct listNode *next;
    // 值
    void *value;
} listNode;

而 list 则是双端链表本身:

typedef struct list {
    // 表头指针
	listNode *head; 
    // 表尾指针
	listNode *tail; 
    // 节点数量
	unsigned long len;
	// 复制函数
	void *(*dup)(void *ptr);
	// 释放函数
	void (*free)(void *ptr);
	// 比对函数
	int (*match)(void *ptr, void *key);
} list;

另外，从这两个数据结构的定义上，也可以它们的一些行为和性能特征:

listNode 带有 prev 和 next 两个指针，因此，对链表的遍历可以在两个方向上进行:从表头到表尾，或者从表尾到表头。
list 保存了 head 和 tail 两个指针，因此，对链表的表头和表尾进行插入的复杂度都为 $\Theta(1)$ ——这是高效实现 LPUSH 、RPOP 、RPOPLPUSH 等命令的关键。
list 带有保存节点数量的 len 属性，所以计算链表长度的复杂度仅为 $\Theta(1)$ ，这也保证了 LLEN 命令不会成为性能瓶颈。

2.3 迭代器

Redis 为双端链表实现了一个迭代器 ，这个迭代器可以从两个方向对双端链表进行迭代:

沿着节点的next指针前进，从表头向表尾迭代;
沿着节点的prev指针前进，从表尾向表头迭代.

以下是迭代器的数据结构定义

typedef struct listIter {
    listNode *next; // 下一节点
    int direction; // 迭代方向
    // 如果值为 adlist.h/AL_START_HEAD，那么迭代器执行从表头到表尾的迭代;
    // 如果值为 adlist.h/AL_START_TAIL，那么迭代器执行从表尾到表头的迭代;
} listIter;

2.4 小结

Redis 实现了自己的双端链表结构
双端链表主要有两个作用:
- 作为 Redis 列表类型的底层实现之一;
- 作为通用数据结构，被其他功能模块所使用。
双端链表及其节点的性能特性如下:
- 节点带有前驱和后继指针，访问前驱节点和后继节点的复杂度为 $O(1)$ ，并且对链表的迭代可以在从表头到表尾和从表尾到表头两个方向进行;
- 链表带有指向表头和表尾的指针，因此对表头和表尾进行处理的复杂度为 $O(1)$ ;
- 链表带有记录节点数量的属性，所以可以在 $O(1)$ 复杂度内返回链表的节点数量(长度).

3 字典

字典(dictionary)，又名映射(map)或关联数组(associative array)，它是一种抽象数据结构，由一集键值对(key-value pairs)组成，各个键值对的键各不相同，程序可以将新的键值对添加到字典中，或者基于键进行查找、更新或删除等操作。

3.1 字典的应用

字典在 Redis 中的应用广泛，使用频率可以说和 SDS 以及双端链表不相上下，基本上各个功能模块都有用到字典的地方。其中，字典的主要用途有以下两个:

实现数据库键空间 (key space)，这里指的是整个 Redis 中的键，包括字符串、列表、集合，哈希、有序集合中的所有键;
用作 Hash 类型键的其中一种底层实现。

🙋实现数据库键空间

Redis 是一个键值对数据库，数据库中的键值对就由字典保存：每个数据库都有一个与之相对应的字典，这个字典被称之为键空间(key space)。

当用户添加一个键值 $key-value$ 中的 $key$ 对到数据库时(不论键值对是什么类型)，程序就将该键值对添加到键空间;当用户从数据库中删除一个键值对时，程序就会将这个键值对从键空间中删除等等。

# 清空键空间上的所有键值对数据:
redis> FLUSHDB
ok
# 返回键空间上现有的键值对:
redis> DBSIZE
(integer) 0

大部分针对数据库的命令，比如 DBSIZE 、FLUSHDB 、:ref:RANDOMKEY等等，都是构建于对字典的操作之上的;而那些创建、更新、删除和查找键值对的命令，也无一例外地需要在键空间上进行操作。

🙋用作 Hash 类型键的其中一种底层实现

Redis 的 Hash 类型键使用以下两种数据结构作为底层实现:

字典
压缩列表

因为压缩列表比字典更节省内存，所以程序在创建新 Hash 键时，默认使用压缩列表作为底层实现，当有需要时，程序才会将底层实现从压缩列表转换到字典。

3.2 字典的实现

实现字典的方法有很多种：

最简单的就是使用链表或数组，但是这种方式只适用于元素个数不多的情况下;
要兼顾高效和简单性，可以使用哈希表;
如果追求更为稳定的性能特征，并且希望高效地实现排序操作的话，则可以使用更为复杂的平衡树。

在众多可能的实现中，Redis 选择了高效且实现简单的哈希表作为字典的底层实现。dict.h/dict 给出了这个字典的定义:

/*
* 字典
*
* 每个字典使用两个哈希表，用于实现渐进式 rehash 
*/
typedef struct dict {
    // 特定于类型的处理函数
    dictType *type;
    // 类型处理函数的私有数据
    void *privdata;
    // 哈希表(2 个)
    dictht ht[2];
    // 记录 rehash 进度的标志，值为-1 表示 rehash 未进行
    int rehashidx;
    // 当前正在运作的安全迭代器数量
	int iterators;
} dict;

🙋哈希表的实现

字典所使用的哈希表实现由 dict.h/dictht 类型定义:

/**
* 哈希表的定义
*/
typedef struct dictht {
    // 哈希表节点指针数组(俗称桶，bucket)
    dictEntry **table;
    // 指针数组的大小
    unsigned long size;
    // 指针数组的长度掩码，用于计算索引值
    unsigned long sizemask;
    // 哈希表现有的节点数量
    unsigned long used;
    
} dictht;

table 属性是一个数组，数组的每个元素都是一个指向 dictEntry 结构的指针。每个 dictEntry 都保存着一个键值对，以及一个指向另一个 dictEntry 结构的指针:

/**
* 哈希表节点
*/
typedef struct dictEntry {
    // key
    void *key;
    // value
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
    } v;
    // 链往后继节点
    struct dictEntry *next;
} dictEntry;

next 属性指向另一个 dictEntry 结构，多个 dictEntry 可以通过 next 指针串连成链表，从这里可以看出，dictht 使用链地址法来处理键碰撞: 当多个不同的键拥有相同的哈希值时，哈希表用一个链表将这些键连接起来。

下图展示了一个由 dictht 和数个 dictEntry 组成的哈希表例子:

如果再加上之前列出的 dict 类型，那么整个字典结构可以表示如下:

在上图的字典示例中，字典虽然创建了两个哈希表，但正在使用的只有 $0$ 号哈希表，这说明字典未进行 rehash 状态。

🙋哈希算法

Redis 目前使用两种不同的哈希算法:

MurmurHash2 32 bit 算法:这种算法的分布率和速度都非常好，具体信息请参考 MurmurHash 的主页。
基于 djb 算法实现的一个大小写无关散列算法

使用哪种算法取决于具体应用所处理的数据:

命令表以及 Lua 脚本缓存都用到了算法 2
算法 1 的应用则更加广泛:数据库、集群、哈希键、阻塞操作等功能都用到了这个算法

3.3 创建新字典

1
2
3

// dictCreate 函数创建并返回一个新字典:
dict *d = dictCreate(&hash_type, NULL);
// d 的值可以用图片表示如下:

新创建的两个哈希表都没有为 table 属性分配任何空间:

ht[0]->table 的空间分配将在第一次往字典添加键值对时进行;
ht[1]->table 的空间分配将在 rehash 开始时进行.

3.4 添加键值对到字典

根据字典所处的状态，将一个给定的键值对添加到字典可能会引起一系列复杂的操作:

如果字典为未初始化(也即是字典的 $0$ 号哈希表的 table 属性为空)，那么程序需要对 $0$ 号哈希表进行初始化;
如果在插入时发生了键碰撞，那么程序需要处理碰撞;
如果插入新元素使得字典满足了 rehash 条件，那么需要启动相应的 rehash 程序.

当程序处理完以上三种情况之后，新的键值对才会被真正地添加到字典上，整个添加流程可以用下图表示：

在接下来的三节中，我们将分别看到添加操作如何在以下三种情况中执行:

字典为空;
添加新键值对时发生碰撞处理;
添加新键值对时触发了 rehash 操作.

3.5 添加新元素到空白字典

当第一次往空字典里添加键值对时，程序会根据 dict.h/DICT_HT_INITIAL_SIZE 里指定的大

小为 d->ht[0]->table 分配空间。字典空白时的样子如 3.3 创建新字典 图所示，以下是往空白字典添加了第一个键值对之后的样子:

3.6 添加新键值对时发生碰撞处理

在哈希表实现中，当两个不同的键拥有相同的哈希值时，我们称这两个键发生碰撞(collision)，而哈希表实现必须想办法对碰撞进行处理。

字典哈希表所使用的碰撞解决方法被称之为链地址法:这种方法使用链表将多个哈希值相同的节点串连在一起，从而解决冲突问题。

假设现在有一个带有三个节点的哈希表，如下图:

对于一个新的键值对 key4 和 value4 ，如果 key4 的哈希值和 key1 的哈希值相同，那么它们将在哈希表的 $0$ 号索引上发生碰撞。通过将 key4-value4 和 key1-value1 两个键值对用链表连接起来，就可以解决碰撞的问题:

3.7 添加新键值对时触发了 rehash 操作

对于使用链地址法来解决碰撞问题的哈希表 dictht 来说，哈希表的性能依赖于它的大小(size属性)和它所保存的节点的数量(used 属性)之间的比率:

比率在 $1:1$ 时，哈希表的性能最好;
如果节点数量比哈希表的大小要大很多的话，那么哈希表就会退化成多个链表，哈希表本身的性能优势就不再存在.

举个例子，对于下面这个哈希表，平均每次失败查找只需要访问 $1$ 个节点(非空节点访问 $2$ 次，空节点访问 $1$ 次):

而对于下面这个哈希表，平均每次失败查找需要访问 $5$ 个节点:

为了在字典的键值对不断增多的情况下保持良好的性能，字典需要对所使用的哈希表(ht[0]) 进行 rehash 操作:在不修改任何键值对的情况下，对哈希表进行扩容，尽量将比率维持在 $1:1$ 左右。

dictAdd 在每次向字典添加新键值对之前，都会对哈希表 ht[0] 进行检查，对于 ht[0] 的 size 和 used 属性，如果它们之间的比率 $ratio = used / siz$e 满足以下任何一个条件的话， rehash 过程就会被激活:

自然 $rehash :ratio \ge 1$ ，且变量 dict_can_resize 为真。
强制 $rehash : ratio$ 大于变量 dict_force_resize_ratio（默认5）。

什么时候 dict_can_resize 会为假?

一个数据库就是一个字典，数据库里的哈希类型键也是一个字典，当 Redis 使用子进程对数据库执行后台持久化任务时(比如执行 BGSAVE 或 BGREWRITEAOF 时)，为了最大化地利用系统的 copy on write 机制，程序会暂时将 dict_can_resize 设为假，避免执行自然 rehash ，从而减少程序对内存的触碰(touch)。

当持久化任务完成之后，dict_can_resize 会重新被设为真。
另一方面，当字典满足了强制 rehash 的条件时，即使 dict_can_resize 不为真(有 BGSAVE或 BGREWRITEAOF 正在执行)，这个字典仍然会被 rehash 。

3.8 Rehash执行过程

字典的 rehash 操作实际上就是执行以下任务:

创建一个比ht[0]->table容量更大的ht[1]->table;
将ht[0]->table中的所有键值对迁移到ht[1]->table;
将原有ht[0]的数据清空，并将ht[1]替换为新的ht[0](备胎上位)

经过以上步骤之后，程序就在不改变原有键值对数据的基础上，增大了哈希表的大小。

作为例子，以下四个小节展示了一次对哈希表进行 rehash 的完整过程。

1 开始 rehash

这个阶段有两个事情要做:

设置字典的 rehashidx 为 $0$ ，标识着 rehash 的开始;
为ht[1]->table分配空间，大小至少为ht[0]->used的两倍.

这时的字典是这个样子:

2 Rehash 进行中

在这个阶段，ht[0]->table 的节点会被逐渐迁移到 ht[1]->table ，因为 rehash 是分多次进行的(细节在下一节解释)，字典的 rehashidx 变量会记录 rehash 进行到 ht[0] 的哪个索引。以下是 rehashidx 值为 2 时，字典的样子:

注意除了节点的移动外，字典的 rehashidx 、ht[0]->used 和 ht[1]->used 三个属性也产生了变化。

3 节点迁移完毕

到了这个阶段，所有的节点都已经从 ht[0] 迁移到 ht[1] 了:

4 rehash 完毕

在 rehash 的最后阶段，程序会执行以下工作:

释放ht[0]的空间;
用ht[1]来代替ht[0]，使原来的ht[1]成为新的ht[0];
创建一个新的空哈希表，并将它设置为ht[1];
将字典的 rehashidx 属性设置为 -1 ，标识 rehash 已停止;

以下是字典 rehash 完毕之后的样子:

对比字典 rehash 之前和 rehash 之后，新的 ht[0] 空间更大，并且字典原有的键值对也没有被修改或者删除。

3.9 渐进式 rehash

假设这样一个场景:在一个有很多键值对的字典里，某个用户在添加新键值对时触发了 rehash 过程，如果这个 rehash 过程必须将所有键值对迁移完毕之后才将结果返回给用户，这样的处理方式谁能接受？另一方面，要求服务器必须阻塞直到 rehash 完成，这对于 Redis 服务器本身也是不能接受的。

所以rehash 程序并不是在激活之后就马上执行直到完成的，而是分多次、渐进式地完成的。

为了解决这个问题，Redis 使用了渐进式(incremental)的 rehash 方式：通过将 rehash 分散到多个步骤中进行，从而避免了集中式的计算。

渐进式 rehash 主要由 _dictRehashStep 和 dictRehashMilliseconds 两个函数进行:

_dictRehashStep 用于对数据库字典、以及哈希键的字典进行被动 rehash ;
dictRehashMilliseconds则由 Redis 服务器常规任务程序(server cron job)执行，用于对数据库字典进行主动 rehash.

_dictRehashStep

每次执行 _dictRehashStep ，ht[0]->table 哈希表第一个不为空的索引上的所有节点就会全部迁移到 ht[1]->table .

在 rehash 开始进行之后(d->rehashidx 不为 $-1$)，每次执行一次添加、查找、删除操作，_dictRehashStep 都会被执行一次:

dictRehashMilliseconds

dictRehashMilliseconds 可以在指定的毫秒数内，对字典进行 rehash 。

当 Redis 的服务器常规任务执行时，dictRehashMilliseconds 会被执行，在规定的时间内，尽可能地对数据库字典中那些需要 rehash 的字典进行 rehash ，从而加速数据库字典的 rehash 进程(progress)。

其他措施

在哈希表进行 rehash 时，字典还会采取一些特别的措施，确保 rehash 顺利、正确地进行:

因为在 rehash 时，字典会同时使用两个哈希表，所以在这期间的所有查找、删除等操作，除了在 ht[0] 上进行，还需要在ht[1]上进行。
在执行添加操作时，新的节点会直接添加到ht[1]而不是ht[0]，这样保证ht[0]的节点数量在整个 rehash 过程中都只减不增。

3.10 字典收缩

上面关于 rehash 的章节描述了通过 rehash 对字典进行扩展(expand)的情况，如果哈希表的可用节点数比已用节点数大很多的话，那么也可以通过对哈希表进行 rehash 来收缩(shrink) 字典。

收缩 rehash 和上面展示的扩展 rehash 的操作几乎一样，它执行以下步骤:

创建一个比ht[0]->table小的ht[1]->table;
将ht[0]->table中的所有键值对迁移到ht[1]->table;
将原有ht[0]的数据清空，并将ht[1]替换为新的ht[0].

扩展 rehash 和收缩 rehash 执行完全相同的过程，一个 rehash 是扩展还是收缩字典，关键在于新分配的 ht[1]->table 的大小:

如果 rehash 是扩展操作，那么 ht[1]->table 比 ht[0]->table 要大;
如果 rehash 是收缩操作，那么 ht[1]->table 比 ht[0]->table 要小.

字典的收缩规则由 redis.c/htNeedsResize 函数定义:

/*
* 检查字典的使用率是否低于系统允许的最小比率 *
* 是的话返回 1 ，否则返回 0 。
*/
int htNeedsResize(dict *dict) { long long size, used;
    // 哈希表已用节点数量 
	size = dictSlots(dict);
    // 哈希表大小
    used = dictSize(dict);
    // 当哈希表的大小大于 DICT_HT_INITIAL_SIZE
    // 并且字典的填充率低于 REDIS_HT_MINFILL 时
    // 返回 1
    return (size && used && size > DICT_HT_INITIAL_SIZE 
            && (used*100/size < REDIS_HT_MINFILL));
}

在默认情况下，REDIS_HT_MINFILL 的值为 $10$ ，也即是说，当字典的填充率低于 $10%$ 时，程序就可以对这个字典进行收缩操作了。

字典收缩和字典扩展的一个区别是:

字典的扩展操作是自动触发的(不管是自动扩展还是强制扩展);
而字典的收缩操作则是由程序手动执行。

因此，使用字典的程序可以决定何时对字典进行收缩:

当字典用于实现哈希键的时候，每次从字典中删除一个键值对，程序就会执行一次htNeedsResize 函数，如果字典达到了收缩的标准，程序将立即对字典进行收缩;
当字典用于实现数据库键空间 (key space) 的时候，收缩的时机由 redis.c/tryResizeHashTables 函数决定

3.11 字典的迭代

字典带有自己的迭代器实现—对字典进行迭代实际上就是对字典所使用的哈希表进行迭代:

迭代器首先迭代字典的第一个哈希表，然后，如果 rehash 正在进行的话，就继续对第二个哈希表进行迭代。
当迭代哈希表时，找到第一个不为空的索引，然后迭代这个索引上的所有节点。
当这个索引迭代完了，继续查找下一个不为空的索引，如此循环，一直到整个哈希表都迭代完为止。

def iter_dict(dict): 
    # 迭代 0 号哈希表
	iter_table(ht[0]->table)
	# 如果正在执行 rehash ，那么也迭代 1 号哈希表
	if dict.is_rehashing(): 
        iter_table(ht[1]->table) 

def iter_table(table):
	# 遍历哈希表上的所有索引 
    for index in table:
		# 跳过空索引
		if table[index].empty():
            continue
        # 遍历索引上的所有节点
        for node in table[index]:
            # 处理节点 
            do_something_with(node)

3.12 小结

字典由键值对构成的抽象数据结构。
Redis 中的数据库和哈希键都基于字典来实现。
Redis 字典的底层实现为哈希表，每个字典使用两个哈希表，一般情况下只使用 $0$ 号哈希表，只有在 rehash 进行时，才会同时使用 $0$ 号和 $1$ 号哈希表。
哈希表使用链地址法来解决键冲突的问题。
rehash 可以用于扩展或收缩哈希表。
对哈希表的 rehash 是分多次、渐进式地进行的。

4 跳跃表

跳跃表(skiplist)是一种随机化的数据，由 $William Pugh$ 在论文《Skip lists: a probabilistic alternative to balanced trees》中提出，这种数据结构以有序的方式在层次化的链表中保存元素，它的效率可以和平衡树媲美——查找、删除、添加等操作都可以在对数期望时间下完成，并且比起平衡树来说，跳跃表的实现要简单直观得多。

以下是一个典型的跳跃表例子(图片来自维基百科):

从图中可以看到，跳跃表主要由以下部分构成:

表头(head): 负责维护跳跃表的节点指针
跳跃表节点: 保存着元素值，以及多个层
层: 保存着指向其他元素的指针。高层的指针越过的元素数量大于等于低层的指针，为了提高查找的效率，程序总是从高层先开始访问，然后随着元素值范围的缩小，慢慢降低层次。
表尾:全部由NULL组成，表示跳跃表的末尾。

4.1 跳跃表的实现

为了适应自身的功能需要，Redis 基于 William Pugh 论文中描述的跳跃表进行了以下修改:

允许重复的score值:多个不同的member的score值可以相同。
进行对比操作时，不仅要检查score值，还要检查member：当score值可以重复时，单靠 score 值无法判断一个元素的身份，所以需要连 member 域都一并检查才行。
每个节点都带有一个高度为 $1$ 层的后退指针，用于从表尾方向向表头方向迭代：当执行 ZREVRANGE 或 ZREVRANGEBYSCORE 这类以逆序处理有序集的命令时，就会用到这个属性。

这个修改版的跳跃表由 redis.h/zskiplist 结构定义:

typedef struct zskiplist {
    // 头节点、尾结点
    struct zskiplistNode *header, *tail;
    // 节点数量
    unsigned long length;
    // 目前表内节点的最大层数
    int level;
} zskiplist;

跳跃表的节点由 redis.h/zskiplistNode 定义:

typedef struct zskiplistNode {
    // member object
    robj *obj;
    double score;
    struct zskiplistNode *backward;
    // level
    struct zskiplistLevel {
        // 前进指针
        struct zskiplistNode *forward;
        // 这个层跨越的节点数量
        unsigned int span;
    } level[];
} zskiplistNode;

4.2 跳跃表的应用

和字典、链表或者字符串这几种在 Redis 中大量使用的数据结构不同，跳跃表在 Redis 的唯一作用，就是实现有序集数据类型。

跳跃表将指向有序集的 score 值和 member 域的指针作为元素，并以 score 值为索引，对有序集元素进行排序。

举个例子，以下代码就创建了一个带有 $3$ 个元素的有序集:

127.0.0.1:6379> zadd s 6 x 10 y 15 z
(integer) 3
127.0.0.1:6379> zrange s 0 -1 withscores
1) "x"
2) "6"
3) "y"
4) "10"
5) "z"
6) "15"

在底层实现中，Redis 为 x 、y 和 z 三个 member 分别创建了三个字符串，并为 6 、10 和 15分别创建三个 double 类型的值，然后用一个跳跃表将这些指针有序地保存起来，形成这样一个跳跃表：

为了展示的方便，在图片中我们直接将 member 和 score 值包含在表节点中，但是在实际的定义中，因为跳跃表要和另一个实现有序集的结构(字典)分享 member 和 score 值，所以跳跃表只保存指向 member 和 score 的指针。

小结

跳跃表是一种随机化(概率性)数据结构，它的查找、添加、删除操作都可以在对数期望时间下完成。
跳跃表目前在 Redis 的唯一作用就是作为有序集类型的底层数据结构(之一，另一个构成有序集的结构是字典)。
为了适应自身的需求，Redis 基于 $William Pugh$ 论文中描述的跳跃表进行了修改，包括:
- score 值可重复
- 对比一个元素需要同时检查它的score和memeber
- 每个节点带有高度为 $1$ 层的后退指针，用于从表尾方向向表头方向迭代。