papers of bloom filter
bloom filter 的相关论文较多，按照时间线整理了下自己觉得比较有意义的。有些观点没有找到佐证的中文资料，如有错误还请指出。
1. Space/Time Trade-offs in Hash Coding with Allowable Errors
Burton Bloom 在1970年发表的文章，布隆过滤器的开山之作。
给定一个 set，查找某个 key 是否存在于该 set，通常考虑两点：
time: 查找时间
space: 空间成本(例如 hash 目标区域大小)
Burton Bloom 在论文里提出了第三点：Allowable Fraction of Errors. ，即允许一定概率的误判，来获取空间成本的显著降低。
A Sample Appl...
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，起到提前过滤...
243 post articles, 31 pages.