跳跃表
跳表(Skip List)是一种随机化的数据结构，插入、删除、查找的复杂度均为O(logN)
简单说来跳表也是链表的一种，只不过它在链表的基础上增加了跳跃功能，正是这个跳跃的功能，使得在查找元素时，跳表能够提供O(logN)的时间复杂度
基本性质
1.由很多层结构组成
2.每一层都是一个有序的链表
3.最底层(Level 1)的链表包含所有元素
4.如果一个元素出现在 Level i 的链表中，则它在 Level i 之下的链表也都会出现
5.每个节点包含两个指针，一个指向同一链表中的下一个元素，一个指向下面一层的元素
跳表最底层是一个全量的有序链表，跳表是可以实现二分查找的有序链表
如下图所示，查找路径：1、7、9、10，找 10 的效率更高了，这就是跳表的思想，用“空间换时间”，通过给链表建立索引，提高了查找的效率
插入节点
插入操作了，基本上两步操作就可以实现：在最底层的数据链表中插入数据，然后调整索引
其中每一层的索引链表中是否需要增加新增的节点，其实并没有什么标准答案，我们尽量做到索引的平均分布即可，常用的就是随机判断决定是否需要新增或调整索引，当有新节点插入的时候，通过概率算法判断这个节点需要插入到几级节点中
比如：
底层数据链表有 N 个元素，随机选择 N/2 个元素作为 1 级索引，随机选择 N/4 个元素作为 2 级索引…一直到顶层索引
新插入数据节点，1/2 概率不插入任何一级索引，1/4 概率返回需要插入 1 级索引，1/8 概率返回需要插入到 2 级索引，以此类推
这里要注意一点，插入 2 级索引的时候，同时也需要插入 1 级索引；也就是插入 n 级索引的时候，同时也要插入 1~( n-1 ) 级索引
时间复杂度
查找元素的过程是从最高级索引开始，一层一层遍历最后下沉到原始链表，所以，时间复杂度 = 索引的高度 * 每层索引遍历元素的个数
先来求跳表的索引高度
假设每两个结点会抽出一个结点作为上一级索引的结点，原始的链表有n个元素，则一级索引有n/2 个元素、二级索引有 n/4 个元素、k级索引就有 n/2k个元素，最高级索引一般有2个元素，所以 h = log2n - 1，最高级索引 h 为索引层的高度加上原始数据一层，跳表的总高度 h = log2n
当每级索引都是两个结点抽出一个结点作为上一级索引的结点时，每一层最多遍历3个结点
跳表的索引高度 h = log2n，且每层索引最多遍历 3 个元素，所以跳表中查找一个元素的时间复杂度为 O(3*logn)，省略常数即：O(logn)
空间复杂度
跳表通过建立索引，来提高查找元素的效率，就是典型的“空间换时间”的思想
假如原始链表包含 n 个元素，则一级索引元素个数为 n/2、二级索引元素个数为 n/4、三级索引元素个数为 n/8 以此类推，所以，索引节点的总和是：n/2 + n/4 + n/8 + … + 8 + 4 + 2 = n-2，空间复杂度是 O(n)
和平衡树、哈希表比较
哈希表不是有序的，因此，在哈希表上只能做单个key的查找，不适宜做范围查找，所谓范围查找，指的是查找那些大小在指定的两个值之间的所有节点
在做范围查找的时候，平衡树比SkipList操作要复杂，在平衡树上，我们找到指定范围的小值之后，还需要以中序遍历的顺序继续寻找其它不超过大值的节点，如果不对平衡树进行一定的改造，这里的中序遍历并不容易实现，而在SkipList上进行范围查找就非常简单，只需要在找到小值之后，对第1层链表进行若干步的遍历就可以实现
平衡树的插入和删除操作可能引发子树的调整，逻辑复杂，而SkipList的插入和删除只需要修改相邻节点的指针，操作简单又快速
同理红黑树的范围查找也没有跳跃表的效率高，跳表也不需要维护平衡性
使用场景
java.util.concurrent 下的ConcurrentSkipListMap()
Redis sorted set的内部使用HashMap和跳跃表(SkipList)来保证数据的存储和有序，HashMap里放的是成员到score的映射，而跳跃表里存放的是所有的成员，排序依据是HashMap里存的score，使用跳跃表的结构可以获得比较高的查找效率，并且在实现上比较简单。
那为什么Redis的作者使用 SkipList 结构而不是红黑树？
- 红黑树：红黑树的查找效率很高，但是在进行重新平衡时，会涉及到大量节点的变化，因此实现和操作起来都比较复杂。
- 跳跃表：通过简单的多层索引结构，实现简单，且能达到近似于红黑树的查找效率，插入节点（多层插入）不需要像红黑树那样有额外操作。而且跳跃表还能实现范围查找及输出，而红黑树只支持单个元素查找，对于范围查找效率低
按照区间来查找数据这个操作，红黑树的效率没有跳表高。对于按照区间查找数据这个操作，跳表可以做到 O(logn) 的时间复杂度定位区间的起点，然后在原始链表中顺序往后遍历就可以了。这样做非常高效