leveldb笔记之9:bloom filter
leveldb 的filter block用到了 filter policy，其中默认提供的是BloomFilterPolicy，即布隆过滤器，这篇笔记聊聊布隆过滤器的理论和在 leveldb 里的实现。
1. 简介
bloom filter是一种数据结构，作用类似于 hash table，相对于后者，空间利用率更高。
不过这种高利用率是有代价的，当我们在 bloom filter 查找 key 时，有返回两种情况：
key 不存在，那么 key 一定不存在。
key 存在，那么 key 可能存在。
也就是说 bloom filter 具有一定的误判率。
2. 理论知识
先介绍下 bloom filter 的几个组成：
n 个 key
m bits...
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，起到提前过滤...
226 post articles, 29 pages.