Scalable Bloom Filter(SBF)的设计过程：
1. 首先将一个简单的BBF看成是SBF[0]={n0,m,k}，其对应的错误率为f0.
2. 计算满足错误率小于f0的前提下，BBF能够存储多少个元素.
3. 当数据增多时，新的SBF1被加到SBF中，其大小为m1=2*m.
4. 当n>3*n0时，另一个新的SBF2被加入到SBF中，其大小为m2=4*m.
5. 当SBF增加了i次，既n>(2^i-1)*n0时，一个新的SBFi被加到SBF后面，其大小为mi=(2^i)*m.
定理1：经过i次拓展后，SBF能够容纳的元素个数为=(2^(i+1))*n0
证明：根据误判率f的计算公式
得到元素个数n的计算公式如下，同时根据第一次拓展后添加的SBF1={n1,m1,k}，其中的m1=2*m，进而得到n1和n0之间的关系如下：
依次得到ni=(2^i)*n0，从而对n0到ni进行求和计算得到其总共的元素个数=(2^(i+1))*n0，下面给出应用DBF和BBF之间的性能对比：
Example1：在数据量持续增长的情况下对比DBF和SBF的表现：
他们都是从BBF{n,m,k}演化而来，其中的m=16，k=2，同时给定f0=0.155，进而得到
由于n0必须是整数，我们设n0=4，现在假设a,b,c,d,e,f,g,h,i连续进入数据集中，DBF和SBF的处理方式分别如下，可以看到DBF和SBF都用了48位来表示这9个元素，但是SBF用了两个数组，DBF用了三个数组，相比之下SBF由于用的数组少，所以它能够表示更多的元素，同时它的错误率也更低(证明过程请参看原文)。
SBF的元素插入过程
1. 插入一个元素之前，进行如下的公式验证，其中的c是SBF所容纳的元素个数
2. 如果上述公式成立，那么生成SBF[i+1]，同时计算k个hash函数对SBF[i+1]进行置位，用c+1替换现有的c，用i+1替换现有的i.
3. 如果公式不成立，那么生成k个hash函数来对SBFi进行置位
定理2： 为了代表一个含有n个元素的数据集，SBF需要拓展i次，包含L个SBF数组，其中的最后一个SBFi代表t个元素，整个SBF占据了MSBF位，对应的误判率为fSBF。
证明：
根据上面的推导可知，需要表示n个元素，它需要满足如下的公式，其中的i为需要的SBF拓展次数
进而得到如果要表达n个元素，那么需要拓展的次数i的表示如下：
容易看出，在经过i次拓展之后，SBF数组的大小变为L=i+1=[log2(n/n0+1)]+1，那么SBF整体需要占用的位大小为：
需要注意的是，SBFj表示了（2^j）*n0个元素，这当然除了最后一个SBF表示的t个元素之外，t=n-n0（2^j-1），前j个SBF中的错误率f的求法如下：
最后的t个元素在最后一个SBF中表示，其错误率如下：
进而得到整体的SBF的错误率如下：
再根据上面推导出的i等公式，进而得到定理中fSBF的最终表达式。
SBF Element Query过程如下：
1. 当我们对某个元素做一次查询时
2. 计算k个hash函数，判断SBFj中的k个位置是否都为1
3. 如果是，那么在SBFj中能够找到这个元素
4. 如果不是，那么SBFj中没有这个元素的表示，此时必须检查SBFj-1中是否有这个元素，j=j-1，然后再返回到第2步，直到j=-1。
很明显，从SBF中查询一个元素在最坏的情况下需要查找所有i+1个SBF，这样一来就需要进行k(i+1)=k([log2(n/n0+1)]+1)次hash计算。
参考文献：
原文：A Scalable Bloom Filter for Membership Queries Kun Xie, etc. IEEE GLOBECOM 2007
图片出处：http://www.docin.com/p-905966302.html