参考

LevelDb 源码阅读--leveldb基础数据结构
https://github.com/google/leveldb/blob/master/db/dbformat.h

1. WriteBatch——Put/Delete

LevelDB对于每一个Put/Delete操作的kv，都会生成一个WriteBatch进行操作。

// WriteBatch::rep_ :=
//    sequence: fixed64
//    count: fixed32
//    data: record[count]
// record :=
//    kTypeValue varstring varstring         |
//    kTypeDeletion varstring
// varstring :=
//    len: varint32
//    data: uint8[len]

WriteBatch实际存储数据的地方在std::string rep_这个成员变量。

• sequence：0-7字节是sequence number
• count：8-11字节是count，记录batch中有多少个kv记录（包括delete的记录）
• data：12字节及之后是一个个编码后的kv数据，每一个kv紧凑排布
  • 对于delete的记录，其编码格式为kTypeDeletion|varstring，kTypeDeletetion == 0x00，占用一个字节，varstring则为待删除key的变长编码（varstring）。
  • 对于写入的记录， 其编码格式为kTypeValue|varstring|varstring，kTypeDeletetion == 0x01，占用一个字节，第一个varstring则为待插入key的变长编码（varstring），第二个varstring为待插入的value的变长编码（varstring）
  • varstring的编码格式为len|data，len表示字符的长度，采用varint32编码方式，data则为对应的字节数组。

可见，在WriteBatch中，每一个kv数据记录都是紧凑地编码到一起的。

最终，在写入MemTable时，会将WriteBatch的data拆分开成一个个的kv数据记录（仅包含varstring的data部分），调用对应的add/delete接口，进行重新编码再写入。此处的重编码，value并没有变化，主要是key需要扩充成InternalKey（原key的后面，增加8个字节，高7个字节是sequence number，最低的一个字节是ValueType（kTypeValue或kTypeDeletion）），然后重新进行varstring。MemTable插入的也是kv紧凑编码在一起的字节数组。重编码后，每个key就是有序的了。

<font color=red>笔者认为，这里 value 可以直接服用 WriteBatch 的编码结果，可以减少编解码的开销。</font>

2. 各种类型的key —— Get

LevelDB是一个kv的数据库，支持mvcc的快照。在内部实现中，key又通过叠加额外的信息，分成了多种key，比如说前文中提到的InternalKey（参见dbformat.h中，LookupKey与其他key的转换函数）。对于Get请求，key都会生成要给LookupKey来查找数据。

• UserKey: 这个就是用户调用db接口的时候，传入的key。
• InternalKey: LevelDB在UserKey的后面增加了8个字节（高7字节表示sequance number，用于mvcc的版本；最低一个字节表示key类型，value/delete），可见函数ParseInternalKey。
• MemtableKey: InternalKey的基础上，在前面增加varint，记录InternalKey的长度
• LookupKey: LookupKey其实就是MemtableKey，只不过这个结构体中，自带了一个200字节的buffer，如果key较小，则直接存放到这个buffer中

// A helper class useful for DBImpl::Get()
class LookupKey {
 public:
  // Initialize *this for looking up user_key at a snapshot with
  // the specified sequence number.
  LookupKey(const Slice& user_key, SequenceNumber sequence);

  LookupKey(const LookupKey&) = delete;
  LookupKey& operator=(const LookupKey&) = delete;

  ~LookupKey();

  // Return a key suitable for lookup in a MemTable.
  Slice memtable_key() const { return Slice(start_, end_ - start_); }

  // Return an internal key (suitable for passing to an internal iterator)
  Slice internal_key() const { return Slice(kstart_, end_ - kstart_); }

  // Return the user key
  Slice user_key() const { return Slice(kstart_, end_ - kstart_ - 8); }

 private:
  // We construct a char array of the form:
  //    klength  varint32               <-- start_
  //    userkey  char[klength]          <-- kstart_
  //    tag      uint64
  //                                    <-- end_
  // The array is a suitable MemTable key.
  // The suffix starting with "userkey" can be used as an InternalKey.
  const char* start_;
  const char* kstart_;
  const char* end_;
  char space_[200];  // Avoid allocation for short keys
};

Key结构：
A: klength  varint32               <-- start_ 指针
B: userkey  char[klength]          <-- kstart_ 指针 
C: tag      uint64    
                                    <-- end_ 指针
A意义：（user_key.size() + 8） 变长编码（varint）后的值
B意义：userkey
C意义：64位整型顺序号<<8+值类型 64位定长编码后的值

memtable_key = A + B + C
internal_key = B + C
user_key = B

查找的时候，SkipList使用的是InternalKeyComparator，先比较user_key，然后比较sequence number。