最近学习一个GO语言写的开源项目Lotusdb， https://github.com/flower-corp/lotusdb, 其中使用跳表作为数据结构来缓存Key-Value，产生了疑惑为什么不直接用Map而要自己写个跳表呢？ 带着这个疑惑我就进一步学习了很多知识。学习过程记录下来。
跳表
首先第一个知识点跳表，跳表可以实现二分查找的有序链表， 这里直接借用一个图来说明
这张图来自极客时间- 王争老师《数据结构与算法之美》 https://time.geekbang.org/column/article/42896
举例说明它的原理， 比如我们要找key=5的结点，我们先在二级索引上面找到1， 向下找到第一级索引中找到4和7之间，从4再向下，到了原始链表，从4开始遍历，就能找到5这个结点了。它能提高我们查找的效率。而且原始链表是有序的，在需要顺序的场景，它就比较有用了。
这里有篇文章详细的描述了跳表的原理 Skip List--跳表（全网最详细的跳表文章没有之一）
跳表的查询，插入，删除时间复杂度O(logn)， 空间复杂度是增加了索引，索引的空间复杂度O(n), 但是索引只是key,所以占用空间可以忽略
Map
第二个知识点“Map”， 以前我只知道Map是用来存储Key-Value的，能够通过key，快速的找到Value， 但是它底层的数据结构是什么，我就不没有细究，这次把它认真的学习了下，实际上Map是数组+链表，看下图
这张图来自博客园 go map数据结构和源码详解
举例说明， 对于某个key, 我们先用对key进行hash, hash成数组的下标， 对应图中的Hmap.buckets，通过数据下标就找到了它的位置。那么对于发生hash 碰撞的情形怎么办呢？ 不同的key，hash成相同的值的情况，Go语言是链接到了一个8个元素的数组， 遍历这个数组就能找到我们要的元素了，对于超过8个的情况就用图上的溢出指针指向个链表。
通过这个大体的分析我们能够知道map的时间复杂度是O(1)， 空间复杂度O(0.1875n) ~ O(n)之间
那么map要比跳表在性能上更优秀。如何来验证这一点呢？ 接下来我们就通过实际的代码来确定这个实验。
这里用到go 自带的benchmark测试
插入性能
首先我们测试插入性能， 这里skiplist 我们使用"github.com/flower-corp/lotusdb/arenaskl"， map使用go runtime自带的
插入SkipList和Map
上面两个方法分别是存入skip list 和 map, 根据recordNum的数据，插入数据到这两个数据结构中
通过对比这两个benchmark, 我们插入相同的100000条记录，InsertSkipList 1S中可以做24次， InsertMap 1S中可以做46次， 性能相差一倍。
读取性能
读数据
分别读取SkipList和Map中的数据。
读性能对比
可以看到读取相同的记录数，ReadMap 要比ReadSkipList快一倍多，一个是74，一个是32.
总结
通过数据结构的原理分析和实际代码验证，我们能看出Map的性能确实要比SkipList快，那么回到我们最初的问题，为什么要选SkipList 呢， 我想答案应该是SkipList是有序的， 后面的操作需要用到它的有序性来存储到磁盘。实际上LSM Tree数据库都是使用SkipList来作为它的数据结构，这点在我们前面的跳表原理的那片博客中有讲到。至此疑问得到解答。通过这个分析源码，我学到了Map和SkipList的原理，学到了如何用Go来写Benchmark test，这个benchmark test确实很好用，对比不同的方法的性能，它很优秀而且天然集成在Go的标准库中，是开发的好帮手。