知道跳表（Skip List）是在看关于Redis的书的时候，Redis中的有序集合使用了跳表数据结构。接着就查了一些博客，来学习一下跳表。后面会使用Java代码来简单实现跳表。

什么是跳表

跳表由William Pugh发明，他在论文《Skip lists: a probabilistic alternative to balanced trees》中详细介绍了跳表的数据结构和插入删除等操作，论文是这么介绍跳表的：

Skip lists are a data structure that can be used in place of balanced trees.Skip lists use probabilistic balancing rather than strictly enforced balancing and as a result the algorithms for insertion and deletion in skip lists are much simpler and significantly faster than equivalent algorithms for balanced trees.

也就是说，跳表可以用来替代红黑树，使用概率均衡技术，使得插入、删除操作更简单、更快。先来看论文里的一张图：

观察上图

a：已排好序的链表，查找一个结点最多需要比较N个结点。

b：每隔2个结点增加一个指针，指向该结点间距为2的后续结点，那么查找一个结点最多需要比较ceil(N/2)+1个结点。

c，每隔4个结点增加一个指针，指向该结点间距为4的后续结点，那么查找一个结点最多需要比较ceil(N/4)+1个结点。

若每第2^i 个结点都有一个指向间距为 2^i的后续结点的指针，这样不断增加指针，比较次数会降为log(N)。这样的话，搜索会很快，但插入和删除会很困难。

一个拥有k个指针的结点称为一个k层结点（level k node）。按照上面的逻辑，50%的结点为1层，25%的结点为2层，12.5%的结点为3层…如果每个结点的层数随机选取，但仍服从这样的分布呢（上图e，对比上图d）？

使一个k层结点的第i个指针指向第i层的下一个结点，而不是它后面的第2^(i-1)个结点，那么结点的插入和删除只需要原地修改操作；一个结点的层数，是在它被插入的时候随机选取的，并且永不改变。因为这样的数据结构是基于链表的，并且额外的指针会跳过中间结点，所以作者称之为跳表（Skip Lists）。

二分查找底层依赖数组随机访问的特性，所以只能用数组实现。若数据存储在链表，就没法用二分搜索了？

其实只需稍微改造下链表，就能支持类似“二分”的搜索算法，即跳表（Skip list），支持快速的新增、删除、搜索操作。

Redis中的有序集合（Sorted Set）就是用跳表实现的。我们知道红黑树也能实现快速的插入、删除和查找操作。那Redis 为何不选择红黑树来实现呢？

跳表的意义究竟在于何处？

单链表即使存储的数据有序，若搜索某数据，也只能从头到尾遍历，搜索效率很低，平均时间复杂度是O(n)。

追求极致的程序员就开始想了，那这该如何提高链表结构的搜索效率呢？

若如下图，对链表建立一级“索引”，每两个结点提取一个结点到上一级，把抽出来的那级叫作索引或索引层。图中的down表示down指针，指向下一级结点。

比如要搜索16：

• 先遍历索引层，当遍历到索引层的13时，发现下一个结点是17，说明目标结点位于这俩结点中间
• 然后通过down指针，下降到原始链表层，继续遍历
  此时只需再遍历2个结点，即可找到16！

原先单链表结构需遍历10个结点，现在只需遍历7个结点即可。可见，加一层索引，所需遍历的结点个数就减少了，搜索效率提升。

若再加层索引，搜索效率是不是更高？于是每两个结点再抽出一个结点到第二级索引。现在搜索16，只需遍历6个结点了！

这里数据量不大，可能你也没感觉到搜索效率ROI高吗。

那数据量就变大一点，现有一64结点链表，给它建立五级的索引。

原来没有索引时，单链表搜索62需遍历62个结点！

现在呢？只需遍历11个！所以你现在能体会到了，当链表长度n很大时，建立索引后，搜索性能显著提升。

这种有多级索引的，可以提高查询效率的链表就是最近火遍面试圈的跳表。

作为严谨的程序员，我们又开始好奇了