11 關於 b+tree (附 python 模擬代碼)
Python實戰-從菜鳥到大牛的進階之路 作者：極客學院 投票推薦 加入書簽 留言反饋
前幾天我寫了點 btree 的東西(http://thuhak.blog.51cto/2891595/1261783)，今天繼續這個思路，繼續寫 b+tree。
而且 b+tree 才是我的目的，更加深入理解文件和數據庫索引的基本原理。
在之前，我一直隻把 b+tree 當成是 btree 的一種變形，或者說是在某種情況下的一種優化，另外一些情況可能還是 btree 好些。但是做完之後才發現，b+tree 在各種情況都可以完全取代 btree，並能夠讓索引性能得到比 btree 更好的優化。因為 b+tree 設計的核心要點，是為了彌補 btree 最大的缺陷。
btree 最大的缺陷是什麽?
首先,我們知道對於 btree 和 b+tree 這種多路搜索樹來說，一個很重要的特點就是樹的度數非常大。因為隻有這樣才能夠降低樹的深度，減少磁盤讀取的次數。而樹的度數越大，葉子節點在樹中的比例就越大。假設度數為 1000，那麽葉子節點比他上一層內部節點的數量至少要多 1000 倍，在上一層就更加可以忽略不計了。可以說樹種 99.9% 的節點都是葉子節點。 但是對於 btree 來說，所有節點都是一樣的結構，都含有一定數量的數據和指向節點的指針。這兩項數據占據 btree 節點的幾乎全部的空間。一個節點內的數據的數量比硬盤指針的數量少一，可以說和指針的數量幾乎相等。對於 python 這種動態類型語言感覺不出來，但是對於 c 這種固定類型語言來說，即使這個 children list 數組為空，這個數組的空間也都是預留出去的。導致的結果就是占絕大多數的葉子節點的 children list 指針數組所占的磁盤空間完全浪費。
一個數據的大小和硬盤指針的大小取決於 key-value 中 key 和 value 大小的比值。假如說這個比值是 2:1。那麽 btree 浪費了幾乎 1/3 的空間。
b+tree 針對這個問題的，把葉子節點和內節點的數據結構分開設計，讓葉子節點不存放指針。因此同樣大小的葉子節點，b+tree 所能包含數據數量要比 btree 大。按照上麵的假設就是大 1/2。數的深度很可能比 btree 矮，大範圍搜索或遍曆所需要的載入磁盤的次數也少。
另外，b+tree 還有一個特點是所有數據都存放在葉子節點，這些葉子節點也可以組成一個鏈表，並把這個鏈表的表頭拿出來，方便直訪問數據。有些文章認為這對於範圍搜索來說是個巨大的優化。但是就我的看法，這個特性最大的作用僅僅是讓代碼更容易一些，性能上，隻會比樹的遍曆差，而不會比樹的遍曆好。因為不管是用指向葉子節點的指針搜，還是用樹的遍曆搜，所搜索的節點的數量都是幾乎相同的。在相同大小的範圍搜索的性能，隻取決於訪問順序的連續性。從樹根向下遍曆，那麽一次可以取得大量的子節點的範圍，並針對這些節點做訪問排序，得到更好的訪問連續性。如果是沿著指向兄弟節點的指針搜索，一是兄弟節點也許是後插入的，存放並不一定和自己是連續的，二是隻有每次從硬盤中將該節點載入到內存，才知道兄弟節點放在硬盤哪個位置，這又變成了對硬盤的一個隨機的同步操作，性能的下降可想而知。
說 b+tree 因為有指向兄弟節點的指針方便數據庫掃庫這種結論，是不正確的。
還是上代碼吧,依舊隻是在內存對數據結構插入刪除查找的模擬
be
#!/usr/bin/env pythonfrom random import randint,choicefrom bisect import bisect_right,bisect_leftfrom collections import dequess initerror(exception): passss paraerror(exception): passss keyvalue(object): __slots__=(\''key\'',\''value\'') def __init__(self,key,value):self.key=keyself.value=value def __str__(self):return str((self.key,self.value)) def __cmp__(self,key):if self.key>key: return 1elif self.key==key: return 0else: return -1ss bptree_internode(object): def __init__(self,m):if not isinstance(m,int): raise initerror,\''m must be int\''if m<=3: raise initerror,\''m must be greater then 3\''else: self.__m=m self.clist= self.ilist= self.par=none def isleaf(self):return false def isfull(self):return len(self.ilist)>=self.m-1 def isempty(self):return len(self.ilist)<=(self.m+1)/2-1 @property def m(self):return self.__mss bptree_leaf(object): def __init__(self,l):if not isinstance(l,int): raise initerror,\''l must be int\''else: self.__l=l self.vlist= self.bro=none self.par=none def isleaf(self):return true def isfull(self):return len(self.vlist)>self.l def isempty(self):return len(self.vlist)<=(self.l+1)/2 @property def l(self):return self.__lss bptree(object): def __init__(self,m,l):if l>m: raise initerror,\''l must be less or equal then m\''else: self.__m=m self.__l=l self.__root=bptree_leaf(l) self.__leaf=self.__root @property def m(self):return self.__m @property def l(self):return self.__l def insert(self,key_value):node=self.__rootdef split_node(n1): mid=self.m/2 newnode=bptree_internode(self.m) newnode.ilist=n1.ilist[mid:] newnode.clist=n1.clist[mid:] newnode.par=n1.par for c in newnode.clist:c.par=newnode if n1.par is none:newroot=bptree_internode(self.m)newroot.ilist=[n1.ilist[mid-1]]newroot.clist=[n1,newnode]n1.par=newnode.par=newrootself.__root=newroot else:i=n1.par.clist.index(n1)n1.par.ilist.insert(i,n1.ilist[mid-1])n1.par.clist.insert(i+1,newnode) n1.ilist=n1.ilist[:mid-1] n1.clist=n1.clist[:mid] return n1.pardef split_leaf(n2): mid=(self.l+1)/2 newleaf=bptree_leaf(self.l) newleaf.vlist=n2.vlist[mid:] if n2.par==none:newroot=bptree_internode(self.m)newroot.ilist=[n2.vlist[mid].key]newroot.clist=[n2,newleaf]n2.par=newleaf.par=newrootself.__root=newroot else:i=n2.par.clist.index(n2)n2.par.ilist.insert(i,n2.vlist[mid].key)n2.par.clist.insert(i+1,newleaf)newleaf.par=n2.par n2.vlist=n2.vlist[:mid] n2.bro=newleafdef insert_node(n): if not n.isleaf:if n.isfull: insert_node(split_node(n))else: p=bisect_right(n.ilist,key_value) insert_node(n.clist[p]) else:p=bisect_right(n.vlist,key_value)n.vlist.insert(p,key_value)if n.isfull: split_leaf(n)else: returninsert_node(node) def search(self,mi=none,ma=none):result=node=self.__rootleaf=self.__leafif mi is none and ma is none: raise paraerror,\''you need to setup searching range\''elif mi is not none and ma is not none and mi>ma: raise paraerror,\''upper bound must be greater or equal than lower bound\''def search_key(n,k): if n.isleaf:p=bisect_left(n.vlist,k)return (p,n) else:p=bisect_right(n.ilist,k)return search_key(n.clist[p],k)if mi is none: while true:for kv in leaf.vlist: if kv<=ma:result.append(kv) else:return resultif leaf.bro==none: return resultelse: leaf=leaf.broelif ma is none: index,leaf=search_key(node,mi) result.extend(leaf.vlist[index:]) while true:if leaf.bro==none: return resultelse: leaf=leaf.bro result.extend(leaf.vlist)else: if mi==ma:i,l=search_key(node,mi)try: if l.vlist[i]==mi:result.append(l.vlist[i])return result else:return resultexcept indexerror: return result else:i1,l1=search_key(node,mi)i2,l2=search_key(node,ma)if l1 is l2: if i1==i2:return result else:result.extend(l.vlist[i1:i2])return resultelse: result.extend(l1.vlist[i1:]) l=l1 while true:if l.bro==l2: result.extend(l2.vlist[:i2+1]) return resultelse: result.extend(l.bro.vlist) l=l.bro def traversal(self):result=l=self.__leafwhile true: result.extend(l.vlist) if l.bro==none:return result else:l=l.bro def show(self):print \''this b+tree is:n\''q=dequeh=0q.append([self.__root,h])while true: try:w,hei=q.popleft except indexerror:return else:if not w.isleaf: print w.ilist,\''the height is\'',hei if hei==h:h+=1 q.extend([[i,h] for i in w.clist])else: print [v.key for v in w.vlist],\''the leaf is,\'',hei def delete(self,key_value):def merge(n,i): if n.clist[i].isleaf:n.clist[i].vlist=n.clist[i].vlist+n.clist[i+1].vlistn.clist[i].bro=n.clist[i+1].bro else:n.clist[i].ilist=n.clist[i].ilist+[n.ilist[i]]+n.clist[i+1].ilistn.clist[i].clist=n.clist[i].clist+n.clist[i+1].clist n.clist.remove(n.clist[i+1]) n.ilist.remove(n.ilist[i]) if n.ilist==:n.clist[0].par=noneself.__root=n.clist[0]del nreturn self.__root else:return ndef tran_l2r(n,i): if not n.clist[i].isleaf:n.clist[i+1].clist.insert(0,n.clist[i].clist[-1])n.clist[i].clist[-1].par=n.clist[i+1]n.clist[i+1].ilist.insert(0,n.ilist[i])n.ilist[i]=n.clist[i].ilist[-1]n.clist[i].clist.popn.clist[i].ilist.pop else:n.clist[i+1].vlist.insert(0,n.clist[i].vlist[-1])n.clist[i].vlist.popn.ilist[i]=n.clist[i+1].vlist[0].keydef tran_r2l(n,i): if not n.clist[i].isleaf:n.clist[i].clist.append(n.clist[i+1].clist[0])n.clist[i+1].clist[0].par=n.clist[i]n.clist[i].ilist.append(n.ilist[i])n.ilist[i]=n.clist[i+1].ilist[0]n.clist[i+1].clist.remove(n.clist[i+1].clist[0])n.clist[i+1].ilist.remove(n.clist[i+1].ilist[0]) else:n.clist[i].vlist.append(n.clist[i+1].vlist[0])n.clist[i+1].vlist.remove(n.clist[i+1].vlist[0])n.ilist[i]=n.clist[i+1].vlist[0].keydef del_node(n,kv): if not n.isleaf:p=bisect_right(n.ilist,kv)if p==len(n.ilist): if not n.clist[p].isempty:return del_node(n.clist[p],kv) elif not n.clist[p-1].isempty:tran_l2r(n,p-1)return del_node(n.clist[p],kv) else:return del_node(merge(n,p),kv)else: if not n.clist[p].isempty:return del_node(n.clist[p],kv) elif not n.clist[p+1].isempty:tran_r2l(n,p)return del_node(n.clist[p],kv) else:return del_node(merge(n,p),kv) else:p=bisect_left(n.vlist,kv)try: pp=n.vlist[p]except indexerror: return -1else: if pp!=kv:return -1 else:n.vlist.remove(kv)return 0del_node(self.__root,key_value)def test: mini=2 maxi=60 testlist= for i in range(1,10):key=ivalue=itestlist.append(keyvalue(key,value)) mybptree=bptree(4,4) for kv in testlist:mybptree.insert(kv) mybptree.delete(testlist[0]) mybptree.show print \''nkey of this b+tree is n\'' print [kv.key for kv in mybptree.traversal] #print [kv.key for kv in mybptree.search(mini,maxi)]if __name__==\''__main__\'': test </pre>
實現過程和 btree 很像，不過有幾點顯著不同。 <ol><li>內節點不存儲 key-value，隻存放 key</li><li>沿著內節點搜索的時候，查到索引相等的數要向樹的右邊走。所以二分查找要選擇 bisect_right</li><li>在葉子節點滿的時候，並不是先分裂再插入而是先插入再分裂。因為 b+tree 無法保證分裂的兩個節點的大小都是相等的。在奇數大小的數據分裂的時候右邊的子節點會比左邊的大。如果先分裂再插入無法保證插入的節點一定會插在數量更少的子節點上，滿足節點數量平衡的條件。</li><li>在刪除數據的時候，b+tree 的左右子節點借數據的方式比 btree 更加簡單有效，隻把子節點的子樹直接剪切過來，再把索引變一下就行了，而且葉子節點的兄弟指針也不用動。</li></ol>
而且 b+tree 才是我的目的，更加深入理解文件和數據庫索引的基本原理。
在之前，我一直隻把 b+tree 當成是 btree 的一種變形，或者說是在某種情況下的一種優化，另外一些情況可能還是 btree 好些。但是做完之後才發現，b+tree 在各種情況都可以完全取代 btree，並能夠讓索引性能得到比 btree 更好的優化。因為 b+tree 設計的核心要點，是為了彌補 btree 最大的缺陷。
btree 最大的缺陷是什麽?
首先,我們知道對於 btree 和 b+tree 這種多路搜索樹來說，一個很重要的特點就是樹的度數非常大。因為隻有這樣才能夠降低樹的深度，減少磁盤讀取的次數。而樹的度數越大，葉子節點在樹中的比例就越大。假設度數為 1000，那麽葉子節點比他上一層內部節點的數量至少要多 1000 倍，在上一層就更加可以忽略不計了。可以說樹種 99.9% 的節點都是葉子節點。 但是對於 btree 來說，所有節點都是一樣的結構，都含有一定數量的數據和指向節點的指針。這兩項數據占據 btree 節點的幾乎全部的空間。一個節點內的數據的數量比硬盤指針的數量少一，可以說和指針的數量幾乎相等。對於 python 這種動態類型語言感覺不出來，但是對於 c 這種固定類型語言來說，即使這個 children list 數組為空，這個數組的空間也都是預留出去的。導致的結果就是占絕大多數的葉子節點的 children list 指針數組所占的磁盤空間完全浪費。
一個數據的大小和硬盤指針的大小取決於 key-value 中 key 和 value 大小的比值。假如說這個比值是 2:1。那麽 btree 浪費了幾乎 1/3 的空間。
b+tree 針對這個問題的，把葉子節點和內節點的數據結構分開設計，讓葉子節點不存放指針。因此同樣大小的葉子節點，b+tree 所能包含數據數量要比 btree 大。按照上麵的假設就是大 1/2。數的深度很可能比 btree 矮，大範圍搜索或遍曆所需要的載入磁盤的次數也少。
另外，b+tree 還有一個特點是所有數據都存放在葉子節點，這些葉子節點也可以組成一個鏈表，並把這個鏈表的表頭拿出來，方便直訪問數據。有些文章認為這對於範圍搜索來說是個巨大的優化。但是就我的看法，這個特性最大的作用僅僅是讓代碼更容易一些，性能上，隻會比樹的遍曆差，而不會比樹的遍曆好。因為不管是用指向葉子節點的指針搜，還是用樹的遍曆搜，所搜索的節點的數量都是幾乎相同的。在相同大小的範圍搜索的性能，隻取決於訪問順序的連續性。從樹根向下遍曆，那麽一次可以取得大量的子節點的範圍，並針對這些節點做訪問排序，得到更好的訪問連續性。如果是沿著指向兄弟節點的指針搜索，一是兄弟節點也許是後插入的，存放並不一定和自己是連續的，二是隻有每次從硬盤中將該節點載入到內存，才知道兄弟節點放在硬盤哪個位置，這又變成了對硬盤的一個隨機的同步操作，性能的下降可想而知。
說 b+tree 因為有指向兄弟節點的指針方便數據庫掃庫這種結論，是不正確的。
還是上代碼吧,依舊隻是在內存對數據結構插入刪除查找的模擬
be
#!/usr/bin/env pythonfrom random import randint,choicefrom bisect import bisect_right,bisect_leftfrom collections import dequess initerror(exception): passss paraerror(exception): passss keyvalue(object): __slots__=(\''key\'',\''value\'') def __init__(self,key,value):self.key=keyself.value=value def __str__(self):return str((self.key,self.value)) def __cmp__(self,key):if self.key>key: return 1elif self.key==key: return 0else: return -1ss bptree_internode(object): def __init__(self,m):if not isinstance(m,int): raise initerror,\''m must be int\''if m<=3: raise initerror,\''m must be greater then 3\''else: self.__m=m self.clist= self.ilist= self.par=none def isleaf(self):return false def isfull(self):return len(self.ilist)>=self.m-1 def isempty(self):return len(self.ilist)<=(self.m+1)/2-1 @property def m(self):return self.__mss bptree_leaf(object): def __init__(self,l):if not isinstance(l,int): raise initerror,\''l must be int\''else: self.__l=l self.vlist= self.bro=none self.par=none def isleaf(self):return true def isfull(self):return len(self.vlist)>self.l def isempty(self):return len(self.vlist)<=(self.l+1)/2 @property def l(self):return self.__lss bptree(object): def __init__(self,m,l):if l>m: raise initerror,\''l must be less or equal then m\''else: self.__m=m self.__l=l self.__root=bptree_leaf(l) self.__leaf=self.__root @property def m(self):return self.__m @property def l(self):return self.__l def insert(self,key_value):node=self.__rootdef split_node(n1): mid=self.m/2 newnode=bptree_internode(self.m) newnode.ilist=n1.ilist[mid:] newnode.clist=n1.clist[mid:] newnode.par=n1.par for c in newnode.clist:c.par=newnode if n1.par is none:newroot=bptree_internode(self.m)newroot.ilist=[n1.ilist[mid-1]]newroot.clist=[n1,newnode]n1.par=newnode.par=newrootself.__root=newroot else:i=n1.par.clist.index(n1)n1.par.ilist.insert(i,n1.ilist[mid-1])n1.par.clist.insert(i+1,newnode) n1.ilist=n1.ilist[:mid-1] n1.clist=n1.clist[:mid] return n1.pardef split_leaf(n2): mid=(self.l+1)/2 newleaf=bptree_leaf(self.l) newleaf.vlist=n2.vlist[mid:] if n2.par==none:newroot=bptree_internode(self.m)newroot.ilist=[n2.vlist[mid].key]newroot.clist=[n2,newleaf]n2.par=newleaf.par=newrootself.__root=newroot else:i=n2.par.clist.index(n2)n2.par.ilist.insert(i,n2.vlist[mid].key)n2.par.clist.insert(i+1,newleaf)newleaf.par=n2.par n2.vlist=n2.vlist[:mid] n2.bro=newleafdef insert_node(n): if not n.isleaf:if n.isfull: insert_node(split_node(n))else: p=bisect_right(n.ilist,key_value) insert_node(n.clist[p]) else:p=bisect_right(n.vlist,key_value)n.vlist.insert(p,key_value)if n.isfull: split_leaf(n)else: returninsert_node(node) def search(self,mi=none,ma=none):result=node=self.__rootleaf=self.__leafif mi is none and ma is none: raise paraerror,\''you need to setup searching range\''elif mi is not none and ma is not none and mi>ma: raise paraerror,\''upper bound must be greater or equal than lower bound\''def search_key(n,k): if n.isleaf:p=bisect_left(n.vlist,k)return (p,n) else:p=bisect_right(n.ilist,k)return search_key(n.clist[p],k)if mi is none: while true:for kv in leaf.vlist: if kv<=ma:result.append(kv) else:return resultif leaf.bro==none: return resultelse: leaf=leaf.broelif ma is none: index,leaf=search_key(node,mi) result.extend(leaf.vlist[index:]) while true:if leaf.bro==none: return resultelse: leaf=leaf.bro result.extend(leaf.vlist)else: if mi==ma:i,l=search_key(node,mi)try: if l.vlist[i]==mi:result.append(l.vlist[i])return result else:return resultexcept indexerror: return result else:i1,l1=search_key(node,mi)i2,l2=search_key(node,ma)if l1 is l2: if i1==i2:return result else:result.extend(l.vlist[i1:i2])return resultelse: result.extend(l1.vlist[i1:]) l=l1 while true:if l.bro==l2: result.extend(l2.vlist[:i2+1]) return resultelse: result.extend(l.bro.vlist) l=l.bro def traversal(self):result=l=self.__leafwhile true: result.extend(l.vlist) if l.bro==none:return result else:l=l.bro def show(self):print \''this b+tree is:n\''q=dequeh=0q.append([self.__root,h])while true: try:w,hei=q.popleft except indexerror:return else:if not w.isleaf: print w.ilist,\''the height is\'',hei if hei==h:h+=1 q.extend([[i,h] for i in w.clist])else: print [v.key for v in w.vlist],\''the leaf is,\'',hei def delete(self,key_value):def merge(n,i): if n.clist[i].isleaf:n.clist[i].vlist=n.clist[i].vlist+n.clist[i+1].vlistn.clist[i].bro=n.clist[i+1].bro else:n.clist[i].ilist=n.clist[i].ilist+[n.ilist[i]]+n.clist[i+1].ilistn.clist[i].clist=n.clist[i].clist+n.clist[i+1].clist n.clist.remove(n.clist[i+1]) n.ilist.remove(n.ilist[i]) if n.ilist==:n.clist[0].par=noneself.__root=n.clist[0]del nreturn self.__root else:return ndef tran_l2r(n,i): if not n.clist[i].isleaf:n.clist[i+1].clist.insert(0,n.clist[i].clist[-1])n.clist[i].clist[-1].par=n.clist[i+1]n.clist[i+1].ilist.insert(0,n.ilist[i])n.ilist[i]=n.clist[i].ilist[-1]n.clist[i].clist.popn.clist[i].ilist.pop else:n.clist[i+1].vlist.insert(0,n.clist[i].vlist[-1])n.clist[i].vlist.popn.ilist[i]=n.clist[i+1].vlist[0].keydef tran_r2l(n,i): if not n.clist[i].isleaf:n.clist[i].clist.append(n.clist[i+1].clist[0])n.clist[i+1].clist[0].par=n.clist[i]n.clist[i].ilist.append(n.ilist[i])n.ilist[i]=n.clist[i+1].ilist[0]n.clist[i+1].clist.remove(n.clist[i+1].clist[0])n.clist[i+1].ilist.remove(n.clist[i+1].ilist[0]) else:n.clist[i].vlist.append(n.clist[i+1].vlist[0])n.clist[i+1].vlist.remove(n.clist[i+1].vlist[0])n.ilist[i]=n.clist[i+1].vlist[0].keydef del_node(n,kv): if not n.isleaf:p=bisect_right(n.ilist,kv)if p==len(n.ilist): if not n.clist[p].isempty:return del_node(n.clist[p],kv) elif not n.clist[p-1].isempty:tran_l2r(n,p-1)return del_node(n.clist[p],kv) else:return del_node(merge(n,p),kv)else: if not n.clist[p].isempty:return del_node(n.clist[p],kv) elif not n.clist[p+1].isempty:tran_r2l(n,p)return del_node(n.clist[p],kv) else:return del_node(merge(n,p),kv) else:p=bisect_left(n.vlist,kv)try: pp=n.vlist[p]except indexerror: return -1else: if pp!=kv:return -1 else:n.vlist.remove(kv)return 0del_node(self.__root,key_value)def test: mini=2 maxi=60 testlist= for i in range(1,10):key=ivalue=itestlist.append(keyvalue(key,value)) mybptree=bptree(4,4) for kv in testlist:mybptree.insert(kv) mybptree.delete(testlist[0]) mybptree.show print \''nkey of this b+tree is n\'' print [kv.key for kv in mybptree.traversal] #print [kv.key for kv in mybptree.search(mini,maxi)]if __name__==\''__main__\'': test </pre>
實現過程和 btree 很像，不過有幾點顯著不同。 <ol><li>內節點不存儲 key-value，隻存放 key</li><li>沿著內節點搜索的時候，查到索引相等的數要向樹的右邊走。所以二分查找要選擇 bisect_right</li><li>在葉子節點滿的時候，並不是先分裂再插入而是先插入再分裂。因為 b+tree 無法保證分裂的兩個節點的大小都是相等的。在奇數大小的數據分裂的時候右邊的子節點會比左邊的大。如果先分裂再插入無法保證插入的節點一定會插在數量更少的子節點上，滿足節點數量平衡的條件。</li><li>在刪除數據的時候，b+tree 的左右子節點借數據的方式比 btree 更加簡單有效，隻把子節點的子樹直接剪切過來，再把索引變一下就行了，而且葉子節點的兄弟指針也不用動。</li></ol>