Redis - 跳表以及其内部结构

跳表的结构

今天在看《Redis 设计与实现》中关于跳表的这一章时，出现完全看不懂它的结构的情况，书中展示跳表的结构是这样的：

然而，一般的文章介绍中，跳表是长这样的：

我有限的想象力没法让我将这两幅图对应起来，然后借助万能的谷歌，我找到了一篇关于跳表的论文（Skip Lists: A Probabilistic Alternative to Balanced Trees），也看到了它原来的面目，这才是跳表比较容易理解的一种结构：

1. 每个节点都保存着一个对象，每个对象都有多层指针来指向同一层的下一个节点。

2. 由于同一个跳表中，对象只会创建一次，因此不用担心层次变多后消耗的资源增加很多。

3. 有一个保存层级的表头节点，最后均指向 NULL

通过这张图再来理解《Redis 设计与实现》中的跳表结构，就一目了然了。

为什么要使用跳表

当集合中需要快速在大量的元素进行搜索时，首先会想到通过平衡树的方式来组织数据，比如 MySQL 中的 InnoDB 引擎就是使用索引组织树来保存数据的。但是 Redis 中却没有使用平衡树结构，这个原因在 Redis 官网中也有阐述过，跟上面提到的那篇论文的概述是一样：

Skip lists are a data structure that can be used in place of balanced trees.Skip lists use probabilistic balancing rather than strictly enforced balancingand as a result the algorithms for insertion and deletion in skip lists aremuch simpler and significantly faster than equivalent algorithms forbalanced trees.

跳表是一种可以用来代替平衡树的数据结构。跳表使用概率平衡而不是严格执行的平衡，因此，与等价的平衡树的算法相比，跳表中的插入和删除算法要简单得多，并且速度要快得多。

Redis 中跳表的特点

1. 跳表查找的平均时间复杂度为 O(logN)，最坏时间复杂度为 O(N)。

2. 每个跳表节点的层高都是 1~32 之间的随机数，也就是说，每个节点被插入后会通过随机的方式决定要不要增加层，以及增加多少层。

3. level 中的跨度（span）是用来计算排位的：在查找某个节点的过程中，将沿途访问过的所有层的跨度累加，得到的结果就是目标节点在跳表中排位。

4. 同一个跳表中，可以包含多个分值相同的节点，但是每个节点中的成员对象必须唯一（符合 Set 的定义）

5. 跳表中的节点按分值大小进行排序，当分值相同时，节点按成员对象的大小进行排序。

有序列表中跳表的使用

在 Redis 中，只有两处地方用到了跳表：

1. 有序列表中保存值

2. 集群节点中用作内部数据结构

基本上，Redis 中的对象都会有两种数据结构来保存数据，对于有序列表而言，它也使用了两种数据结构来保存数据，分别是：ziplist（压缩列表）、skiplist（跳表）

他们的转换条件是：

• 有序集合保存的所有元素的长度都小于 64 字节

• 保存的元素个数少于 128 个

如果满足以上两个条件，则使用 ziplist 来保存，任意一个条件不满足，就使用 skiplist 来保存。

同时使用跳表和字典来实现

但是需要注意的是，实际上，如果有序列表使用了跳表这种结构来保存时，会同时创建一个 hashtable 对象用以记录对象和它的分值。在实际中， 字典和跳跃表会共享元素的成员和分值， 所以并不会造成任何数据重复，也不会因此而浪费任何内存。

而之所以这样做，是为了让有序集合的命令能高效的执行。以下引用《Redis 设计与实现》的原文：

“在理论上来说， 有序集合可以单独使用字典或者跳跃表的其中一种数据结构来实现， 但无论单独使用字典还是跳跃表， 在性能上对比起同时使用字典和跳跃表都会有所降低。”

举个例子， 如果我们只使用字典来实现有序集合， 那么虽然以 O(1) 复杂度查找成员的分值这一特性会被保留， 但是， 因为字典以无序的方式来保存集合元素， 所以每次在执行范围型操作 —— 比如 ZRANK 、 ZRANGE 等命令时， 程序都需要对字典保存的所有元素进行排序， 完成这种排序需要至少 O(NlogN)时间复杂度,以及额外的 O(N)的内存空间 （因为要创建一个数组来保存排序后的元素）。

另一方面， 如果我们只使用跳跃表来实现有序集合， 那么跳跃表执行范围型操作的所有优点都会被保留， 但因为没有了字典， 所以根据成员查找分值这一操作的复杂度将从 O(1)上升到 O(logn)。

因为以上原因， 为了让有序集合的查找和范围型操作都尽可能快地执行， Redis 选择了同时使用字典和跳跃表两种数据结构来实现有序集合。