redis-跳跃表zskiplist
跳跃表结构介绍
跳跃表是在有序链表的基础上实现的一种数据结构。先看一下有序链表的结构：
如图所示的有序链表，如果要查询值为51的元素，需要从链表头开始依次查找，查找的效率是O(n)。有序链表的插入和删除都需要先找到合适的位置再修改next指针，修改操作基本不耗时，所以有序链表的插入、删除操作时间消耗主要在元素的查找上。跳表就是在此基础上实现的一种优化方案。
如果我们将有序链表的部分节点分层，每一层的元素个数逐渐减少，并且每一层都是一个有序链表。在查找时优先从最高层开始向后查找，在到达某节点时，如果next节点值大于要查找的值或者next的值指向NULL,则从当前节点下降一层继续向后查找，这样就会提升查找效率。
图1：分层有序链表
假如我们还是查找值为51的节点，按照上述规则，则查找的思路如下：
图2
1) 从第2层开始，1节点比51节点小，向后比较。
2) 21节点比51节点小，继续向后比较。第2层21节点的next指针指向NULL，所以从21节点开始需要下降一层到第1层继续向后比较。
3) 第1层中，21节点的next节点为41节点，41节点比51节点小，继续向后比较。第1层41节点的next节点为61节点，比要查找的51节点大，所以从41节点开始下降一层到第0层继续向后比较。
4) 在第0层，51节点为要查询的节点，节点被找到。
采用图2所示的数据结构后，总共查找4次就可以找到51节点，比有序链表少2次。当数据量大时，优势会更明显。
综上所述，通过将有序集合的部分节点分层，由最上层开始依次向后查找，如果本层的next节点大于要查找的值或next节点为NULL，则从本节点开始，降低一层继续向后查找，依次类推，如果找到则返回节点;否则返回NULL。采用该原理查找节点，在节点数量比较多时，可以跳过一些节点，查询效率大大提升，这就是跳跃表的基本思想。
跳跃表的性质
跳表节点与结构
由以上分析我们知道，跳跃表由多个节点构成，每个节点由很多层构成，每层都有指向本层下个节点的指针。那么，Redis中 的跳跃表是如何实现的呢?
我们看下跳跃表节点的zskiplistNode结构体。redis6.0代码在server.h中定义
typedef struct zskiplistNode {
sds ele;
double score;
struct zskiplistNode *backward;
struct zskiplistLevel {
struct zskiplistNode *forward;
unsigned long span;
} level[];
} zskiplistNode;
typedef struct zskiplist {
struct zskiplistNode *header, *tail;
unsigned long length;
int level;
} zskiplist;