目录
为什么需要 SkipList（跳表）
在普通链表中查找元素的时候，因为需要遍历查找，所以查询效率非常低，时间复杂度是O(N)。
因此我们需要跳表。跳表是在链表基础上改进过来的，实现了一种 “多层” 的 有序 链表，这样的好处是能快速定位数据。
跳表的结构设计
如下图所示，这是一个层级为3的跳表
和普通的双向链表一样，SkipList 都有一个指向上一个节点的指针，也有一个指向下一个节点的指针。
但是你会发现，在层次为 3 的跳表中，会有三级指针的存在，而且 SkipList 中元素会按照 score 值升序排序（score 值一样则按照 ele 排序）
- 一级指针普通链表一样，指向下一个节点（图中的 L0）
- 二级指针跨度为2，指向的节点与自己间隔了一个节点
- 三级指针跨度为3，指向的节点与自己间隔了两个节点
这样的设计会带来什么好处呢？
- 假设我们要在普通链表中查询值为 3 的节点，我们需要从头结点开始，向后遍历1 → 2 → 3 ，三个节点才能找到。时间复杂度为 O(n)
- 当使用了 SkipList 这个数据结构之后，我们可以直接通过三级指针（L2），直接找到这个节点（建立在元素有序的情况下，类似于二分查找一步一步缩小范围）。时间复杂度为 O(logN)
跳表的节点（zskiplistNode ）
我们来看看跳表的结构体源码
typedef struct zskiplistNode {
sds ele;
double score;
struct zskiplistNode *backward;
struct zskiplistLevel {
struct zskiplistNode *forward;
unsigned long span;
} level[];
} zskiplistNode;
其中，
- ele，用于存储该节点的元素
- score，用于存储节点的分数（节点按照 score 值排序，score 值一样则按照 ele 排序）
- *backward，指向上一个节点
而 level[] 就是实现跳表多层次指针的关键所在，level 数组中的每一个元素代表跳表的一层，比如 leve[0] 就表示第一层，leve[1] 就表示第二层。zskiplistLevel 结构体里定义了指向下一个跳表节点的指针** *forward 和用来记录两个节点之间的距离 span，如图所示，
