跳跃表
跳跃表是一种有序数据结构，它通过在每个节点中维持多个指向其他节点的指针，从而达到快速访问的目的。跳跃表支持平均O(logN)和最坏O(N^2)复杂度的节点查找，还可以通过顺序性操作来批量处理节点。效率可以和平衡树媲美。
跳跃表的实现
redis中用zskiplistNode表示跳跃表节点，而zskiplist结构用于保存跳跃表相关信息。结构如下所示：
typedef struct zskiplist {
//表头节点和表尾节点
struct zskiplistNode *header,*tail;
//表中节点数量
unsigned long length;
//表中层数最大的节点的层数
int level;
}
跳跃表
- [ ] header：指向跳跃表的表头节点。
- [ ] tail：指向跳跃表的表尾节点。
- [ ] level：记录目前跳跃表内，层数最大的那个节点的层数（不包括表头节点）。
- [ ] length：记录跳跃表的长度，即，跳跃表目前包含节点的数量（不计算表头节点）。
节点
跳跃表节点的结构定义如下
typedef struct zskiplistNode {
// 后退指针
struct askiplistNode *backward;
//分值
double score;
//成员对象
robj *obj;
//层
struct zskiplistLevel {
//前进指针
struct askiplistNode *forward;
//跨度
unsigned int span;
}level[];
}zskiplistNode;
- 层： 用L1，L2等标记的各个层，每个层都有两个属性：前进指针和跨度，前进指针用于访问其他节点，跨度则记录了当前前进指针所指向的节点和当前节点的距离。
- 后退指针： 它指向当前节点的前一个节点。
- 分值： 在跳跃表中，节点按照保存的分值从小到大排列。
- 成员对象： 保存的成员对象。
表头节点和其他节点是一样的，知识后退指针，分值和成员对象不会应用到，所以省略了。
指向NULL的所有前进指针的跨度都为0；
在同一个跳跃表中，各个节点保存的程艳对象必须是唯一的，但多个节点保存的分值可以是相同的。节点的成员对象obj是一个指针，它指向一个字符串对象，而字符串对象则保存了一个SDS值。
每个跳跃表节点的层高都是1~32之间的随机数。
跳跃表中的节点按照分值大小进行排序，当分值相同时，节点按照成员对象的大小进行排序。
跳跃表API
| 函数 | 作用 | 时间复杂度 |
|---|---|---|
| zslCreate | 创建一个新的跳跃表 | O(1) |
| zslFree | 释放给定跳跃表，以及表中的节点 | O(N),N为跳跃表长度 |
| zslInsert | 将包含给定成员和分值的新节点调价到跳跃表中 | 平均logN，最坏N^2 |
| zslDelete | 删除跳跃表中包含给定成员和分值的节点 | 平均logN，最坏N^2 |
| zslGetRank | 返回包含给定成员和分值的节点在跳跃表中的排位 | 平均logN，最坏N^2 |
| zslGetElementByRank | 返回跳跃表在给定排位上的节点 | 平均logN，最坏N^2 |
| zslIsRange | 给定一个范围，如果给定的范围包含在跳跃表的分值返回内返回1，否则返回0 | O(1) |
| zslFirstInRange | 给定一个分值范围，返回跳跃表中第一个符合这个返回的节点 | 平均logN，最坏N^2 |
| zslLastInRange | 给定一个分值范围，返回跳跃表中最后一个符合这个范围的节点 | 平均logN，最坏N^2 |
| zslDeleteRangeByScore | 给定一个分值范围，删除跳跃表中所有在这个范围之内的节点 | O(N)，N为被删除的节点数量 |
| zslDeleteRangeByRank | 给定一个排位范围，删除跳跃表中所有在这个范围内的节点 | O(N)，N为被删除的节点数量 |
