LevelDB源码解析(2) SkipList(跳跃表)
背景
SkipList是LevelDB的MemTable使用的底层存储结构，LevelDB实现了一个支持泛型的跳跃表。本文不会具体介绍跳跃表的数据结构，如果读者不了解跳跃表的原理、实现，可以先看一下跳跃表（Skiplist）从原理到实现
SkipList的对外接口
Level对外只提供了3个接口，构造、插入、查找。没有提供删除接口，这个主要是因为LevelDB不会对SkipList的元素进行删除操作，整个SkipList的存储会在MemTable被释放时一起销毁。这里可以先不管MemTable，只要知道SkipList最后会被整体删除就够了。此外因为LevelDB的SkipList是用于存储用户写入的key和value的，所以LevelDB的SkipList中不会也不允许有重复的元素。
下面是SkipList的部分代码，只展示了和对外接口相关的代码
template<typename Key, class Comparator>
class SkipList
{
public:
explicit SkipList(Comparator cmp, Arena* arena);
void Insert(const Key& key);
bool Contains(const Key& key) const;
}
模板参数
template<typename Key, class Comparator>
SkipList有两个模板参数，Key和Comparator。Key是SkipList要保存的元素类型，Comparator是一个函数对象类型，用于比较两个Key的大小。
构造函数
explicit SkipList(Comparator cmp, Arena* arena);
第一个参数cmp是一个Comparator函数对象的实例，用于比较大小。第二个参数arena是一个内存分配器，SkipList会使用arena来申请内存。Arena内存分配器我们在前面的文章 —— LevelDB源码解析之Arena内存分配器介绍过。如果不了解的话，可以简单理解为malloc。SkipList将从arena申请内存，而不是直接调用malloc申请内存。
Insert 和 Contains
void Insert(const Key& key);
字如其人，插入key，不解释了。
bool Contains(const Key& key) const;
判断SkipList是否包含key，包含就返回true，反之返回false。
Iterator
LevelDB还实现了一个Iterator，用于对SkipList进行寻址、遍历等操作。下面是具体的接口和作用。
class Iterator
{
public:
// 构造函数，构造后iterator指向的是一个无效节点。
explicit Iterator(const SkipList* list);
// 判断当前节点（iterator指向的节点）是否是一个有效节点
bool Valid() const;
// 返回当前节点的值。
const Key& key() const;
// 指向当前节点的下一个节点
void Next();
// 指向当前节点的前一个节点。
void Prev();
// 指向满足 key >= target的最小节点
void Seek(const Key& target);
// 指向第一个有效节点（即不含头结点的第一个节点）
void SeekToFirst();
// 指向最后一个有效节点
void SeekToLast();
private:
//Iterator所述的SkipList
const SkipList* list_;
//指向Iterator当前节点。
Node* node_;
};
SkipList的内部实现。
因为LevelDB的SkipList是结合LevelDB的使用场景，进行了简化的SkipList，相当于是一个丐版SkipList。本文不会介绍具体的实现逻辑，关于SkipList的完整实现逻辑，可以看跳跃表（Skiplist）从原理到实现。这篇文章的跳跃表实现参考了LevelDB的实现，但是支持插入重复元素和删除元素。
LevelDB的SkipList通过next指针数组的方式来构建整个链表结构，避免了复制节点带来的内存开销和实践开销，也让链表管理变得更为简单。
此外，LevelDB在读、写next数组时，引入了原子变量用于同步，是线程安全的，可以支持多线程场景。
内存分配器
LevelDB的SkipList的内存管理使用了LevelDB自己开发的Arena内存分配器，以提高性能。Arena内存分配器的详细介绍可以看这篇文章LevelDB源码解析之Arena内存分配器