LevelDB源码｜Block的索引设计

本文从Block索引原理介绍，收束至函数 FindShortSuccessor

为什么需要Block索引

假设一个SSTable里有大量数据：

apple
banana
cat
dog
elephant
fox
grape ...

LevelDB 不会把所有数据都当成一个巨大的连续块来查，而是分成多个 Block：

SSTable

┌─────────────────┐
│ Data Block 1    │
│ apple           │
│ banana          │
│ cat             │
└─────────────────┘

┌─────────────────┐
│ Data Block 2    │
│ dog             │
│ elephant        │
│ fox             │
└─────────────────┘

┌─────────────────┐
│ Data Block 3    │
│ grape           │
│ orange          │
│ zoo             │
└─────────────────┘

那么查询一个data首先就要知道它在哪个Block。

朴素的索引方式与索引查找

假设每个Block使用自己最后一个（即最大的）key作为索引key：

Text

Data Block 1 → cat
Data Block 2 → fox
Data Block 3 → zoo

形成索引Block：

Text

Index Block

cat ─────→ Block 1
fox ─────→ Block 2
zoo ─────→ Block 3

当我们 Get(“elephant”):

在 Index Block 中寻找：第一个大于等于 elephant 的 Index Key。
cat < elephant, fox >= elephant，所以找到Block2

然后读取 Block2 找到 elephant。

内存压缩

LevelDB 并不会原样使用 Data Block 的最后一个 key（那样 key 可能很长，Index Block 会变大）。

它会调用 comparator 的 FindShortestSeparator(last_key, next_first_key)，生成最短的分隔字符串作为索引 key。这样可以显著减小 Index Block 的体积（Index Block 通常需要常驻内存）。

void FindShortestSeparator(std::string* start,
                             const Slice& limit) const override {
    // 找公共前缀
    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) {
      // 不存在介于 start 和 limit 之间且更短的 key
    } 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

当构建 SSTable 到最后一个 Data Block 时（没有下一个 Block 提供 first key）：

中间 Block 用 FindShortestSeparator(last_key, next_first_key) 生成最短分隔键。
最后一个 Block 在 TableBuilder::Finish() 中改为调用：options.comparator->FindShortSuccessor(&last_key);然后把处理后的 last_key + BlockHandle 写入 Index Block。

FindShortSuccessor 的作用：

生成一个较短的字符串，且满足 新 key ≥ 原 last_key。
简单实现可以直接保持原 key 不变（也正确）。
目的是尽量缩短索引 key，减小 Index Block 体积。

void FindShortSuccessor(std::string* key) const override {
    // Find first character that can be incremented
    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;
      }
    }
  }

总结

索引 key 只需满足 ≥ 该 Data Block 内所有 key。
查找逻辑统一：在 Index 中找第一个 index_key ≥ target 的条目即可定位到对应 Data Block。