Leveldb写入数据时并不是直接写磁盘，而是首先写入到内存中，然后通过后台线程进行compact并写入到磁盘，而Memtable就是leveldb在内存中用来存储写入数据的结构。所有写入的内容都会同Memtable进行排序存储，等这个Memtable的容量达到一个阀值时就将其设置为只读，然后重新创建一个新的Memtable继续提供写入操作。一个Memtable核心提供了下面两个接口，通过这两个接口来实现增删查。

// Add an entry into memtable that maps key to value at the
  // specified sequence number and with the specified type.
  // Typically value will be empty if type==kTypeDeletion.
  void Add(SequenceNumber seq, ValueType type, const Slice& key,
           const Slice& value);

  // If memtable contains a value for key, store it in *value and return true.
  // If memtable contains a deletion for key, store a NotFound() error
  // in *status and return true.
  // Else, return false.
  bool Get(const LookupKey& key, std::string* value, Status* s);

首先我们来看下它的Add方法的实现。

void MemTable::Add(SequenceNumber s, ValueType type, const Slice& key,
                   const Slice& value) {
  // Format of an entry is concatenation of:
  //  key_size     : varint32 of internal_key.size()
  //  key bytes    : char[internal_key.size()]
  //  value_size   : varint32 of value.size()
  //  value bytes  : char[value.size()]
  size_t key_size = key.size();
  size_t val_size = value.size();
  size_t internal_key_size = key_size + 8;
  const size_t encoded_len = VarintLength(internal_key_size) +
                             internal_key_size + VarintLength(val_size) +
                             val_size;
  char* buf = arena_.Allocate(encoded_len);
  char* p = EncodeVarint32(buf, internal_key_size);
  std::memcpy(p, key.data(), key_size);
  p += key_size;
  EncodeFixed64(p, (s << 8) | type);
  p += 8;
  p = EncodeVarint32(p, val_size);
  std::memcpy(p, value.data(), val_size);
  assert(p + val_size == buf + encoded_len);
  table_.Insert(buf);
}

将key和value进行编码，编码的格式为key_size、key、value_size、value，其中key部分又做了一次编码，包装成了internal_key，其编码格式如下图：

这么做的目的是为了解决两个问题，第一个问题就是将删除变成add，真正的删除在进行Compaction的时候进行，因此在编码Key的时候添加了type标志，标记这个key是删除还是添加。另外一个问题就是对象相同key的处理，如何区分新旧，因此Leveldb引入了sequence number，每次插入都会进行递增，因此相同的key一定具有不同的sequence number，谁的sequence number大谁就是最新的key。所以需要将sequence number也编码到key中，最终产生了这个internal_key。