MySQL · myrocks · myrocks之Bloom filter

  1. 云栖社区>
  2. 阿里云数据库ApsaraDB>
  3. 博客>
  4. 正文

MySQL · myrocks · myrocks之Bloom filter

db匠 2017-09-21 09:00:06 浏览1725
展开阅读全文

Bloom filter 简介

Bloom filter用于判断一个元素是不是在一个集合里,当一个元素被加入集合时,通过k个散列函数将这个元素映射成一个位数组中的k个点,把它们置为1。检索时如果这些点有任何一个为0,则被检元素一定不在;如果都是1,则被检元素很可能在。这就是布隆过滤器的基本思想。
优点:布隆过滤器存储空间和插入/查询时间都是常数O(k)。
缺点:有一定的误算率,同时标准的Bloom Filter不支持删除操作。
Bloom Filter通过极少的错误换取了存储空间的极大节省。

bloom filter

设集合元素个数为n,数组大小为m, 散列函数个数为k

有一个规律是当 k=m/n*ln2 时,误算率最低。参考Bloom_filter wiki

rocksdb与bloom filter

rocksdb中memtable和SST file都属于集合类数

网友评论

登录后评论
0/500
评论