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