leveldb查找操作主函数：
Status DBImpl::Get(const ReadOptions& options,
const Slice& key,
std::string* value) {
Status s;
MutexLock l(&mutex_);
SequenceNumber snapshot;
if (options.snapshot != NULL) {
snapshot = reinterpret_cast<const SnapshotImpl*>(options.snapshot)->number_;
} else {
snapshot = versions_->LastSequence();
}
MemTable* mem = mem_;
MemTable* imm = imm_;
Version* current = versions_->current();
mem->Ref();
if (imm != NULL) imm->Ref();
current->Ref();
bool have_stat_update = false;
Version::GetStats stats;
// Unlock while reading from files and memtables
{
mutex_.Unlock();
// First look in the memtable, then in the immutable memtable (if any).
LookupKey lkey(key, snapshot);
if (mem->Get(lkey, value, &s)) {
// Done
} else if (imm != NULL && imm->Get(lkey, value, &s)) {
// Done
} else {
s = current->Get(options, lkey, value, &stats);
have_stat_update = true;
}
mutex_.Lock();
}
if (have_stat_update && current->UpdateStats(stats)) {
MaybeScheduleCompaction();
}
mem->Unref();
if (imm != NULL) imm->Unref();
current->Unref();
return s;
}
Get函数主体流程很简单，先从memtable中查找，再从Immutable中查找，最后从磁盘Table中查找。但是查找过程中可以考虑几个问题：
多版本控制
查找时指定某个快照版本时如何找到数据
先后插入了数据 "wcc":28, "wcc":29, "wcc":30, 此时查找过程如何
先插入了数据 "wcc":28 然后删除了数据 "wcc":28, 此时查找过程如何
并发控制
读数据的时候 其他的写线程会造成哪些影响
对于memtable(底层数据结构是skiplist)，插入的数据格式为：
key.png
而skiplist插入查找元素时使用的比较函数是:
// aaa:101 aab:101 --> aaa:101, aab:101 //user key小的会排在前面
// aaa:101 aaa:102 --> aaa:102, aaa:101 //user key相同, sequence大的会排在前面(教新的操作)
int InternalKeyComparator::Compare(const Slice& akey, const Slice& bkey) const {
// Order by:
// increasing user key (according to user-supplied comparator)
// decreasing sequence number
// decreasing type (though sequence# should be enough to disambiguate)
int r = user_comparator_->Compare(ExtractUserKey(akey), ExtractUserKey(bkey));
//userkey相同时,比较 (sequence num << 8 | value_type)
//实际上sequence num已经能完全区分了
if (r == 0) {
const uint64_t anum = DecodeFixed64(akey.data() + akey.size() - 8);
const uint64_t bnum = DecodeFixed64(bkey.data() + bkey.size() - 8);
if (anum > bnum) {
r = -1;
} else if (anum < bnum) {
r = +1;
}
}
return r;
}
因此：
当需要从指定快照版本查找数据时，ReadOptions::snapshot 应该设置成指定版本。查找key时会把 key,快照版本号组合起来进行查找。
当数据被修改(多次插入)，如果没指定版本号，会根据当前最新版本号，找到最后一次插入的数据值。
当数据插入后被删除，因为删除操作的sequence number更大，因此查找时优先返回，然后根据valueType是kTypeDeletion 告知调用者key对应的数据不存在。
对于磁盘中的Table, compact数据时会保证，如果key的sequence number比最小的snapshot 大的话, delete的数据也不会被drop掉.
