共计 1375 个字符，预计需要花费 4 分钟才能阅读完成。
skiplist 简介
skip List 是一种随机化的数据结构，基于并联的链表，实现简单，插入、删除、查找的复杂度均为 O(logN)（大多数情况下），因为其性能匹敌红黑树且实现较为简单，因此在很多著名项目都用跳表来代替红黑树，例如 LevelDB、Reddis 的底层存储结构就是用的 SkipList。
目前常用的 key-value 数据结构有三种：Hash 表、红黑树、SkipList，它们各自有着不同的优缺点：Hash 表：插入、查找最快，为 O(1)；如使用链表实现则可实现无锁；数据有序化需要显式的排序操作。红黑树：插入、查找为 O(logn)，但常数项较小；无锁实现的复杂性很高，一般需要加锁；数据天然有序。SkipList：插入、查找为 O(logn)，但常数项比红黑树要大；底层结构为链表，可无锁实现；数据天然有序。
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 的查询过程
查询的第一个比 vx 大的节点的前一个值，看是否相等。相等则存在，否则查找下一层，直到层数为 0。
以已有数据 13、22、75、80、99 为例
从最高层（此处为 2）开始
1、level2 找到结点 Node75 小于 80，且 level2.Node75->next 大于 80，则进入 level1 查找 (此处已经跳过了 13~75 中间的结点（22),
2、level1.Node75 < 80 < level1.Node75->next，进入 level0
3、level0.Node75->next 等于 80，找到结点
skiplist 的插入过程
假设插入一新键值 key，值为 84，level 为当前层
1、从最高层开始找到每一层比 84 大的节点的前一个值，存入 prev[level]。
这里
prev[2] = leve2.Node75
prev[1] = leve1.Node75
prev[0] = level0.Node80
2、初始化一个新的节点 843、为 x 随机选择一个高度 h, 这里选 24、x->next[0..h-1] = prev[0..h-1]->next5、prev[0..h-1]->next[0..h-1] = x
（步骤 4、5 为链表插入结点的操作）
skiplist 删除操作
删除操作类似于插入操作，包含如下 3 步：1、查找到需要删除的结点 2、删除结点 3、调整指针
总结
如果要实现一个 key-value 结构，需求的功能有插入、查找、迭代、修改，那么首先 Hash 表就不是很适合了，因为迭代的时间复杂度比较高；而红黑树的插入很可能会涉及多个结点的旋转、变色操作，因此需要在外层加锁，这无形中降低了它可能的并发度。而 SkipList 底层是用链表实现的，可以实现为 lock free，同时它还有着不错的性能（单线程下只比红黑树略慢），非常适合用来实现我们需求的那种 key-value 结构。
