首页 > 代码库 > leveldb源码分析--Comparator
leveldb源码分析--Comparator
既然leveldb是一个按Key序组织的LSM-Tree实现，那么对于Key的比较就是非常之重要了，这个Key的比较在leveldb中是Comparator的形式出现的。我们首先来看看Comparator的基本方法有哪些
// 实际的比较函数 virtual int Compare(const Slice& a, const Slice& b) const = 0; // 名称，主要是为了防止建立和读取时使用了不同的Comparator virtual const char* Name() const = 0; //找出 [start, limit）之间的一个短的串，主要作用是降低一些存储空间 virtual void FindShortestSeparator( std::string* start, const Slice& limit) const = 0; //作用类似，但无上端限制 virtual void FindShortSuccessor(std::string* key) const = 0;
在leveldb中已经实现的类有两个，一个是内置的BytewiseComparatorImpl，另一个是InternalKeyComparator。我们首先来分析BytewiseComparatorImpl的实现，实现十分简单，我们这里只对实现的功能用注释的方式进行说明
// Bytewise直接调用Slice的Compare，按memcmp的方式进行比较，然后再比较长短 int Compare(const Slice& a, const Slice& b)
//对start和limit的公共部分外的start中的可以uint8方式+1的字节+1，清除该位之后的数据 void FindShortestSeparator(std::string* start, const Slice& limit) //直接对key中第一个可以uint8方式+1的字节+1，清除该位后面的数据 void FindShortSuccessor(std::string* key)
我们分析InternalKeyComparator的内部实现，看其成员变量其包含了一个Comparator类型的user_comparator_，其比较都用到了这个成员变量的方法，这个类的实现是在使用这些方法的过程中加入了一些解码的过程。根据其解码过程和名字我们可以看出这个比较器是用来比较传入为InternalKey对象，我们知道其组成为
user_key (string) | sequence (7 byte) | value_type (1 byte)
对于InternalKeyComparator的三个函数的具体实现说明为
// 传入的值解码得到user_key后对user_key进行比较 int Compare(const Slice& a, const Slice& b)
//解码后对user_key FindShortestSeparator，然后再最后加入kMaxSequenceNumber|kValueTypeForSeek void FindShortestSeparator(std::string* start, const Slice& limit) //将key的第一个可以+1的字节+1，然后加上kMaxSequenceNumber|kValueTypeForSeek void FindShortSuccessor(std::string* key)
我们再来看看MemTable关于Table 的定义
typedef SkipList<const char*, KeyComparator> Table; Table table_;而 KeyComparator的定义为： struct KeyComparator { const InternalKeyComparator comparator; explicit KeyComparator(const InternalKeyComparator& c) : comparator(c) { } int operator()(const char* a, const char* b) const; };
由此可知KeyComparator是一个引用了InternalKeyComparator作为成员变量的结构体，而InternalKeyComparator又引用了一个 Comparator类型的user_comparator_。理清了了这些所谓的Comparator的引用层次关系以后，我们来看看leveldb中定义SkipList是使用的哪个Comparator。首先看MemTable的构造函数
MemTable::MemTable(const InternalKeyComparator& cmp) : comparator_(cmp), refs_(0), table_(comparator_, &arena_) {}
可以看到构造函数接收一个InternalKeyComparator类型的参数，然后构建内部的KeyComparator，然后在将其传递给SkipList 的table_，而通过查找我们看到其构造是在DBImpl的构造函数中被调用的，看代码
DBImpl::DBImpl(const Options& raw_options, const std::string& dbname) : env_(raw_options.env), internal_comparator_(raw_options.comparator), ...... mem_(new MemTable(internal_comparator_)),
再继续往下找到有如下代码
Status DB::Open(const Options& options, const std::string& dbname, DB** dbptr) { DBImpl* impl = new DBImpl(options, dbname); ......}
所以我们可以得出结论是最终的SkipList中使用的Comparator就是在Open数据库的时候传入的参数Option中的成员变量comparator，所以我们在实现自己的Comparator的时候只有仿照BytewiseComparatorImpl实现一个，然后通过option的方式传递给leveldb即可。
最后我们整理一下思路：
1. SkipList中使用的KeyComparator仅仅是对InternalKeyComparator的一个包含式的封装；
2. 而InternalKeyComparator是对key的简单编解码后使用option中传入的Comparator，默认为BytewiseComparatorImpl
InternalKeyComparator中的编解码是user_key和InternalKey之间的转换，所以最终的顺序（大小）的比较其实都是user_key（Put,Get,Delete传入的Key值）根据option中的Comparator（默认为BytewiseComparatorImpl）进行compare得出顺序。
理清这个顺序以后对leveldb中的各个Comparator就比较容易理解了。