leveldb memtable

Introduction

Memtable 提供了NewIterator, Get支持read操作， Add支持write操作， Ref/Unref支持reference count

Implementation Details

entry format

entry compared order by:

• increasing user key (according to user-supplied comparator)
• decreasing sequence number
• decreasing type (though sequence# should be enough to disambiguate)

Add

将key, value, sequence number, value type组合成entry, 然后insert到skiplist

Get

通过Skiplist::Seek找到entry， 然后判断entry里的user key是否匹配， sequence number降序排列， 这里就不需要判断了， 最后判断value type是否是kTypeValue。

Iterator

Memtable::Iterator 通过调用Skiplist::Iterator对应方法实现

Concurrency

Memtable并没有为skiplist提供write mutex，需要外部保证。

总结

Memtable提供了非常简单的接口，在leveldb中是非常重要的数据结构。