【6千字解析】不仅仅是源码学习，更是数据结构的实战

【深入浅出leveldb】SkipList跳表

跳表是一种单链表+红黑树/avl树组合数据结构，平均O(logn)，最坏O(n)。简单来说，是多层单链表，越往上越稀疏，上层节点多少是以均衡概率或者某种概率来保持类似红黑树/AVL树平衡。基本结构我以下图为例，大家可以理解为放视频速度，可以1倍播放，2倍，4倍等等，leveldb实现有不同的方式，有采用链表形式，也有采用数组方式，到底哪种方式效率更高呢？

在我测试LeetCode 1206.设计跳表这道题上，采用leveldb方式效率直接翻倍，简直太强了，里面可以学到不少知识，今天呢详细阐述一下这篇价值不菲的文章，写给我的读者一起学习。

源码版本【1.23】

代码位置【db/skiplist.h】