简要介绍
跳表是一种神奇的数据结构，因为几乎所有版本的大学本科教材上都没有跳表这种数据结构，而且神书《算法导论》、《算法第四版》这两本书中也没有介绍跳表。但是跳表插入、删除、查找元素的时间复杂度跟红黑树都是一样量级的，时间复杂度都是O(logn)，而且跳表有一个特性是红黑树无法匹敌的（具体什么特性后面会提到）。所以在工业中，跳表也会经常被用到。
调表被用在 redis 和 leveldb中，相对红黑树而言，跳表非常容易理解，使其成为了红黑树的常见替代。
Redis只在两个地方用到了跳跃表，一个是实现有序集合键(zset)，另一个是在集群节点中用作内部数据结构，除此之外，跳表在Redis里面没有其他用途。
实现原理
跳表是可以实现二分查找的有序链表。
实现原理类似二分查找，在数据量巨大的时候，就能非常快的加速索引。
这是一个递增的单链表，如果需要获取一个其中一个节点，需要从头开始找，时间复杂度为O(n)
如果在这个单链表的基础上，插入一些别的节点来保存，这样能将加速索引
|  |
如果我再加一层，这样能更快的找到目标数据
|  |
跳表性能分析 - 和红黑树相比
为什么 redis 要用跳表，而不是红黑树呢？
什么情况下红黑树效率高？什么情况下跳表性能高？
为什么Redis会用到跳表
因为跳表实现比较简单，简单的逻辑就能让扩展性更强。虽然跳表的性能比起b-tree和红黑树都要差，但这不是redis的性能瓶颈，性能够用就行
为什么有序集合需要同时使用跳跃表和字典来实现? 在理论上,有序集合可以单独使用字典或者跳跃表的其中一种数据结构来实现,但无论单独使用字典还是跳跃表,在性能上对比起同时使用字典和跳跃表都会有所降低。 举个例子,如果我们只使用字典来实现有序集合,那么虽然以O(1)复杂度查找成员的分值这一特性会被保留,但是,因为字典以无序的方式来保存集合元素,所以每次在执行 范围型操作——比如ZRANK、ZRANGE等命令时,程序都需要对字典保存的所有元素进行排序,完成这种排序需要至少O(NlogN)时间复杂度,以及额外的O(N)内存空间(因为要创建一个数组来保存排序后的元素)。
另一方面,如果我们只使用跳跃表来实现有序集合,那么跳跃表执行范围型操作的所有优点都会被保留,但因为没有了字典,所以根据成员查找分值这一操作的复杂度将 从O(1)上升为 O(logN)。因为以上原因,为了让有序集合的查找和范围型操作都尽可能快地执行,Redis 选择了同时使用字典和跳跃表两种数据结构来实现有序集合。
在 redis 源码注释中作者写到
* This skiplist implementation is almost a C translation of the original * algorithm described by William Pugh in "Skip Lists: A Probabilistic * Alternative to Balanced Trees", modified in three ways: * a) this implementation allows for repeated scores. * b) the comparison is not just by key (our 'score') but by satellite data. * c) there is a back pointer, so it's a doubly linked list with the back * pointers being only at "level 1". This allows to traverse the list * from tail to head, useful for ZREVRANGE.作者注释中提到的文章在这里：《Skip Lists:AProbabilistic Alternative to Balanced Trees》
可以看到，redis 中的跳表实现基本就是用C从原论文中的算法翻译过来，只做了以下三点改变：
- 是允许出现重复的
scores - 这里
比较不仅是通过key(redis 中的 key 就是score)，还有实际存储的数据对比 - 支持
后向指针，因此，是一个双端链表
参考
redis zskiplist跳表，性能堪比红黑树？（深度分析）
其他：
跳表介绍的论文：《Skip Lists:AProbabilistic Alternative to Balanced Trees》
