key比较接口Comparator

LevelDB是按照key排序后进行存储的，所以必然少不了对key的比较。因此提供了一个用于key比较的接口，可以让用户自定义排序方法的实现。

Comparator是一个纯虚类：

class Comparator {
public:
    virtual ~Comparator();
    // 比较a和b的key值的大小
    virtual int Compare(const Slice& a, const Slice& b) const = 0;
    // 返回比较器的名称，用于检测比较器的一致性。不同的比较方法名称要不同
    virtual const char* Name() const = 0;
    // 如果start<limit，返回一个短的字符串，这个字符串在start<=string<limit之间。主要是为了压缩字符串的存储空间。
    virtual void FindShortestSeparator(std::string* start, const Slice& limit) const = 0;
    // 返回一个较短的字符串string， string>=key，同样是为了减少字符串的存储空间。
    virtual void FindShortSuccessor(std::string* key) const = 0;
};

LevelDB有两个内置的Comparator的实现类：一个是BytewiseComparatorImpl，另一个是InternalKeyComparator。

BytewiseComparatorImpl是默认的比较器。采用字典序进行比较。需要注意的是FindShortestSeparator与FindShortSuccessor这两个方法。

BytewiseComparatorImpl中FindShortestSeparator的算法逻辑如下：

1. 找出两个字符串start与limit的公共前缀。如果没有公共前缀则直接退出。
2. 有公共前缀，判断公共前缀的后一个字符（不属于公共前缀） 是否小于0xff，且后一个字符加1要小于limit公共前缀的后一个字符，不满足直接退出。其实就是找到start ⇐ string < limit。
3. 将start中公共前缀的后一个字符+1，然后去掉后续所有字符并返回退出。 假设有start = “abcd”, limit=“abzf”。ab是公共前缀，那么c+1 要小于z，那么就可以返回abd了。

FindShortSuccessor是找到最短的后继字符串。也就是找到第一个不为0xff的字符，然后该字符+1，丢弃后面的字符串并返回即可。就是说给定字符串”abcd”，那么a就是第一个不为0xff的字符，所以后继字符串就是b。

使用BytewiseComparator()函数就可以获取默认的这个比较器了。而实际上这是获取程序中单例的一个函数。其实现如下：

const Comparator* BytewiseComparator() {
  static NoDestructor<BytewiseComparatorImpl> singleton;
  return singleton.get();
}

可以在单例工具类中了解一下实现。