单盘kv数据的快速索引，支持读写接口。不支持更新和删除
- 对所有数据的key进行索引。每一个key存储在一个"index page"中
- kv index内部维护了以类似hash table的大hash表。
- hash表中的每一个entry维护了一组index page，即: "page group"
- page group中的第一个index page（内存page）缓存在内存中，后续index page（磁盘page）存储在磁盘中
- 引入bloom filter，加速判断key是否存在于磁盘page中。在内存空间不足以缓存所有key时，减少磁盘page的访问次数。
- page group中存在多个磁盘page时，采用并发异步的方式读取磁盘， 优化磁盘读取效率（这里此采用posix_fadvise的POSIX_FADV_WILLNEED功能实现）
- kv index的实现通过key查找存储数据的offset。用户通过这个offset读取对应的value。代码中提供DB类，对kv index进行封装，快速读取数据value
- 建议使用tcmalloc加速内存申请效率
- 对key进行hash，查找到对应的page group
- 找到page group中的最后一个page（之前的page都已经写满），在该page的末尾写入key的索引信息，
- 如果该page为磁盘page，将追加写入的信息写入磁盘（不修改现有磁盘数据，仅为追加）
- 如果page不足以容纳这个key，生成bloom filter，申请新的page写入
- 更新内存信息，如page的尾部位置
- 对key进行hash，查找到对应的page group
- 对page group中的所有page进行查找：
- 首先用bloom filter判断key是否存在于该page，不存在则跳过，存在则使用posix_fadvise的POSIX_FADV_WILLNEED，进行预读取，加入预读取队列
- 对预读取队列的page进行遍历，读取磁盘page到内存，并查找该key
- 返回查找到的key
在内存空间足够，可以缓存全部key时
- 索引的写入和读取都为内存操作。
在内存空间不足以缓存所有key时
- 索引的写入仅在磁盘page末尾追加一次写入操作。生成bloom filter时，由于不容易预先估计key的个数，因此需要读取一次磁盘page
- 索引的读取需要查找内存和磁盘page。利用bloom filter加速，并合理设置磁盘page的大小、个数，磁盘读取操作通常仅需要一次
// 初始化db
kvindex::DB* db;
kvindex::Options options;
options.mem_size = 1048576; // 内存page占用内存大小。在4G内存系统下，可以设置为2-3G左右
//"test.idx" 是kv index内部缓存磁盘page的缓存文件。
//"test.data" 是用户提供的数据文件，加载时使用。格式为|key_size(8byte)|key|value_size(8byte)|value|...
kvindex::ErrorCode code = kvindex::DB::Open("test.idx", "test.data", options, &db);
assert(kvindex::kOk == code);
// 测试读取key（该key已经存在于数据文件中）
char value[16];
code = db->Get("00002004", 8, value, 16);
assert(kvindex::kOk == code);
assert(0 == memcmp(value, "kv_value00002004", 16));
更多示例可以参考test目录下的文件
- 使用协程库（如：libco）提高程序的并发，提高磁盘的并发
- 提供一种hash page的方式：对key进行hash后，将hash存入index page，而不是存入整个key，使index page可以容纳更多的key，减少空间占用率。（需要额外解决hash冲突，对数据文件中记录的key与要读的key做进一步验证）
- 生成bloom filter时，由于不容易预先估计key的个数，因此需要读取一次磁盘page，可以根据场景提前确定优化