REDIS_SKIPLIST
skipList，即：跳表，或者叫跳跃表。skiplist的优势是能支持平均 O(logN) 复杂度的节点查找。
用一句话来说：skiplist就是一个有着索引的list。
编码结构
简单理解
简单来说，skipList有多层“索引”以加快查找速度：
其中L1、L2和L3都是一个list。
当查找8时，从L3查找到5，再从L2从5开始查找，查找到7，再L3中从7开始查找，最终查找到8。
这样，原本需要8次查找的操作直接简化到了4次。
从源码理解
typedef struct zskiplist {
struct zskiplistNode *header, *tail;
unsigned long length;
int level;
} zskiplist;
typedef struct zskiplistNode {
sds ele;
double score;
struct zskiplistNode *backward;
struct zskiplistLevel {
struct zskiplistNode *forward;
unsigned long span;
} level[];
} zskiplistNode;
Redis 只有 Zset 对象的底层实现用到了跳表。
Zset 需要你填入元素和权重，其中权重就是跳表用于排序的根源，即listNode中的score。
zskipList中的level即为跳表的层级， Zset的元素存储在listNode中的ele中，以sds形式存储。
SkipList的层级设计
前文提到，SkipList相邻两层的节点数量的比例会影响跳表的查询性能。
当设计不合理时，跳表的查询性能可能会降低到 O(n)。
**跳表的相邻两层的节点数量最理想的比例是 2:1，查找复杂度可以降低到 O(logN)**。
但Redis所提出的解决方案是：跳表在创建节点的时候，随机生成每个节点的层数，并没有严格维持相邻两层的节点数量比例为 2 : 1 的情况。
skipList在创建节点时候，会生成范围为[0-1]的一个随机数，如果这个随机数小于 0.25（相当于概率 25%），那么层数就增加 1 层，然后继续生成下一个随机数，直到随机数的结果大于 0.25 结束，最终确定该节点的层数。
// 创建一个空表头的跳表
zskiplist *zslCreate(void) {
int j;
zskiplist *zsl;
// 尝试分配内存空间
zsl = zmalloc(sizeof(*zsl));
// 初始化level和length
zsl->level = 1;
zsl->length = 0;
// 调用下面的方法zslCreateNode, 传入的参数有数组长度。
// 分数0，对象值NuLL
// 这一步就是创建管理所有节点的数组
// 并且设置表头的头头指针为此对象的地址
zsl->header = zslCreateNode(ZSKIPLIST_MAXLEVEL,0,NULL);
// 为这32个数组赋值前指针forward和跨度span
for (j = 0; j < ZSKIPLIST_MAXLEVEL; j++) {
zsl->header->level[j].forward = NULL;
zsl->header->level[j].span = 0;
}
// 设置尾指针
zsl->header->backward = NULL;
zsl->tail = NULL;
// 返回对象
return zsl;
}
zskiplistNode *zslCreateNode(int level, double score, sds ele) {
zskiplistNode *zn =
zmalloc(sizeof(*zn)+level*sizeof(struct zskiplistLevel));
zn->score = score;
zn->ele = ele;
return zn;
}
ZSKIPLIST_MAXLEVEL 定义的是最高的层数，Redis 7.0 定义为 32，Redis 5.0 定义为 64，Redis 3.0 定义为 32。
为什么要用跳表而不用平衡树？
对于这个问题，Redis作者@antirez如是回答：
There are a few reasons:
- They are not very memory intensive. It's up to you basically. Changing parameters about the probability of a node to have a given number of levels will make then less memory intensive than btrees.
- A sorted set is often target of many ZRANGE or ZREVRANGE operations, that is, traversing the skip list as a linked list. With this operation the cache locality of skip lists is at least as good as with other kind of balanced trees.
- They are simpler to implement, debug, and so forth. For instance thanks to the skip list simplicity I received a patch (already in Redis master) with augmented skip lists implementing ZRANK in O(log(N)). It required little changes to the code. 简单来说：
1.Btree和SkipList不是内存密集型数据模型，用什么取决于你，只不过改变节点级数的时候SkipList可以比树用更少的内存。
2.Redis经常需要执行ZRANGE或ZREVRANGE命令，即作为链表遍历跳表。通过此操作，跳表的缓存局部性至少与其他类型的平衡树一样好。
3.SkipList实现简单，社区维护起来方便。比如社区提交来一个用O(logN)的ZRANK实现，只需要改动少量代码就能完成。
详细来说：
- 从内存占用上来比较，跳表比平衡树更灵活。平衡树每个Node固定包含 2 个指针（指向左右子树），而跳表每个节点包含的指针数目平均为 1/(1-p)，具体取决于参数 p 的大小。如果像 Redis里的实现一样，取 p=1/4，那么平均每个节点包含 1.33 个指针，比树占用的内存更少。
- 在做范围查找的时候，跳表比平衡树操作要简单。在平衡树上，我们找到指定范围的小值之后，还需要以中序遍历的顺序继续寻找其它不超过大值的节点。如果不对树进行改造，中序遍历并不容易实现。而在跳表上进行范围查找就非常简单，只需要在找到小值之后，对第 1 层链表进行遍历就可以实现。
- 从算法实现难度上来比较，跳表比平衡树要简单得多。平衡树的插入和删除操作可能引发子树的调整，逻辑复杂，而跳表的插入和删除只需要修改相邻节点的指针，操作简单快速。