leveldb笔记之7:filter block
1. 简介
leveldb 里 sstable 文件里，有多个 block 组成。其中 filter block 用于提高 sstable 的读取效率，源码位于 filter_block.cc.
本文主要分析 filter block 的数据格式以及FilterBlockBuilder/FilterBlockReader类的实现。
2. 如何提高查找性能
在 leveldb 中，查找 data block使用二分法，能够达到 lg(n) 的复杂度，如果想进一步提高，就需要用到 filter block 了。
如果说 data block 的作用是查找 key 对应的 value，那么 filter block 则是查找 key 是否存在于该 data block，起到提前过滤...
leveldb笔记之3:skiplist实现
上篇笔记 skiplist 简介里从理论上介绍了 skiplist，本文对照 leveldb 的 C++ 源码看下 skiplist 的实现，同时介绍下 leveldb 里的实现技巧。
leveldb 在 MemTable 里使用 skiplist 高效的插入与查找数据。
typedef SkipList<const char*, KeyComparator> Table;
Table table_;
存储的数据类型为const char*，KeyComparator定义如下，主要起到比较 key 的作用：
struct KeyComparator {
const InternalKeyComparator comparator;
explic...
158 post articles, 20 pages.