有趣的bloom过滤器

设想以下的一个问题:有一个keyword的集合,我们需要快速判定某个keyword是否包含在其中。最简单的方法是遍历,但是效率很差。我们马上想到了hash的方法,因为在Oracle内部,hash无处不在。比如在cache buffer中找到某个block,在shared pool中找到某个SQL等等。我们可以把keyword的集合build成一个hash table,然后根据keyword计算hash值,通过是否落在相应的hash bucket中,这样就可以实现快速查找的目的。这个方法不错,但是当keyword过多时,hash table会占用大量内存,效率也会随之下降。

今天公司的架构师介绍了一个新的方法给我:Bloom Filter。它是一种基于随机数(或Hash)的数据结构,它支持对成员使用较少空间来存储,却能得到较高效率的查询。换句话说:在Bloom Filter 可以用于检索一个元素是否在一个集合中。其原理如下:

建立一个容量为500万的Bit Array结构(Bit Array的大小和keyword的数量决定了误判的几率),将集合中的每个keyword通过32个hash函数分别计算出32个数字,然后对这32个数字分别用500万取模,然后将Bit Array中对应的位置为1,我们将其称为特征值。简单的说就是将每个keyword对应到Bit Array中的32个位置上,见下图:

bloom

当需要快速查找某个keyword时,只要将其通过同样的32个hash函数运算,然后映射到Bit Array中的对应位,如果Bit Array中的对应位全部是1,那么说明该keyword匹配成功。

Bloom filter 是一个集合的有损编码,所以它不是一种“保险”的方案,存在一定的误判率。

有人问:这个对DBA有什么用?虽然我们不直接开发应用,但是开阔视野和思路对我们同样重要。难道我们碰到这种问题就只能用like或者in去解决吗?

–EOF–

后记:要深入了解Oracle,hash的原理和实现是必须要掌握的。有一次面试一个技术专家,高精尖的技术谈得头头是道,但是连hash的基本原理都说不清楚。对于一个技术专家来说,不能只懂“高精尖”,没有基础的知识,任何“高精尖”都只是空中楼阁,对于DBA,尤其如此。

觉得文章有用?立即: 和朋友一起 共学习 共进步!

猜您喜欢

发表评论

电子邮件地址不会被公开。 必填项已用 * 标注

*

您可以使用这些 HTML 标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>