【文章仅供非商业用途或交流学习使用】
最近研究Redis的相关内容，发现SkipList跳表多次用到，在这里记录一下。
一、跳表简介
SkipList（后面简称SL）是一种支持快速查找的随机化数据结构，是一种可以进行二分查找的有序链表。跳表在原有的有序链表上增加了多级索引，通过索引可以实现快速查找，不仅提高了搜索性能，同时也可以提高插入和删除操作的性能。
二、数据结构
SL的主要设计思想是将链表与二分查找相结合，它维护了一个多层级的链表结构，这是一个用空间换时间的思路。可以把SL看做是一个含有多个行的链表结合，并具有如下性质：
1 SL由很多层组成；
2 每一层都是一个有序的链表；
3 最底层包含的连接包含所有元素；
4 如果一个额元素出现在Level i 层的链表中，则它在level i 之下所有层的链表中都会出现；
5 每个节点包含两个指针，一个指向同一个链表中的下一个元素，一个指向下面一层的元素。
三、搜索方式
对一个目标元素的搜索会从顶层链表的头部元素开始，然后遍历该链表，直到找到元素大于或等于目标元素的节点：
1 如果当前元素正好等于目标，那么就直接返回它；
2 如果当前元素小于目标元素，那么就跳到下一层继续搜索；
3 如果当前元素大于目标或到达链表尾部，则先移动到前一个节点的位置，然后跳到下一层。
四、随机产生的层
SL具体产生多少层，是完全随机的，业界最恰当的比喻是丢硬币，正面则将节点复制到上层，反面则停止。
参考文献：
https://en.wikipedia.org/wiki/Skip_list
https://baike.baidu.com/item/%E8%B7%B3%E8%A1%A8/22819833?fr=aladdin#6_1
