在Google的Bigtable中，如果对key-value数据对进行写入或更新操作，实际上执行的都是写入操作。比如数据库中插入了这么几条记录：

张三 ：男

李四：女

王二麻子：男

如果接下来，用户张三进行了一个更新，把性别从‘男’改成了‘女’。那么数据库会变成什么样子呢?很自然的想法是，它会变成这样：

张三 ：女

李四：女

王二麻子：男

这样做逻辑上没有问题，但它会带来一个性能上的问题。因为这涉及到了硬盘的随机存取。当硬盘读写到王二麻子这条记录时，如果此时对张三的记录进行更新，计算机需要移动硬盘磁头进行寻道，在它把磁头移动到张三记录所在的位置后，它才能进一步进行写入操作。

在现代计算机系统中，磁头寻道时间是一个巨大的开销，相比内存和CPU而言，它的代价是昂贵的。于是，在系统设计时需要避免磁头频繁寻道这样的随机磁盘访问，用顺序磁盘访问来代替它。顺续磁盘访问就可以避免磁头寻道时间。在BigTable中，上述操作在数据表就类似这样：

张三 ：男  t1

李四：女   t2

王二麻子：男 t3

张三： 女  t4

它为每条记录打上了时间戳，对需要前面以往的记录进行修改时，它只是简单得顺序往里面添加了一条新记录，这样的顺序访问就避免了磁头往回寻道到前面某条记录的开销。这样读取张三的时候，需要系统扫描所有的数据库数据块把所有张三的记录读取出来，然后对其进行合并，根据时间戳选出最新的那个。比如我们读取张三，那么我们要扫描所有的数据块，会发现有2条记录：

张三：男 t1

张三：女 t4

然后我们对记录进行合并，比较版本，得到张三的性别是女。

然而，由于数据库的文件可能会被分成多个数据块，比如上面的例子，前2条放在数据块1中，后两条放在数据块2中，两个块文件都可能包含需要的记录（比如张三），那是否意味着我们需要对所有的块进行一个二叉树查找？我们需要一种手段来快速告诉我们某个数据块是否包含指定的关键字，从而告诉我们是否有进一步的必要来查找整个数据块。方法就是Bloom Filter（布隆算法）。

布隆算法的目的就是为了解决如果快速得知道某一个对象是否存在于一个对象集合中。这种方法有一定的误判率，他会把一些不属于这个集合的对象误判为属于这个集合，但是它绝不会漏判，对于属于这个集合的对象他一定能够判断正确。也就是说它倾向于“宁可错杀一千，不可放过一人”，这种倾向性的概率比较低，并且是可控的。

简单解释一下算法，算法其实很好理解。

所谓布隆过滤器，其实就是一个比特位图，每一位要么是0，要么是1。初始化的情况下，所有位都为0。布隆过滤器代表的就是对象集合，你可以把布隆过滤器理解为对象集合的指纹信息。

如何向对象集合中添加对象生成布隆过滤器呢？你先准备k个hash函数，对于每一个新添加过来的对象，这k个hash函数生成k个整数值，这个k个整数值代表k个位置，我们把布隆过滤器中相应的位置都设为1（不管原来这个位置的bit是0还是1，我们都把他设成1），也就是说有k个位会被置1。

经过上面不断得向集合中添加元素，我们得到了一个布隆过滤器。接下来就可以查询了。对于一个待查询的对象，我们也对它进行上述处理，用同样的k个hash生成代表k个位置的整数值，如果布隆过滤器中的这k个位置的值全部是1，那么就认为待查询对象已经被包含在布隆过滤器对应的对象集合中了，否则，则 认为对象集合还未包含此待查对象。

该算法有误判率，通过证明可以获得误判率的上限。