跳表介绍
目前经常使用的平衡数据结构有：B树，红黑树，AVL树，Splay Tree, Treep等。
跳表是一种随机化的数据结构，目前开源软件Redis和LevelDB都有用到它，它的效率和红黑树以及AVL树不相上下，但跳表的原理相当简单，只要你能熟练操作链表，就能轻松实现一个 SkipList。
这是跳表的作者，上面介绍的William Pugh给出的解释。
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.
跳表是平衡树的一种替代的数据结构，但是和红黑树不相同的是，跳表对于树的平衡的实现是基于一种随机化的算法的，这样也就是说跳表的插入和删除的工作是比较简单的。
跳表核心思想
从该有序表中搜索元素“23,43,59”，需要比较的次数分别为<2, 4, 6>，总共比较的次数为2 + 4 + 6 = 12次。有没有优化的算法吗? 链表是有序的，但不能使用二分查找。类似二叉搜索树，把一些节点提取出来，作为索引。得到如下结构。
把“14,34,50,72”提取出来作为一级索引，这样搜索的时候就可以减少比较次数了。还可以再从一级索引提取一些元素出来，作为二级索引，变成如下结构。
如果是说链表是排序的，并且节点中还存储指向前面第二个节点的指针的话，那么在查找一个节点时，仅仅需要遍历N/2个节点即可。
这基本上就是跳表的核心思想，其实也是一种通过“空间来换取时间”的一个算法，通过在每个节点中增加了向前的指针，从而提升查找的效率。