基于跳表实现的轻量级键值型KV存储引擎，使用C++实现。
链表在查找元素的时候，需要进行线性逐一查找比对，时间复杂度为线性O(n).
跳表是在链表基础上改进过来的，实现了一种「多层」的有序链表，它的原理就是为链表加多级索引，使得查找的效率提高到O(logn).
## 当读过跳表的定义后，我心里是这么想的:
查询效率为O(logn), 那不就是 二分 or 平衡二叉查找树
=> 进一步，链表不支持随机访问，显然不支持二分查找。 那就是查找树，查找树本质就是加上一层层索引，
而定义里提到跳表是“一种「多层」的有序链表”，那不就是简单的多层链表么？ 于是，我想到了下面这幅图所示的数据结构
这里模仿二分查找或二叉查找树，每两个结点会抽出一个结点作为上一级索引的结点
head -> 1 -------------------- 5 -------------------- 9 二级索引
| | |
1 ------- 3 --------- 5 -------- 7 -------- 9 一级索引
| | | | |
1 ---2 --- 3 --- 4 --- 5 ---6 --- 7 --- 8 ----9 0级索引(原始链表)
### 查找的时间复杂度:
查找元素的过程是从最高级索引开始, 一层一层遍历最后下沉到原始链表. 所以, 时间复杂度 = 索引的高度 * 每层索引遍历元素的个数
以每两个结点会抽出一个结点作为上一级索引的结点为例, h = log2(n) - 1, 而每层索引最多比较3次, 因此查询效率为 O(logn).
### 空间开销
虽然建立了多级索引, 但可以学习B+树, 索引结点并不需要存储value, 只需要存储key和本层下一个结点及下一层结点的地址值(指针)就好了.
### 插入数据
插入数据需要插入到原始链表， 以插入6.5 6.6 6.7 为例：
head -> 1 -------------------- 5 --------------------------------------- 9 二级索引
| | |
1 ------- 3 --------- 5 --------------------------- 7 --------- 9 一级索引
| | | | |
1 ---2 --- 3 --- 4 --- 5 --6 -- 6.5 -- 6.6 -- 6.7 -- 7 --- 8 ----9 0级索引(原始链表)
可以发现，当在原始链表的某个区间插入元素后，需要进行索引调整，否则若如果大量数据全部插入到同一个区间后，会退化成线性查找
索引调整其实也并不难，每两个结点会抽出一个结点作为上一级索引的结点，
我们可以允许一个区间最多三个结点，当达到4个结点时就像上递归"分裂"，即递归建立索引结点. 如图
(注意将区间为左闭右开, 和常用的C++ STL算法保持一致~)
head -> 1 -------------------- 5 --------------------------------------- 9 二级索引
| | |
1 ------- 3 --------- 5 ------ 6.5----------------- 7 --------- 9 一级索引
| | | | | |
1 ---2 --- 3 --- 4 --- 5 --6 -- 6.5 -- 6.6 -- 6.7 -- 7 --- 8 ----9 0级索引(原始链表)
支持O(logn)的查找, O(logn)的插入, 且索引不存储实际数据不会有太大空间开销
但向上递归建立索引需要记录从上到下的搜索路径(插入一个结点需要知道插入位置的前一个结点)， 那这实在太像B+树(度为2) 了. 搜了搜，事情果然没有这么简单...
个人理解：
Redis 跳表设计了非常有意思的数据结构来实现跳表，主要改进了两个点:
为了保持O(logn)查询性能，可以在每次新插入元素的时候，尽量让该元素有 1/2 的几率建立一级索引、1/4 的几率建立二级索引、1/8 的几率建立三级索引，以此类推。
这样同样保证在数据量足够大的情况下，k层 索引的结点数是 k-1层 索引结点数的 1/2. 进而保证了对数时间内完成查找.
Redis的跳表实现，这个值设置的是0.25。
即跳表在创建节点时候, 会生成范围为[0-1]的一个随机数, 如果这个随机数小于 0.25(相当于概率 25%), 那么层数就增加 1 层,
然后继续生成下一个随机数, 直到随机数的结果大于 0.25 结束, 最终确定该节点的层数
而我们这里相当于这个数是 0.5
这个值越大, 一个区间内的结点数就越少, 越容易向上建立索引, 或者说相同数据量的情况下“高度”越高。 反之亦然
在对“高度”有限制的情况下，即最高“高度”确定的情况下, 当数据量足够大时, 其实也是会退化成线性查找。
如16层，每次向上建立索引的概率为1/2，则最高层索引的节点数量为 n/(2^16). 当n足够大时，2^16的作用就很小了。
不过这应该也不是问题，因为Redis是内存型数据库，内存再大还能多大呢？
仅用原始链表的结点就可以表示全部索引！
具体的，加入最高n层索引，则可以简单在原始链表的结点中存n+1个指针，
其中第0个指针指向原始链表中下一个结点，如果这个结点最高上升到k层索引，则第 1..k 个指针指向其在 1..k层索引中的下一个结点
Node 的成员
template<typename K, typename V>
class Node {
// 没有加入前向指针
K key;
V value;
int level; // 最高出现在第几层(几级索引)
/*
* 表示当前节点在所有层的下一个节点，从上层切换到下层，就是数组下标 -1，
* 比如: forward[3]表示当前节点在第三层的下一个节点。
*/
std::vector<Node<K, V>* > forward;
};- 插入记录 - insert_element(const K&, const V&)
- 删除记录 - delete_element(const K&)
- 查找记录 - search_element(const K&);
- 展示记录 - display_list()
- 数据加载 - load_file();
- 数据存盘 - dump_file()
- 记录数量 - size()
插入数据时会使用此方法决定最高插入到第几级索引(层)
template<typename K, typename V>
int SkipList<K, V>::get_random_level() {
/*
该 randomLevel 方法会随机生成 1~MAX_LEVEL 之间的数，且 ：
1/2 的概率返回 0 => No
1/4 的概率返回 1 => 一级索引
1/8 的概率返回 2 以此类推
*/
int level = 0;
while(rand() % 2 && level < max_level)
++level;
return level;
}