先让我们看一个问题：如果要存一组有序的 int 型数据集合，我们可以如何实现？
- 数组
可能大多数同学最先想到的是用数据实现，将有序的数据集合存放在数据中，可以使用二分法进行查找，效率比较高，但是对于新增和删除的操作并不友好，因为这些操作都需要移动后面位置的元素。
- 链表
那么有没有什么数据结构可以让查询、新增、删除操作都变得很快呢？这就是我们今天要介绍的跳跃表了，让我们看几张图，很容易理解。
跳跃表
如上图，一个有序的链表，如果要找值为 50 的节点，需要从第一个节点开始遍历，查询最后才能找到值为 50 的节点。
我们给这个链表加一层索引，如图：
我们按照一级索引来查询（橙色查询路线），可以发现我们至少可以少遍历一半的节点。
还觉得有些慢？，那么再增加一层，再加一层，如图：
是不是更快地找到我们需要的节点了，当然这里的节点数量不够多，如果节点数量非常多，查找效率提升会更加明显。
如果需要找中间的某个节点，比如寻找 42 ，过程大概是这样的：
插入节点
看懂了跳跃表的数据结构，那么就很容易理解节点的插入操作了，基本上两步操作就可以实现：在最底层的数据链表中插入数据，然后调整索引；
其中每一层的索引链表中是否需要增加新增的节点，其实并没有什么标准答案，我们尽量做到索引的平均分布即可，常用的就是【随机判断】决定是否需要新增或调整索引，当有新节点插入的时候，通过概率算法判断这个节点需要插入到几级节点中。
比如：
底层数据链表有 N 个元素，随机选择 N/2 个元素作为 1 级索引，随机选择 N/4 个元素作为 2 级索引...一直到顶层索引；
新插入数据节点，1/2 概率不插入任何一级索引，1/4 概率返回需要插入 1 级索引，1/8 概率返回需要插入到 2 级索引，以此类推；
这里要注意一点，插入 2 级索引的时候，同时也需要插入 1 级索引；也就是插入 n 级索引的时候，同时也要插入 1~( n-1 ) 级索引。
删除节点
跳跃表删除节点就更简单了，删除数据节点，并删除每一层的索引节点（如果有的话）。
总结来说：
可以把跳跃表看成多个有序链表（最底层的数据链表+多层索引链表）；
查找的过程中，从最长层开始查找，找到对应的区间再到下一层查找 ；
每个节点都有两个指针，分别指向右边和下边；
插入新节点时，随机判断该节点是否要插入索引，最高插入几级索引；
插入 n 级索引的时候，同时也要插入 1~(n-1) 级索引；
跳跃表和红黑树等平衡树相比，更容易实现，并且不需要维护平衡性；
Redis 中的 ZSet 的一种实现方式是 skipList 与 hashTable 的结合；
Google 的 LevelDB 、Facebook 的 RocksDB ，它们都是使用了跳跃表这种数据结构。
会点代码的大叔 | 文【原创】
