定义
跳跃表（skip list），简称跳表，是一个随机化的数据结构，实质是一种可以进行二分查找的有序链表。跳跃表在原有的单向有序链表上增加了多级的索引，通过索引实现快速查找，快速插入，快速删除的性能。
跳跃表可以看作是二叉树的一个变种，在性能上与红黑树，AVL树等不相上下，但是实现原理相对简单很多，目前在redis和levelDB中均有使用。
实现原理
对于一个单向的有序链表而言，如果我们想在链表中查找某个数据，只能从头到尾遍历链表，这样的查找效率比较低，时间复杂度也会很高，复杂度为O(n)。
为了提高查找的效率，我们可以考虑在单向有序链表上增加索引的方式，比如，每两个链表结点提取一个结点到上一级，我们将抽出来的那一级别叫做索引，如下图：
假设我们需要查找结点8，可以先在索引层（L1）进行遍历，当遍历到索引层中值为7的结点时，发现下一个结点的值为9，那么，需要查找值为8的结点必然在这两个结点之间，这时我们可以下降到链表层继续遍历，就可以找到了值为8的结点。
原先我们在单向有序链表中查找值为8的结点，需要遍历8个结点才能查找到，而增加了一级索引的跳跃表中，只需要遍历5个结点就能查找到，查找性能得到提升。
理论上，如果我们再增加一层索引，则查找效率可以得到进一步的提升：
在以上的例子中，结点数量较少，当结点数量较大时，可以进一步增加多级索引，其查找效率可以得到明显的提升。比如下图表示的三级索引：
redis中跳跃表的使用
在redis中使用跳跃表作为有序集合的底层实现之一，如果一个有序集合中包含的元素的数量比较多时，或者有序集合中元素的成员比较长时，redis就会使用跳跃表作为有序集合的底层实现。
跳跃表在单向有序链表的基础上，增加了多级索引以提升查找的效率，这本质上是一个空间换时间的解决方案，索引是占用内存的。在原始的单向有序链表中存储的值有可能是很大的对象，而索引结点值需要存储关键值和相关的几个指针，并不存储值对象，因此当结点本身比较大时，或者元素数量比较多时，跳跃表的优势就会被放大，而缺点可以忽略，这就是redis在特定情形下使用跳跃表的原因。
在redis中，跳跃表是由redis.h/zskiplistNode和redis.h/zskiplist这两个结构体定义的。其中zskiplistNode表示跳跃表的结点，而zskiplist表示跳跃表的相关信息，比如结点数量，执行表头与表尾的指针等。
上图展示了一个跳跃表的示例。图中展示的是最左边的zskiplist结构，以及四个zskiplistNode结点。
zskiplist结构包含的属性主要包括：
-
header：指向跳跃表的表头结点 -
tail：指向跳跃表的表尾结点 -
level：记录当前跳跃表中，层数最大的那个结点的层数（不包括表头节点的层数） -
length：记录跳跃表的长度，即跳跃表中包含的结点的数量（不包括表头结点）
zskiplistNode结构包含的属性主要包括：
-
level：层，结点中使用L1、L2、L3等字样标识结点中的各个层，每个层都带有两个属性，即前进指针与跨度。前进指针用于访问位于表尾方向的其他结点，而跨度记录了前进指针所指向的结点和当前结点的距离。在上图中，连线上带有数字的箭头代表了前进指针，数字就是跨度 -
backward：后退指针，在上图中各个结点使用BW来标识，执行位于当前结点的前一个结点，后退指针可以在程序从表尾向表头遍历时使用 -
score：各个结点中对象的分值，在跳跃表中，结点按照各自所保存的分值从小到大排序，redis有序集合使用分值作为集合元素排序的依据 -
obj：成员对象，即结点中保存的成员对象
在redis源码中，上述结构的定义源码为：
/**
* ZSETs use a specialized version of Skiplists
* 跳跃表中的数据节点
*/
typedef struct zskiplistNode {
sds ele;
double score;
// 后退指针
struct zskiplistNode *backward;
// 层
struct zskiplistLevel {
// 前进指针
struct zskiplistNode *forward;
/**
* 跨度实际上是用来计算元素排名(rank)的，
* 在查找某个节点的过程中，将沿途访过的所有层的跨度累积起来，
* 得到的结果就是目标节点在跳跃表中的排位
*/
unsigned long span;
} level[];
} zskiplistNode;
/**
* 跳跃表结构体
*/
typedef struct zskiplist {
struct zskiplistNode *header, *tail;
unsigned long length;
int level;
} zskiplist;
/**
* 有序集合结构体
*/
typedef struct zset {
/*
* Redis 会将跳跃表中所有的元素和分值组成
* key-value 的形式保存在字典中
* todo：注意：该字典并不是 Redis DB 中的字典，只属于有序集合
*/
dict *dict;
/*
* 底层指向的跳跃表的指针
*/
zskiplist *zsl;
} zset;
