SkipList
超高性能的数据库redis和levelDB都用到了这种神奇的数据结构:SkipList(跳跃表)。之所以说它神奇，是因为跳跃表是基于一个随机数的。跳跃表是在有序链表的基础上进行了扩展，解决了有序链表结构查找特定值困难的问题(O(logn))，是一种可以替代平衡二叉树的数据结构(查询的时间二者基本相同，但是插入的时间跳跃表优于平衡二叉树)。
相比于各种平衡二叉树，跳跃表的实现比较简单。
有序表的搜索
从这个链表中 寻找23，找2次 寻找43，找4次 寻找59，找6次
怎么优化？链表当然不能二分查找，但可以把一些节点提取出来作为索引，得到下面的结构
把14 24 50 72 提取出来作为一级索引，这样的搜索的时候就可以减少比较次数了。还可以提取出来一个二级索引，变成如下的结构
我们可以看出，这是一种类似树状数组思想的分层链表结构。
跳跃列表
下面的结构就是跳表 其中-1表示INTMIN 链表的最小值 1表示INTMAX链表的最大值。
跳表具有下面的性质 ①由很多层结构组成 ②每一层都是一个有序的列表 ③最底层(Level 1)的链表包含所有元素 ④如果一个元素出现在Level i的链表中，则它在Level i之下的链表中也都会出现 ⑤每个节点包含两个指针，一个指向同一链表中的下一个元素，一个指向下面一层的元素
跳表的搜索
从最高层开始找，如果发现下一个元素小于搜索值，那么继续往本层的后一个找。如果发现下一个元素大于搜索值，那么就往当前的下一层找。如果等于 = = 正好。
代码
/*如果存在x 返回x所在的节点 *否则返回x的后继节点*/find(x){p = top;while(true) {while(p->next->key < x) p = p->next;if(p->down == NULL) return p->next;p = p->down;}}跳表的插入
先确定该元素要占据的层数K(这是一个随机数) 然后再Level 1…k 各个层的链表都插入元素
比如K(119) = 2的情况
比如插入119，K=4
“丢硬币”决定K
插入元素的时候，元素所占有的层数完全是随机的，通过以下的随机算法产生：
int random_level(){k = 1;while(random(0,1)) k ++;return k;}
相当于做一次丢硬币的实验，如果正面则继续丢，遇到反面则停止。 用试验中丢硬币的次数K作为元素占有的层数。显然随机变量K满足参数为p=1/2的几何分布。 K的期望值E[K]=1/p=2 就是说，各个元素的层数期望值是2层。
跳表的高度
n个元素的跳表，每个元素插入的时候都要做一次实验，，用来决定元素占据的层数K. 跳表的高度等于这N次实验中产生的最大K。
跳表的空间复杂度
每个元素的期望高度为2，一个大小为n的跳表，其节点数目的期望值是2n
跳表的删除
在每个层中找到包含x的节点，使用标准的delete form list方法删除该节点
比如，删除 71
上帝从不埋怨人们的愚昧，人们却埋怨上帝的不公平
