# README
## 基于C++11和跳表的KV存储引擎
在非关系型数据库redis,以及levedb,rockdb其核心存储引擎的数据结构就是跳表。
本项目就是基于跳表实现的轻量级键值型存储引擎,使用C++实现。插入数据、删除数据、查询数据、数据展示、数据落盘、文件加载数据,以及数据库大小显示。
在随机写读情况下,该项目每秒可处理啊请求数(QPS): 24.39w,每秒可处理读请求数(QPS): 18.41w
## 项目架构
![image-20230808151049499](https://happygoing.oss-cn-beijing.aliyuncs.com/img/image-20230808151049499.png)
## 提供接口
- `insertElement`:插入数据
- `deleteElement`:删除数据
- `searchElement`:查询数据
- `displayList`:展示已存数据
- `dumpFile`:数据落盘
- `loadFile`:加载数据
- `size`:返回数据规模
## 项目编译运行方式
```shell
make // complie demo main.cpp
./bin/main // run
```
如果要在其他程序中适用该引擎,只需 `include "EZ_SkipList.h" `即可
## 跳表原理简介
跳表 (Skip List) 是由 William Pugh 发明的一种查找数据结构,支持对数据的快速查找,插入和删除。
跳表的期望空间复杂度为 $O(n)$,跳表的查询,插入和删除操作的期望时间复杂度都为 $O(\log n)$。
## 基本思想
顾名思义,跳表是一种类似于链表的数据结构。更加准确地说,跳表是对有序链表的改进。
为方便讨论,后续所有有序链表默认为 **升序** 排序。
一个有序链表的查找操作,就是从头部开始逐个比较,直到当前节点的值大于或者等于目标节点的值。很明显,这个操作的复杂度是 $O(n)$。
跳表在有序链表的基础上,引入了 **分层** 的概念。首先,跳表的每一层都是一个有序链表,特别地,最底层是初始的有序链表。每个位于第 $i$ 层的节点有 $p$ 的概率出现在第 $i+1$ 层,$p$ 为常数。
记在 n 个节点的跳表中,期望包含 $\frac{1}{p}$ 个元素的层为第 $L(n)$ 层,易得 $L(n) = \log_{\frac{1}{p}}n$。
在跳表中查找,就是从第 $L(n)$ 层开始,水平地逐个比较直至当前节点的下一个节点大于等于目标节点,然后移动至下一层。重复这个过程直至到达第一层且无法继续进行操作。此时,若下一个节点是目标节点,则成功查找;反之,则元素不存在。这样一来,查找的过程中会跳过一些没有必要的比较,所以相比于有序链表的查询,跳表的查询更快。可以证明,跳表查询的平均复杂度为 $O(\log n)$。
## 复杂度证明
### 空间复杂度
对于一个节点而言,节点的最高层数为 $i$ 的概率为 $p^{i-1}(1 - p)$。所以,跳表的期望层数为 $\sum_{i>=1} ip^{i - 1}(1-p) = \frac{1}{1 - p}$,且因为 $p$ 为常数,所以跳表的 **期望空间复杂度** 为 $O(n)$。
在最坏的情况下,每一层有序链表等于初始有序链表,即跳表的 **最差空间复杂度** 为 $O(n \log n)$。
### 时间复杂度
从后向前分析查找路径,这个过程可以分为从最底层爬到第 $L(n)$ 层和后续操作两个部分。在分析时,假设一个节点的具体信息在它被访问之前是未知的。
假设当前我们处于一个第 $i$ 层的节点 $x$,我们并不知道 $x$ 的最大层数和 $x$ 左侧节点的最大层数,只知道 $x$ 的最大层数至少为 $i$。如果 $x$ 的最大层数大于 $i$,那么下一步应该是向上走,这种情况的概率为 $p$;如果 $x$ 的最大层数等于 $i$,那么下一步应该是向左走,这种情况概率为 $1-p$。
令 $C(i)$ 为在一个无限长度的跳表中向上爬 $i$ 层的期望代价,那么有:
$$
\begin{aligned}
C(0) & = 0 \\
C(i) & = (1-p)(1+C(i)) + p(1+C(i-1))
\end{aligned}
$$
解得 $C(i)=\frac{i}{p}$。
由此可以得出:在长度为 $n$ 的跳表中,从最底层爬到第 $L(n)$ 层的期望步数存在上界 $\frac{L(n) - 1}{p}$。
现在只需要分析爬到第 $L(n)$ 层后还要再走多少步。易得,到了第 $L(n)$ 层后,向左走的步数不会超过第 $L(n)$ 层及更高层的节点数总和,而这个总和的期望为 $\frac{1}{p}$。所以到了第 $L(n)$ 层后向左走的期望步数存在上界 $\frac{1}{p}$。同理,到了第 $L(n)$ 层后向上走的期望步数存在上界 $\frac{1}{p}$。
所以,跳表查询的期望查找步数为 $\frac{L(n) - 1}{p} + \frac{2}{p}$,又因为 $L(n)=\log_{\frac{1}{p}}n$,所以跳表查询的 **期望时间复杂度** 为 $O(\log n)$。
在最坏的情况下,每一层有序链表等于初始有序链表,查找过程相当于对最高层的有序链表进行查询,即跳表查询操作的 **最差时间复杂度** 为 $O(n)$。
插入操作和删除操作就是进行一遍查询的过程,途中记录需要修改的节点,最后完成修改。易得每一层至多只需要修改一个节点,又因为跳表期望层数为 $\log_{\frac{1}{p}}n$,所以插入和修改的 **期望时间复杂度** 也为 $O(\log n)$。
## 具体实现
### 获取节点的最大层数
模拟以 $p$ 的概率往上加一层,最后和上限值取最小。
```cpp
int randomLevel() {
int lv = 1;
// MAXL = 32, S = 0xFFFF, PS = S * P, P = 1 / 4
while ((rand() & S) < PS) ++lv;
return min(MAXL, lv);
}
```
### 查询
查询跳表中是否存在键值为 `key` 的节点。具体实现时,可以设置两个哨兵节点以减少边界条件的讨论。
```cpp
V& find(const K& key) {
SkipListNode<K, V>* p = head;
// 找到该层最后一个键值小于 key 的节点,然后走向下一层
for (int i = level; i >= 0; --i) {
while (p->forward[i]->key < key) {
p = p->forward[i];
}
}
// 现在是小于,所以还需要再往后走一步
p = p->forward[0];
// 成功找到节点
if (p->key == key) return p->value;
// 节点不存在,返回 INVALID
return tail->value;
}
```
### 插入
插入节点 `(key, value)`。插入节点的过程就是先执行一遍查询的过程,中途记录新节点是要插入哪一些节点的后面,最后再执行插入。每一层最后一个键值小于 `key` 的节点,就是需要进行修改的节点。
```cpp
void insert(const K &key, const V &value) {
// 用于记录需要修改的节点
SkipListNode<K, V> *update[MAXL + 1];
SkipListNode<K, V> *p = head;
for (int i = level; i >= 0; --i) {
while (p->forward[i]->key < key) {
p = p->forward[i];
}
// 第 i 层需要修改的节点为 p
update[i] = p;
}
p = p->forward[0];
// 若已存在则修改
if (p->key == key) {
p->value = value;
return;
}
// 获取新节点的最大层数
int lv = randomLevel();
if (lv > level) {
lv = ++level;
update[lv] = head;
}
// 新建节点
SkipListNode<K, V> *newNode = new SkipListNode<K, V>(key, value, lv);
// 在第 0~lv 层插入新节点
for (int i = lv; i >= 0; --i) {
p = update[i];
newNode->forward[i] = p->forward[i];
p->forward[i] = newNode;
}
++length;
}
```
### 删除
删除键值为 `key` 的节点。删除节点的过程就是先执行一遍查询的过程,中途记录要删的节点是在哪一些节点的后面,最后再执行删除。每一层最后一个键值小于 `key` 的节点,就是需要进行修改的节点。
```cpp
bool erase(const K &key) {
// 用于记录需要修改的节点
SkipListNode<K, V> *update[MAXL + 1];
SkipListNode<K, V> *p = head;
for (int i = level; i >= 0; --i) {
while (p->forward[i]->key < key) {
p = p->forward[i];
}
// 第 i 层需要修改的节点为 p
update[i] = p;
}
p = p->forward[0];
// 节点不存在
i