至此，将插入流程以及压缩流程都已介绍完毕了，本篇主要介绍查询流程。
一、查询流程
首先来看一下查询接口具体实现内容:
/**
* 查询
* @param options 查询选项
* @param key 查询key
* @param value 输出参数 如果找到则赋值给value
*/
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)) {//查找mem table
// Done
} else if (imm != NULL && imm->Get(lkey, value, &s)) {//查找immutable mem table
// Done
} else {
// 查找ldb文件 最新的版本信息Version都保存在current中
s = current->Get(options, lkey, value, &stats);
have_stat_update = true;
}
mutex_.Lock();
}
//是否需要启动压缩流程
if (have_stat_update && current->UpdateStats(stats)) {
MaybeScheduleCompaction();//表示由于某个文件seek次数过多需要合并
}
mem->Unref();
if (imm != NULL) imm->Unref();
current->Unref();
return s;
}
查找顺序按照:MemTable -> Immutable MemTable -> ldb文件(sst文件)，只要有一个流程中找到则返回。对于查找MemTable流程可参考《leveldb深度剖析-MemTable》。下面介绍在ldb中查询流程
二、ldb查询流程
/**
* 进入此方法 说明在memtable中没有找到 因此需要在文件中查找
* @param options 查询流程选项
* @param k 查询关键字
* @param value 查询value 输出参数
* @param 查询结果 输出参数
*/
Status Version::Get(const ReadOptions& options,
const LookupKey& k,
std::string* value,
GetStats* stats) {
Slice ikey = k.internal_key();
Slice user_key = k.user_key();
const Comparator* ucmp = vset_->icmp_.user_comparator();// 比较器
Status s;
stats->seek_file = NULL;
stats->seek_file_level = -1;
FileMetaData* last_file_read = NULL;
int last_file_read_level = -1;
// We can search level-by-level since entries never hop across
// levels. Therefore we are guaranteed that if we find data
// in an smaller level, later levels are irrelevant.
// 这个循环 是确定文件范围
std::vector<FileMetaData*> tmp;
FileMetaData* tmp2;
for (int level = 0; level < config::kNumLevels; level++) {// 循环遍历每一层文件
size_t num_files = files_[level].size();
if (num_files == 0) continue;
// Get the list of files to search in this level
FileMetaData* const* files = &files_[level][0];
if (level == 0) {// level0文件中 key是有重叠的
// Level-0 files may overlap each other. Find all files that
// overlap user_key and process them in order from newest to oldest.
tmp.reserve(num_files);
for (uint32_t i = 0; i < num_files; i++) {//循环遍历 当前层次中每个文件
FileMetaData* f = files[i];
if (ucmp->Compare(user_key, f->smallest.user_key()) >= 0 &&
ucmp->Compare(user_key, f->largest.user_key()) <= 0) {
tmp.push_back(f);
}
}
if (tmp.empty()) continue;//说明key不存在当前level中所有文件
//
std::sort(tmp.begin(), tmp.end(), NewestFirst);
files = &tmp[0];
num_files = tmp.size();
} else {//非level0文件
// Binary search to find earliest index whose largest key >= ikey.
uint32_t index = FindFile(vset_->icmp_, files_[level], ikey);
if (index >= num_files) {//表示没有找到
files = NULL;
num_files = 0;
} else {//当前文件中最大值比key要大 因此只能说明待查找的key可能存在当前文件中
tmp2 = files[index];
if (ucmp->Compare(user_key, tmp2->smallest.user_key()) < 0) {
// All of "tmp2" is past any data for user_key
// 要查找的key 比当前文件中最小的key 还要小 说明不在此文件中
files = NULL;
num_files = 0;
} else {// 待查找key 都已经满足文件最大值和最小值 但是此时仍然不能确定是否存在
files = &tmp2;
num_files = 1;
}
}
}
//到这里说明：我们要查找的文件范围已经确定了 具体有没有我们需要的key则需要进一步查询
//num_files已经重新赋值 当num_files不为0 只能说明待查找key可能存在文件中 需要进一步对比
for (uint32_t i = 0; i < num_files; ++i) {
if (last_file_read != NULL && stats->seek_file == NULL) {
// We have had more than one seek for this read. Charge the 1st file.
// 该分支如果进入了 只会进入一次 表示第一个文件不存在我们要查找的key 相当于没有命中 那么我们
// 就要将其记录下来 并且在UpdateStats函数中对器allow_seek进行减一操作
stats->seek_file = last_file_read;
stats->seek_file_level = last_file_read_level;
}
FileMetaData* f = files[i];
last_file_read = f;
last_file_read_level = level;
Saver saver;
saver.state = kNotFound;
saver.ucmp = ucmp; //比较器
saver.user_key = user_key;
saver.value = value; //输出参数 保存value返回给用户
//构建 table cache 基于局部性原理+LRU算法
s = vset_->table_cache_->Get(options, f->number, f->file_size,
ikey, &saver, SaveValue);
if (!s.ok()) {//异常
return s;
}
switch (saver.state) {
case kNotFound:
break; // Keep searching in other files 没有找到继续查找
case kFound:
return s;//找到直接返回
case kDeleted:
s = Status::NotFound(Slice()); // Use empty error message for speed
return s;
case kCorrupt:
s = Status::Corruption("corrupted key for ", user_key);
return s;
}
}
}
return Status::NotFound(Slice()); // Use an empty error message for speed
}
说明：
1）该函数有两个for循环，第一个for循环按照层次遍历文件，凡是符合这个条件： smallest.user_key <= 待查找user_key <= largest.user_key的文件都是我们需要查询的。
2） 第二个for循环，按照第一个for循环确定出来的文件，进行深入查询对比。这里采用cache思想来提升性能。
3）leveldb采用LRU方式管理open的文件，table_cache->Get返回后判断saver状态，如果是kFound/kDeleted则说明找到了直接退出，否则继续查找下一个文件。
三、总结
查找流程其实不是特别复杂，主要逻辑还是在于TableCache这部分。由于TableCache功能比较独立，这里单独放一篇博客，来详细说明TableCache具体实现。
