前几天我写了点btree的东西(http://thuhak.blog.51cto.com/2891595/1261783)，今天继续这个思路，继续写b+tree。而且b+tree才是我的目的，更加深入理解文件和数
前几天我写了点btree的东西()，今天继续这个思路，继续写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因为有指向兄弟节点的指针方便数据库扫库这种结论，是不正确的。
还是上代码吧,依旧只是在内存对数据结构插入删除查找的模拟
#!/usr/bin/env pythonfrom random import randint,choicefrom bisect import bisect_right,bisect_leftfrom collections import dequeclass InitError(Exception):passclass ParaError(Exception):passclass KeyValue(object):__slots__=(‘key’,’value’)def __init__(self,key,value):self.key=keyself.value=valuedef __str__(self):return str((self.key,self.value))def __cmp__(self,key):if self.key>key:return 1elif self.key==key:return 0else:return -1class Bptree_InterNode(object):def __init__(self,M):if not isinstance(M,int):raise InitError,’M must be int’if M=self.M-1def isempty(self):return len(self.ilist)self.Ldef isempty(self):return len(self.vlist)M:raise InitError,’L must be less or equal then M’else:self.__M=Mself.__L=Lself.__root=Bptree_Leaf(L)self.__leaf=self.__root@propertydef M(self):return self.__M@propertydef L(self):return self.__Ldef insert(self,key_value):node=self.__rootdef split_node(n1):mid=self.M/2newnode=Bptree_InterNode(self.M)newnode.ilist=n1.ilist[mid:]newnode.clist=n1.clist[mid:]newnode.par=n1.parfor c in newnode.clist:c.par=newnodeif 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=newrootelse: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)/2newleaf=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=newrootelse: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.parn2.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 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.broresult.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 resultelse:return resultexcept IndexError:return resultelse:i1,l1=search_key(node,mi)i2,l2=search_key(node,ma)if l1 is l2:if i1==i2:return resultelse:result.extend(l.vlist[i1:i2])return resultelse:result.extend(l1.vlist[i1:])l=l1while True:if l.bro==l2:result.extend(l2.vlist[:i2+1])return resultelse:result.extend(l.bro.vlist)l=l.brodef traversal(self):result=[]l=self.__leafwhile True:result.extend(l.vlist)if l.bro==None:return resultelse:l=l.brodef show(self):print 'this b+tree is:\n'q=deque()h=0q.append([self.__root,h])while True:try:w,hei=q.popleft()except IndexError:returnelse:if not w.isleaf():print w.ilist,'the height is',heiif hei==h:h+=1q.extend([[i,h] for i in w.clist])else:print [v.key for v in w.vlist],'the leaf is,',heidef delete(self,key_value):def mer本文来源gao@daima#com搞(%代@#码@网2ge(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].broelse: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].clistn.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.__rootelse: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.pop()n.clist[i].ilist.pop()else:n.clist[i+1].vlist.insert(0,n.clist[i].vlist[-1])n.clist[i].vlist.pop()n.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 -1else:n.vlist.remove(kv)return 0del_node(self.__root,key_value)def test():mini=2maxi=60testlist=[]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()
实现过程和btree很像，不过有几点显著不同。
1.内节点不存储key-value，只存放key
2.沿着内节点搜索的时候，香港服务器租用，查到索引相等的数要向树的右边走。所以二分查找要选择bisect_right
转载请注明原文链接：关于B+tree (附python 模拟代码)
