我们先不谈Redis，来看一下跳表。
1.1、业务场景场景来自小灰的算法之旅，我们需要做一个拍卖行系统，用来查阅和出售游戏中的道具，类似于魔兽世界中的拍卖行那样，还有以下需求：
拍卖行拍卖的商品需要支持四种排序方式，分别是：按价格、按等级、按剩余时间、按出售者ID排序，排序查询要尽可能地快。
还要支持输入道具名称的精确查询和不输入名称的全量查询。
这样的业务场景所需要的数据结构该如何设计呢？拍卖行商品列表是线性的，最容易表达线性结构的是数组和链表。假如用有序数组，虽然查找的时候可以使用二分法（时间复杂度O(logN)），但是插入的时间复杂度是O(N)，总体时间复杂度是O(N)；而如果要使用有序链表，虽然插入的时间复杂度是O(1)，但是查找的时间复杂度是O(N)，总体还是O(N)。
那有没有一种数据结构，查找时，有二分法的效率，插入时有链表的简单呢？有的，就是 跳表。
1.2、skiplistskiplist，即跳表，又称跳跃表，也是一种数据结构，用于解决算法问题中的查找问题。
一般问题中的查找分为两大类，一种是基于各种平衡术，时间复杂度为O(logN)，一种是基于哈希表，时间复杂度O(1)。但是skiplist比较特殊，没有在这里面
2、跳表 2.1、跳表简介跳表也是链表的一种，是在链表的基础上发展出来的，我们都知道，链表的插入和删除只需要改动指针就行了，时间复杂度是O(1)，但是插入和删除必然伴随着查找，而查找需要从头/尾遍历，时间复杂度为O(N)，如下图所示是一个有序链表（最左侧的灰色表示一个空的头节点）（图片来自网络，以下同）：
链表中，每个节点都指向下一个节点，想要访问下下个节点，必然要经过下个节点，即无法跳过节点访问，假设，现在要查找22，我们要先后查找 3->7->11->19->22，需要五次查找。
但是如果我们能够实现跳过一些节点访问，就可以提高查找效率了，所以对链表进行一些修改，如下图：
我们每个一个节点，都会保存指向下下个节点的指针，这样我们就能跳过某个节点进行访问，这样，我们其实是构造了两个链表，新的链表之后原来链表的一半。
我们姑且称原链表为第一层，新链表为第二层，第二层是在第一层的基础上隔一个取一个。假设，现在还是要查找22，我们先从第二层查找，从7开始，7小于22，再往后，19小于22，再往后，26大于22，所以从节点19转到第一层，找到了22，先后查找 7->19->26->22，只需要四次查找。
以此类推，如果再提取一层链表，查找效率岂不是更高，如下图：
现在，又多了第三层链表，第三层是在第二层的基础上隔一个取一个，假设现在还是要查找22，我们先从第三层开始查找，从19开始，19小于22，再往后，发现是空的，则转到第二层，19后面的26大于22，转到第一层，19后面的就是22，先后查找 19->26>22，只需要三次查找。
由上例可见，在查找时，跳过多个节点，可以大大提高查找效率，skiplist 就是基于此原理。
上面的例子中，每一层的节点个数都是下一层的一半，这种查找的过程有点类似二分法，查找的时间复杂度是O(logN)，但是例子中的多层链表有一个致命的缺陷，就是一旦有节点插入或者删除，就会破坏这种上下层链表节点个数是2:1的结构，如果想要继续维持，则需要在插入或者删除节点之后，对后面的所有节点进行一次重新调整，这样一来，插入/删除的时间复杂度就变成了O(N)。
2.2、跳表层级之间的关系如上所述，跳表为了解决插入和删除节点时造成的后续节点重新调整的问题，引入了随机层数的做法。相邻层数之间的节点个数不再是严格的2:1的结构，而是为每个新插入的节点赋予一个随机的层数。下图展示了如何通过一步步的插入操作从而形成一个跳表：