Redis 只在两个地方用到了跳跃表，一个是实现有序集合键，另一个是在集群节点中用作内部数据结构。
之前在学习数据结构的时候有接触到跳跃表，看图：
跳表.png
跳表有点像二分法，链表的二分法，Redis 中的跳表使用双向链表实现
node of skiplist
typedef struct zskiplistNode{
// 后退指针
struct zskiplistNode *backward;
// 分值
double score;
// 成员对象
robj *obj;
// 层
struct zskiplistLevel {
// 前进指针
struct zskiplistNode *forward;
// 跨度
unsigned int span;
} level[];
} zskiplistNode;
level
每次创建一个新跳表节点时，程序都会根据幂次定律（power law，越大的数出现的概率越小）随机生成一个介于 1 和 32 之间的值作为 level 数组的大小，这个大小就是层的“高度”。
forward
遍历跳表中所有节点的方式：从 header 节点开始，再从当前节点的最高层向下，当遇到第一个跨度为 1 的层后，遍历下一个节点。伪代码如下：
void reverseSkiplistNode(zskiplistNode *header) {
while(header != null) {
printf(header.obj);
int height = header.level.length;
for (int i = height - 1; i > 0 ; i ++){
if (header.level[i].span == 1) {
header = header.level[i].forward;
break;
}
}
}
}
span
跨度是用来计算排位（rank）的：在查找某个节点的过程中，将沿途访问过的所有层的跨度累计起来，得到的结果就是目标节点在跳表中的排位。
score & obj
节点的分值是一个 double 类型的浮点数，跳表中的所有节点都按分值从小到大来排序。
节点的成员对象是一个指针，它指向一个字符串对象，而字符串对象则保存着一个 SDS 值。
在同一个跳表中，各个节点保存的成员对象必须是唯一的，但是多个节点保存的分值却可以是相同的：分支相同的节点将按照成员对象在字典序中的大小来进行排序，成员对象较小的节点会排在前面，而成员对象较大的节点则会排在后面。看图：
有序集合.png
zskiplist
typedef struct zskiplist {
// 表头、尾节点
structz skiplistNode *header, *tail;
// 表中节点的数量
unsigned long length;
// 表中最大的层数
int level;
} zskiplist;
level 属性用于在 O(1) 复杂度内获取跳表中最大的层数，注意表头节点的层高并不计算在内。
