leveldb前缀匹配查找Seek

个人随笔 (Owed by: 春夜喜雨 http://blog.csdn.net/chunyexiyu)
参考：https://github.com/google/leveldb/blob/main/include/leveldb/db.h
参考：百度AI

1. 背景

最近偶然发现了，leveldb前缀匹配查找的功能。
之前没有从这个角度去想过Seek方法，尝试使用之后，效率还是很好的。
另外今天使用关键词查找时，百度AI也给了一个很棒的例子。
时不我待，下面也谈一谈该技术点，以及这个技术点的背后支持，leveldb为此做的实现。

2. 前缀匹配需求

先说前缀查找的需求：
我们已知的是leveldb是一个KV数据库，KV数据提供的形如一个排序队列，按照key排序的队列；
当我们在leveldb库中存了许多的key与value值之后，某些时候，我们希望找出某个prefix开头的元素列表。

例如，我们存储了 公司名称key 到 公司简介value的 信息，我们希望查询公司名称 以"中国"开头的公司信息；
按照KV数据库的排序特点，在Key的排序队列中，缺省是字节比较，前缀相同的是存储到一块的，会和前缀不同的分开；
如果我们能查询到第一条前缀为"中国"的公司的key-value键值数据，往后继续查找，就能找到其它的数据了。

3. 技术实现

按照上述推断，如果我们用leveldb::Get()方法的话，是不可以的，
一方面是：当我们使用前缀查找时，是不知到排序第一条的公司名称；
另一方面是：Get方法直接提供的value数据，无法来找到下一条数据。

  // If the database contains an entry for "key" store the
  // corresponding value in *value and return OK.
  //
  // If there is no entry for "key" leave *value unchanged and return
  // a status for which Status::IsNotFound() returns true.
  //
  // May return some other Status on an error.
  virtual Status Get(const ReadOptions& options, const Slice& key,
                     std::string* value) = 0;

对于数据查找接口，就只剩余iterator接口了，iterator接口可以用于遍历leveldb的数据。
常用的方法是，先NewIterator，然后使用iter.SeekToFirst，之后使用Next遍历数据。
对于Iterator::Seed(const Slice& target)方法，在leveldb的内部Get方法中是有被使用到的。
同样的，这个Seek方法我们也可以直接调用使用，这个方法就是我们做前缀匹配的关键支持接口。

  // Return a heap-allocated iterator over the contents of the database.
  // The result of NewIterator() is initially invalid (caller must
  // call one of the Seek methods on the iterator before using it).
  //
  // Caller should delete the iterator when it is no longer needed.
  // The returned iterator should be deleted before this db is deleted.
  virtual Iterator* NewIterator(const ReadOptions& options) = 0;

class LEVELDB_EXPORT Iterator {
 public:
  Iterator();

  Iterator(const Iterator&) = delete;
  Iterator& operator=(const Iterator&) = delete;

  virtual ~Iterator();

  // An iterator is either positioned at a key/value pair, or
  // not valid.  This method returns true iff the iterator is valid.
  virtual bool Valid() const = 0;

  // Position at the first key in the source.  The iterator is Valid()
  // after this call iff the source is not empty.
  virtual void SeekToFirst() = 0;

  // Position at the last key in the source.  The iterator is
  // Valid() after this call iff the source is not empty.
  virtual void SeekToLast() = 0;

  // Position at the first key in the source that is at or past target.
  // The iterator is Valid() after this call iff the source contains
  // an entry that comes at or past target.
  virtual void Seek(const Slice& target) = 0;

  // Moves to the next entry in the source.  After this call, Valid() is
  // true iff the iterator was not positioned at the last entry in the source.
  // REQUIRES: Valid()
  virtual void Next() = 0;

  // Moves to the previous entry in the source.  After this call, Valid() is
  // true iff the iterator was not positioned at the first entry in source.
  // REQUIRES: Valid()
  virtual void Prev() = 0;
  ...
}

4. 技术理解

一般而言，对于经常使用std库的我们，可能会觉得Seek接口就和std库的find等接口类似，找一个元素，找到了返回元素，找不到了，返回指向末尾flag元素。
这点是一个思维误区了，我之前也有这个思维误区，我也缺省认为Seek就是查找元素用的，实际这样理解的不准确。
Seek所代表的是，在这个KV的排序队列上，找到一个>=TargetKey的元素后，然后停下来，Seek更多表达的是找到一个符合条件，停止下来的元素点。
所以Seek操作之后呢，并不是说iter.Valid()就查找到元素了，而是说iter.Valid()表达找到符合>=Tagetkey的这个点了。
如果要判定是否找到了，是==Tagetkey，需要Seek之后，再来判断一下。

  // Position at the first key in the source that is at or past target.
  // The iterator is Valid() after this call iff the source contains
  // an entry that comes at or past target.
  virtual void Seek(const Slice& target) = 0;

Seek的这种实现方式—[找到一个>=TargetKey的元素后，然后停下来]，就为我们做前缀匹配提供了功能支持。
前缀匹配，也就是找到符合前缀的第一个元素，方便我们沿着这个元素，继续找到剩余符合该前缀的所有元素。
在leveldb的内部存储里面，MemTable层(Mem与Imm)，提供了Iterato封装方法，各个level的SST持久化文件，也都封装提供了Iterator方法，通过这些内存存储的包装，提供了总体的leveldb数据遍历查找Iterator方法。通过Seek方法，让Iterator指向第一个符合>=Targetkey的元素，来最终让Iterator指向这个排序key-value对列的首个符合条件的元素，之后附加后续的prefix比对，就可以支持前缀查找。

5. 附：样例代码

下面附一段，由百度AI生成的leveldb前缀匹配样例代码，这段代码生动演示了前缀匹配实现。

这段代码
首先，打开了一个LevelDB数据库，然后写入了一些带有不同前缀的键值对。
接着，它使用了一个迭代器来进行前缀匹配查询，并打印出所有匹配的键值对。
最后，代码关闭了数据库并释放了相关资源。

#include <iostream>
#include <string>
#include "leveldb/db.h"
 
int main() {
    leveldb::DB* db;
    leveldb::Options options;
    options.create_if_missing = true;
    leveldb::Status status = leveldb::DB::Open(options, "./testdb", &db);
    if (!status.ok()) {
        std::cerr << "Error opening db: " << status.ToString() << std::endl;
        return -1;
    }
 
    // 写入一些数据
    status = db->Put(leveldb::WriteOptions(), "apple", "1");
    if (status.ok()) status = db->Put(leveldb::WriteOptions(), "applet", "2");
    if (status.ok()) status = db->Put(leveldb::WriteOptions(), "banana", "3");
    if (!status.ok()) {
        std::cerr << "Error writing to db: " << status.ToString() << std::endl;
        return -1;
    }
 
    // 进行前缀匹配查询
    std::string prefix = "app";
    leveldb::Iterator* it = db->NewIterator(leveldb::ReadOptions());
    for (it->Seek(prefix);
         it->Valid() && it->key().starts_with(prefix);
         it->Next()) {
        std::cout << it->key().ToString() << ": " << it->value().ToString() << std::endl;
    }
    delete it;
 
    // 关闭数据库
    delete db;
 
    return 0;
}

个人随笔 (Owed by: 春夜喜雨 http://blog.csdn.net/chunyexiyu)