1. 什么是跳表(skip list)

跳表是由William Pugh发明。他在 Communications of the ACM June 1990, 33(6) 668-676 发表了Skip lists: a probabilistic alternative to balanced trees，在该论文中详细解释了跳表的数据结构和插入删除操作。

跳表全称为跳跃列表，可以快速查询，插入和删除一个有序连续元素的数据链表。

跳表在查找、插入平均时间复杂度是O(logn)，速度很快。我们知道链表的查找的时间复杂度是O(logn)效率较低，而跳表则解决了此问题。

那么跳表是怎么解决的呢？

有序链表需要从头遍历，在链表上建立多层索引，可以通过先查找索引然后确定元素的范围，最后小范围的遍历找到元素。

跳表的空间复杂度O(n)，跳表是以空间换时间的思路。向上每级有n/2个节点，依次，最后上层有2个节点。

如下图所示：

2. 跳表索引维护

通过前面的讲解，我们知道了跳表如何查找。那么往跳表插入数据，我们该如何维护索引呢？

首先，最底层的链表的插入和链表的插入没有区别，这个就不多讲了。

当我们不断插入链表的数据时候，如果不维护索引，那么两个索引之间有可能聚集大量的数据，跳表的查询效率会降低。在极端的情况下，跳表会退化成单链表。

所以，我们需要用一种方法，来动态更新索引。

红黑树和AVL树都是平衡二叉树，树的大小平衡是通过左旋和右旋的方式来维护。跳表一般通过i 个随机函数的方式来维护索引的平衡性。

当往跳表中插入数据时，通过随机函数生成一个随机值N，那么把该索引添加到从第1级到N级的索引中。从概率学上讲，跳表就不至于性能过度退化，这样就可以使索引平衡了。

但是，随机函数该如何选择呢？这个读者可以自己研究，这里不做讲解了。

3. 跳表的应用

通过前面的讲解，我们知道跳表的优势是查找速速快，且修改的效率高。所以，跳表的应用很广泛，下面我们来举例。

Redis的有序集合（zset）就是通过跳表实现的，支持插入、删除、查找、有序输出所有元素、按照范围检索。

那么Redis 的有序集合为什么不用红黑树实现呢？

因为红黑树在按照范围查找的效率没有跳表的效率高，跳表按照范围查好可以达到O(logn)。