简介

这种数据结构是William Pugh于1990年在在 Communications of the ACMJune 1990, 33(6) 668-676 发表了Skip lists: a probabilistic alternative to balanced trees，论文标题可知，SkipList设计初衷是替换平衡树

（1）AVL树查询效率严格O(logN)，插入需多次旋转，导致插入效率较低，才有更实用红黑树。

（2）红黑树并发环境不方便，更新数据时，Skip更新较少，锁的也少，而红黑树有平衡的过程（涉及到较多节点），锁住更多节点，降低并发性。

（3）SkipList优势实现简单，红黑树2天，SkipList2个小时实现。

用途：Redis, 还有Google的著名项目Bigtable    

概要：查找、插入、移除

一、查找

在普通单向链表加索引（分层），快速查

找key为19，索引到9，9 < 19,继续查找到21这个节点，21 > 19, level由2降低到1

17这个节点，17 < 19, 继续往后，21这个结点，发现21>19, level由1降低到0

在结点17上，level==0索引到19,查找完毕。

1、整体：

2、Node定义:

3、参数

4、查找代码

二、插入

从所有小于待插入节点key值的节点中，找出最大

插入17，查到12,12 < 17,19 > 17,满足条件

创建新结点，在1~MAX_LEVEL之间随机level值作为该结点的level

三、移除

查找到指定结点，没找到则返回

调整指针指向

释放结点空间

完整代码https://github.com/HiWong/SkipListPro

https://blog.csdn.net/tjtulong/article/details/106138945