Memtable：

Memtable是leveldb数据在内存中的存储形式，写操作的数据都会先写到memtable中，memtable的size有限制最大值（write_buffer_size）。memtable的底层数据结构是skiplist，class memtable完成的只是key-value的打包和调用底层跳表的接口。
首先看看Memtable的成员变量：

//实例化跳表模板
  typedef SkipList
   
     Table; //字符大小比较器 KeyComparator comparator_; //memtable的引用计数 int refs_; //内存池 Arena arena_; //底层跳表 Table table_;
   

由于memtable只是一个配接器，entry的插入操作交由底层的skiplist接口完成，关于leveldb的skiplist实现请看我写的另一篇博客。memtable真正完成的任务是打包key_value数据。memtable中存储的数据格式如下图：

参见MemTable::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(); //sequencenumber和valuetype另占8字节 size_t internal_key_size = key_size + 8; //插入的entry打包后的长度 //VarintLength(int)计算int转化为varint所要字节 const size_t encoded_len = VarintLength(internal_key_size) + internal_key_size + VarintLength(val_size) + val_size; //分配内存 char* buf = arena_.Allocate(encoded_len); //EncodeVarint32()完成varint型转化工作 char* p = EncodeVarint32(buf, internal_key_size); //写入内存 memcpy(p, key.data(), key_size); p += key_size; //把sequencenumber和valuetype写入内存 EncodeFixed64(p, (s << 8) | type); p += 8; //把valuesize和value写入内存 p = EncodeVarint32(p, val_size); memcpy(p, value.data(), val_size); assert((p + val_size) - buf == encoded_len); //把char指针插入跳表 table_.Insert(buf); }

在bool MemTable::Get( )就是查找操作

bool MemTable::Get(const LookupKey& key, std::string* value, Status* s) { //LookupKey是leveldb为了在memtable/sstable查找方便，为key包装的类型 //调用成员函数memtable_key可以返回在memtable中的key格式 Slice memkey = key.memtable_key(); //利用skiplist的专属迭代器查找key Table::Iterator iter(&table_); iter.Seek(memkey.data()); if (iter.Valid()) { // entry format is: // klength varint32 // userkey char[klength] // tag uint64 // vlength varint32 // value char[vlength] // Check that it belongs to same user key. We do not check the // sequence number since the Seek() call above should have skipped // all entries with overly large sequence numbers. const char* entry = iter.key(); uint32_t key_length; //找到了再把memtable中记录的userkey和查找对象做一次检查，要求相等 const char* key_ptr = GetVarint32Ptr(entry, entry+5, &key_length); if (comparator_.comparator.user_comparator()->Compare( Slice(key_ptr, key_length - 8), key.user_key()) == 0) { // Correct user key //从memtable中的entry提取valuetype //valuetype = kTypeva lue，是真实的数据，查找成功 //valuetype = kTypeDeletion，是要删除的数据，并非不代表数据真实存在 const uint64_t tag = DecodeFixed64(key_ptr + key_length - 8); switch (static_cast
     
      (tag & 0xff)) { case kTypeva lue: { Slice v = GetLengthPrefixedSlice(key_ptr + key_length); value->assign(v.data(), v.size()); return true; } case kTypeDeletion: *s = Status::NotFound(Slice()); return true; } } } return false; }
     

GetVarint32Ptr函数就是varint型编码的逆过程，解码。

关于Varint（变长整型）