key 比较函数接口 Comparator

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

class Slice;

class Comparator
{
public:
    virtual ~Comparator();
    
    // 比较 a 和 b 的 key 的大小，返回值代表3种比较结果：
    // 如果 "a" < "b"，则返回值 <0
    // 如果 "a" == "b"，则返回值 ==0
    // 如果 "a" > "b"，则返回值 >0
    virtual int Compare(const Slice &a, const Slice &b) const = 0;

    // 返回Comparator的名称
    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为接口，定义新的比较算法模块。在LevelDB中，有两个实现Comparator的类：

• 一个是BytewiseComparatorImpl
• 另一个则是InternalKeyComparator

Comparator 的难点在于理解 FindShortestSeparator 和 FindShortSuccessor。
这里我们以BytewiseComparatorImpl为例，BytewiseComparatorImpl是 LevelDB 中内置的默认比较器，主要采用字典序对两个字符串进行比较。

FindShortestSeparator 传入的参数是 *start 和 limit 这两个字符串。参数 *start 对应原字符串，经过一系列的逻辑处理之后，相应的短字符串也将保存在 *start 之中返回。

void FindShortestSeparator(std::string *start, const Slice &limit) const override
{
    // Find length of common prefix
    size_t min_length = std::min(start->size(), limit.size());
    size_t diff_index = 0;
    while ((diff_index < min_length) &&((*start)[diff_index] == limit[diff_index]))
    {
        diff_index++;
    }

    if (diff_index >= min_length)
    {
        // Do not shorten if one string is a prefix of the other
    }
    else
    {
        uint8_t diff_byte = static_cast<uint8_t>((*start)[diff_index]);
        if (diff_byte < static_cast<uint8_t>(0xff) &&
            diff_byte + 1 < static_cast<uint8_t>(limit[diff_index]))
        {
            (*start)[diff_index]++;
            start->resize(diff_index + 1);
            assert(Compare(*start, limit) < 0);
        }
    }
}

FindShortSuccessor 目的是找出key字符串中第一个不为0xff的字符，并将该字符+1，然后丢弃后面的所有字符。举例，对于字符串abcd，由于第一个字符不等于0xff，那么最短后继字符串为'a'+1，即为'b'

void FindShortSuccessor(std::string *key) const override
{
    size_t n = key->size();
    for (size_t i = 0; i < n; i++)
    {
        const uint8_t byte = (*key)[i];
        if (byte != static_cast<uint8_t>(0xff))
        {
            (*key)[i] = byte + 1;
            key->resize(i + 1);
            return;
        }
    }
}