本文共 2734 字，大约阅读时间需要 9 分钟。

---

前言

根据前一篇可以知道，leveldb在磁盘中的存储模型是sstable，sstable总的来说就是存储一个一个的key-value信息序列以及一些管理信息。用户一般是通过leveldb的用户接口

Status Put(const WriteOptions&, const Slice& key, const Slice& value);

或者

Status Write(const WriteOptions& options, WriteBatch* updates);

来向leveldb中保存数据的。显然对每个key-value都直接写入磁盘上的sstable中是不现实的，一方面效率有问题，磁盘IO太频繁，而且写入的数据量太小；另一方面是这样的写入方式不利于对整个sstabl的管理信息的统计。leveldb采取的策略是，先将key-value写到内存中的MemTable中，当MemTable中的数据量到达一定程度时，再将整个MemTable以sstable的形式写入磁盘，形成一个sstable。我们可以把Memtable看成是sstable的内存形式。这种方式除了可以避免上面的两个缺点外，还可以加快读的速度。

在leveldb中有两个Memtable，分别是imm_和mem_。imm_是不可写的，mem_可写，一般我们所说的写数据就是向mem_中写入数据。那imm_有什么用呢？这个主要是当mem_被写满时(满足一定的阀值)，因为需要将mem_写入到磁盘形成sstable，但是在写入mem_的时候，又不希望用户因等待而不能继续向数据库写数据(如果只有一个mem_的话，只能等到mem_全部写到磁盘后，用户才能再往mem_上写数据)。imm_的作用就是当mem_写满时，将当前的mem_赋值给imm_，然后为mem_重新分配一个MemTable供用户写，而开启一个背景线程将imm_写入磁盘。

---

MemTable的底层数据结构

为了方便查找，leveldb中的key-value键值序列是按key的大小顺序存储的。因此应该设计一种数据结构，使得key-value的插入(leveldb里面没有删除)比较简单，这种数据结构很多，包括AVL树，红黑树等二叉树结构，它们都可以保证插入操作的事件复杂度为O(lgn)。不过leveldb使用的是另一种更加简单的数据结构——skiplist(跳跃链表)。下面我们看一下跳跃链表的实现：

---

跳跃链表的实现

跳跃链表是一种随机化的数据结构，基于并联的链表，它的效率可以比拟于平衡二叉查找树。基本上，跳跃链表是对有序的链表增加上附加的前进链接，增加是以随机化的方式进行的。所以在链表插叙的时候可以快速跳过某些元素找到目标元素。我们可以用地铁线路来类比跳跃链表，一次来直观了解跳跃链表的优越性：

在这个地铁线路图中，如果我们要从上海南站到东川路地铁站，则我们要途径线路上的每一个站，显然比较费时间，但是也没办法。如果铁路局在这条线路上建一条高速线路，如下所示：

那我们去东川路就要快的多。如果我们要去富锦路的话，可以先走高速线路：上海南 -> 佘山 然后再从高速线路下来，走下面的 佘山->虹桥->富锦路，相当于只经过了两站。随着最底层的站数的增多，我们可以多建几个高速层以提高到达目的地的速度。跳跃链表本质上就是基于这样的原理。如下图所示

原理搞清楚了，可是如果要插入新的元素应该怎么办呢？显然因为最底层是要包含所有元素的，因此新元素肯定要插入到最底层的链表中，问题在于 什么时候选择为这个新插入的元素在高速层建一个站台呢？答案是，由上帝决定。这就是skiplist的随机化来源，在考虑是否将一个新插入的元素插入更高层的链表时，采用抛硬币的方法，如果反面就不用再往上层的链表插入了，反则反之。考虑在上图中插入一个新元素9，则首先在底层链表将这个新元素插入进去，如下图所示：

好了，下面通过抛硬币决定是否将9插入到它的上一层。如果结果是要插入，则链表变成如下形式：

因为这次抛硬币结果是将新插入的节点插入更上一层，接下来，我们还要继续抛硬币，决定是否将节点再往上插入一层，如果结果还是肯定的，那链表将会变成如下形式：

接下来还要继续抛，一直到该节点不再往更上层插入为止。每一个新插入的节点都是这个过程。 而且我们可以看到，当需要将某个节点插入更高一层的链表，而这个更高一层的链表还不存在时，需要新建一个链表，这个新链表的首节点和它下面各层的链表的首节点相同。所以说，跳跃链表中各层链表的首节点是一样的。因为不断的插入新节点可能使得跳跃链表的层数(高度)很多，因此我们可以设置一个阀值，当上升的层数达到这个阀值时就不再上升了，这样我们就可以在最开始初始化时将跳跃链表的高度确定下来，并初始化各层链表的头结点，以方便后面的插入。比如对于一个高度设置为5的跳跃链表，我们可以进行如下初始化：

其中头结点只起到标记作用，不存储数据。初始时各个链表的头结点都指向空。后续的插入就按我们之前的算法进行即可。

可以看到跳跃链表非常简单直观，实现起来也非常容易，起码和RB tree相比是这样的。

Memtable中的跳跃链表基本上就是按照我们上面的思路实现的：

typedef SkipList
   
     Table;
   

其中KeyComparator是比较器，char*表示插入的元素类型是字符串。可以看到Memtable是按key-value为整体的字符串的大小将其插入到skiplist中的，key-value的字符串形式正如我们前篇所说的那样：

从Memtable的Add函数我们可以了解到这些细节。

Add函数的接口如下所示：

void Add(SequenceNumber seq, ValueType type,           const Slice& key,           const Slice& value);

具体细节再看源码了，还是比较简单的。

---

总结

用户向leveldb写入数据时，首先写入到内存的Memtable中，当Memtable中的数据积累到一定数量时，再统一生成一个sstable，并将memtable中的数据写入进去。可以认为一个MemTable对应一个sstable。为了方便查找，leveldb将所有数据按照大小顺序存储，为了提高数据写入的效率，Memtable用skiplist做底层的存储数据结构。本质上用户是将数据(internal-key-value)串成一个字符串，插入到Memtable的skiplist中，保证插入的字符串在SkipList中按顺序存储。