2.3　key比较函数接口Comparator

LevelDB是按key排序后进行存储，因此必然少不了对key的比较。在源码中，key的比较主要是基于Comparator这个接口实现的，Comparator是一个纯虚类，具体定义如下：

class Comparator{
public:
 　  virtual ~Comparator();
 　  virtual int Compare(const Slice &a, const Slice& b) const = 0;
 　  virtual const char* Name() const = 0;
 　  virtual void FindShortestSeparator(std::string *start, const Slice 
 　  　 &limit) const = 0;
 　  virtual void FindShortSuccessor(std::string *key) const = 0;
}

Comparator类的接口的具体作用，参见表2-1。其中，Compare方法是其主要的逻辑功能（即相应的字符串比较功能）的实现。Name用于获取这个比较器的名称，可以用这个函数检查比较器是否匹配。

表2-1　Comparator类的主要接口

一般而言，用户可以针对自身的要求，以Comparator为接口，定义新的比较算法模块。在LevelDB中，有两个实现Comparator的类：一个是BytewiseComparatorImpl，另一个是InternalKeyComparator。

BytewiseComparatorImpl是LevelDB中内置的默认比较器，主要采用字典序对两个字符串进行比较。Comparator接口理解的难点在于FindShortestSeparator和FindShortSuccessor这两个函数。下面分别对这两个函数在BytewiseComparatorImpl中的具体定义进行详细描述。

FindShortestSeparator（std::string* start, const Slice& limit）传入的参数是*start和limit这两个字符串。参数*start对应原字符串，而经过一系列逻辑处理后，相应的短字符串也将保存在*start中以返回。该函数在BytewiseComparatorImpl中的具体算法逻辑如下。

1）找出两个字符串*start和limit之间的共同前缀，如果没有共同前缀，则直接退出。

2）如果有共同前缀，判断start中共同前缀的后一个字符是否小于0xff，且后一个字符加1后要小于limit中共同前缀的后一个字符，如果条件不满足，则直接退出。

3）将*start中共同前缀的后一个字符串加1，然后去掉后续所有的字符，并返回退出。

为了更好地说明这个函数的具体实现，这里假如有*start = "abcd"，limit="abzf "，则很明显它们之间有共同前缀ab，那么经过函数处理后c+1=d，*start最终为abd。

FindShortSuccessor（std::string* key）只传入一个参数，与FindShortestSeparator不同的是，该类没有limit参数，在实际的代码中，首先找出key字符串中第一个不为0xff的字符，并将该字符加1，然后丢弃后面的所有字符。例如，对于字符串"abcd"，由于第一个字符a不等于0xff，那么最短的后继字符串为"a"+1，即"b"。