写在开头

最近在看leveldb源码，读到了skiplist的实现，虽然早就知道有这样一种数据结构，但是一直没有好好的研究它。正好借此机会对它做一次深入的研究，也为自己之后动手实现做铺垫

skiplist简介

skip List是一种随机化的数据结构，基于并联的链表，实现简单，插入、删除、查找的复杂度均为O(logN)（大多数情况下），因为其性能匹敌红黑树且实现较为简单，因此在很多著名项目都用跳表来代替红黑树，例如LevelDB、Reddis的底层存储结构就是用的SkipList。

SkipList基本数据结构及其实现

一个跳表，应该具有以下特征：

1、一个跳表应该有几个层（level）组成；
通常是10-20层，leveldb中默认为12层。

2、跳表的第0层包含所有的元素；
且节点值是有序的。

3、每一层都是一个有序的链表；
层数越高应越稀疏。

4、如果元素x出现在第i层，则所有比i小的层都包含x；

5、每个节点包含key及其对应的value和一个指向该节点第n层的下个节点的指针数组
x->next[level]表示第level层的x的下一个节点

skiplist结构.png

1.1 skiplist的插入过程

一张经典的skiplist插入图

假设插入一新键值key，值为vx，level为当前层
1、从最高层开始找到每一层比vx大的节点的前一个值，存入prev[level]。
2、初始化一个新的节点x
3、为x随机选择一个高度h
4、x->next[0..h-1] = prev[0..h-1]->next
5、prev[0..h-1]->next[0..h-1] = x

1.2 skiplist的查询过程

可直接复用上述插入前查询的第一个比vx大的节点的前一个值，看是否相等。相等则存在，否则查找下一层，直到层数为0。

1.3 skiplist删除操作

删除操作类似于插入操作，包含如下3步：1、查找到需要删除的结点 2、删除结点 3、调整指针

总结

以下来自网上我看到的一篇文章中的精辟总结：

目前常用的key-value数据结构有三种：Hash表、红黑树、SkipList，它们各自有着不同的优缺点：
Hash表：插入、查找最快，为O(1)；如使用链表实现则可实现无锁；数据有序化需要显式的排序操作。
红黑树：插入、查找为O(logn)，但常数项较小；无锁实现的复杂性很高，一般需要加锁；数据天然有序。
SkipList：插入、查找为O(logn)，但常数项比红黑树要大；底层结构为链表，可无锁实现；数据天然有序。
如果要实现一个key-value结构，需求的功能有插入、查找、迭代、修改，那么首先Hash表就不是很适合了，因为迭代的时间复杂度比较高；而红黑树的插入很可能会涉及多个结点的旋转、变色操作，因此需要在外层加锁，这无形中降低了它可能的并发度。而SkipList底层是用链表实现的，可以实现为lock free，同时它还有着不错的性能（单线程下只比红黑树略慢），非常适合用来实现我们需求的那种key-value结构。