跳跃表（skiplist）是一种有序数据结构，通过在每个节点中维持多个指向其他节点的指针，从而达到快速访问节点的目标
跳跃表支持O（logN），O（N）复杂度的节点查找，还可以通过顺序性的操作来大量处理节点，跳跃表的效率可以和平衡树进行相媲美
Redis使用跳跃表作为有序集合键的底层实现之一，如果一个有序集合中包含的元素比较多，或者有序集合中的元素的成员是比较长的字符串的时候，Redis就会使用跳跃表作为有序集合键的底层实现
Redis中使用跳跃表：
- 实现有序集合
- 集群节点中用作内部数据结构
跳跃表实现
zskiplistNode结构用于表示跳跃表节点
zskiplist结构用于表示跳跃表节点相关信息
header:指向跳跃表的表头节点
tail:指向跳跃表的表尾节点
level:记录目前跳跃表内，层数最大的那个节点的层数（表头节点的层数不计算在内）
length:记录跳跃表的长度，就是节点的个数（表头节点不计算在内）
level(层):L1，L2，L3，表示每个节点的各个层，每层有两个属性：前进指针和跨度，前进指针用于表示位于表尾方向的其他节点，跨度记录了前进指针所指向节点和当前节点的距离，上图，箭头表示前进指针，数字表示跨度，当程序从表头向表尾遍历的时候，访问会沿着层的前进指针进行
backward(后退指针):BW表示节点的后退指针，指向位于当前节点的前一个节点，后退指针在程序从表尾向表头遍历的时候使用
score(分值):1.0,2.0,3.0表示节点所保存的分值，跳跃表中按分值大小从小到大排序
obj(成员对象):O1,O2,O3就是节点所保存的成员对象
表头节点也有后退指针，分值，成员对象，不过表头节点的这些属性用不到，省略了，只显示了表头节点的各个层
跳跃表节点
typedef struct zskiplistNode{
//层
struct zskiplistLevel{
//前进指针
struct zskiplistNode *forward;
//跨度
unsigned int span;
}level[];
//后退指针
struct zskiplistNode *backward;
//分值
double score;
//成员对象
robj *obj;
}zskiplistNode;
层（level）:程序通过这些层可以加快访问其他节点的速度，一般，层的数量越多，访问其他节点的速度越快
创建一个新节点的时候，程序根据幂次定律随机生成一个1到32之间的数作为level数组的大小
前进指针：用于从表头向表尾方向访问节点，可以用来遍历跳跃表中所有节点
跨度：用于记录两个节点之间的距离
- 两个节点跨度越大，离得越远
- 指向NULL的所有前进指针的跨度为0
跨度和遍历操作无关，是用来计算排位的
排位：在查找某个节点的过程中，将沿途访问过的所有层的跨度累加起来，得到的结果就是目标节点在跳跃表中的排位
后退指针：用于从表尾向表头方向访问节点，每次只能后退到前一个节点
分值和成员：所有节点都按分值从小到大排序，obj是一个指针，指向一个字符串对象，字符串对象保存一个SDS值，各个节点保存的成员对象必须唯一，但多个节点的分值可以相同，相同分值的，按obj在字典中的排序，从小到大排序
跳跃表
通过使用一个zskiplist来维持这些节点，程序可以更方便的对整个跳跃表进行处理，快速访问表头节点和表尾节点，快速获取跳跃表节点的数量
typedef struct zskiplsit{
//表头节点和表尾节点
struct zskiplistNode *header,*tail;
//节点数量
unsigned long length;
//层数最大节点的层数
int level;
}zskiplist;
跳跃表API
| 函数 | 作用 | 时间复杂度 |
|---|---|---|
| zslCreate | 创建一个 新的跳跃表 | O（1） |
| zslFree | 释放给定跳跃表，以及表中包含的所有节点 | O（N），N是跳跃表长度 |
| zslInsert | 将包含给定成员和分值的新节点添加到跳跃表中 | O（logN），最坏O（N），N为表长 |
| zslDelete | 删除跳跃表中包含给定成员和分值的节点 | O（logN），最坏为O（N） |
| zslGetRank | 返回包含给定成员和分值的节点在跳跃表中的排位 | O（logN），最坏O（N） |
| zslGetElementByRank | 返回跳跃表在给定排位上的节点 | O（logN），最最坏O（N） |
| zslIsInRange | 给定一个分值范围，如果跳跃表中有至少一个节点的分值在这个范围之内，返回1，否则返回0 | 通过表头和表尾节点可以检测O（1） |
| zslFirstInRange | 给定一个分值范围，返回跳跃表中第一个符合这个范围的节点 | O（logN），最坏O（N） |
| zslLastInRange | 给定一个分值范围，返回跳跃表中最后一个符合这个范围的节点 | O（logN），最坏O（N） |
| zalDeleteRangeByScore | 给定一个分值范围，删除 跳跃表中所有在这个范围内的节点 | O（N），N是删除节点的数量 |
| zslDeleteRangeByRank | 给定一个排位范围，删除所有在这个范围内的节点 | O（N） |
