python实现b+树（⾃⽤笔记）
对于btree和b + tree这种多路搜索树来说，⼀个很重要的特点就是树的度数⾮常⼤。因为只有这样才能够降低树的深度，减少磁盘读取的次数。⽽树的度数越⼤，叶⼦节点在树中的⽐例就越⼤。假设度数为1000，那么叶⼦节点⽐他上⼀层内部节点的数量⾄少要多1000倍，在上⼀层就更加可以忽略不计了。可以说树种99.9％的节点都是叶⼦节点。但是对于btree来说，所有节点都是⼀样的结构，都含有⼀定数量的数据和指向节点的指针。这两项数据占据btree节点的⼏乎全部的空间。⼀个节点内的数据的数量⽐硬盘指针的数量少⼀，可以说和指针的数量⼏乎相等。对于python这种动态类型语⾔感觉不出来，但是对于C这种固定类型语⾔来说，即使这个孩⼦list数组为空，这个数组的空间也都是预留出去的。导致的结果就是占绝⼤多数的叶⼦ 点的孩⼦列表指针数组所占的磁盘空间完全浪费。
⼀个数据的⼤⼩和硬盘指针的⼤⼩取决于key-value中键和值⼤⼩的⽐值。假如说这个⽐值是2：1。那么btree浪费了⼏乎1/3的空间。
b + tree针对这个问题的，把叶⼦节点和内节点的数据结构分开设计，让叶⼦节点不存放指针。因此同样⼤⼩的叶⼦节点，b + tree所能包含数据数量要⽐btree⼤。按照上⾯的假设就是⼤1/2。数的深度很可能⽐btree矮，⼤范围搜索或遍历所需要的载⼊磁盘的次数也少。
另外，b + tree还有⼀个特点是所有数据都存放在叶⼦节点，这些叶⼦节点也可以组成⼀个链表，并把这
个链表的表头拿出来，⽅便直访问数据。有些⽂章认为这对于范围搜索来说是个巨⼤的优化。但是就我的看法，这个特性最⼤的作⽤仅仅是让代码更容易⼀些，性能上，只会⽐树的遍历差，⽽不会⽐树的遍历好。因为不管是⽤指向叶⼦节点的指针搜，还是⽤树的遍历搜，所搜索的节点的数量都是⼏乎相同的。在相同⼤⼩的范围搜索的性能，只取决于访问顺序的连续性。从树根向下遍历，那么⼀次可以取得⼤量的⼦节点的范围，并针对这些节点做访问排序，得到更好的访问连续性。如果是沿着指向兄弟节点的指针搜索，⼀是兄弟节点也许是后插⼊的，存放并不⼀定和⾃⼰是连续的，⼆是只有每次从硬盘中将该节点载⼊到内存，才知道兄弟节点放在硬盘 哪个位置，这⼜变成了对硬盘的⼀个随机的同步操作，性能的下降可想⽽知。
说b + tree因为有指向兄弟节点的指针⽅便数据库扫库这种结论，是不正确的。
还是上代码吧，依旧只是在内存对数据结构插⼊删除查找的模拟
from random import randint,choice
from bict import bict_right,bict_left
from collections import deque
class InitError(Exception):
pass
class ParaError(Exception):
pass
class KeyValue(object):
__slots__=('key','value')
def __init__(lf,key,value):
lf.key=key
lf.value=value
def __str__(lf):
return str((lf.key,lf.value))
def __cmp__(lf,key):
if lf.key>key:
return 1
elif lf.key==key:
return 0
el:
return -1
class Bptree_InterNode(object):
def __init__(lf,M):
if not isinstance(M,int):
rai InitError,'M must be int'
if M<=3:
rai InitError,'M must be greater then 3'
el:
lf.__M=M
lf.clist=[]
lf.ilist=[]
lf.par=None
def isleaf(lf):
return Fal
def isfull(lf):
return len(lf.ilist)>=lf.M-1
def impty(lf):
def impty(lf):
return len(lf.ilist)<=(lf.M+1)/2-1
@property
def M(lf):
return lf.__M
class Bptree_Leaf(object):
def __init__(lf,L):
if not isinstance(L,int):
rai InitError,'L must be int'
el:
lf.__L=L
lf.vlist=[]
lf.bro=None
lf.par=None
def isleaf(lf):
return True
def isfull(lf):
return len(lf.vlist)>lf.L
def impty(lf):
return len(lf.vlist)<=(lf.L+1)/2
@property
def L(lf):
return lf.__L
class Bptree(object):
def __init__(lf,M,L):
if L>M:
rai InitError,'L must be less or equal then M' el:
lf.__M=M
lf.__L=L
lf.__root=Bptree_Leaf(L)
lf.__leaf=lf.__root
@property
def M(lf):
return lf.__M
@property
def L(lf):
return lf.__L
def inrt(lf,key_value):
node=lf.__root
def split_node(n1):
mid=lf.M/2
newnode=Bptree_InterNode(lf.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(lf.M)
newroot.ilist=[n1.ilist[mid-1]]
newroot.clist=[n1,newnode]
n1.par=newnode.par=newroot
lf.__root=newroot
el:
i=n1.par.clist.index(n1)
n1.par.ilist.inrt(i,n1.ilist[mid-1])
n1.par.clist.inrt(i+1,newnode)
n1.ilist=n1.ilist[:mid-1]
n1.clist=n1.clist[:mid]
return n1.par
def split_leaf(n2):
mid=(lf.L+1)/2
newleaf=Bptree_Leaf(lf.L)
newleaf.vlist=n2.vlist[mid:]
if n2.par==None:
if n2.par==None:
newroot=Bptree_InterNode(lf.M)
newroot.ilist=[n2.vlist[mid].key]
newroot.clist=[n2,newleaf]
n2.par=newleaf.par=newroot
lf.__root=newroot
el:
i=n2.par.clist.index(n2)
n2.par.ilist.inrt(i,n2.vlist[mid].key)
n2.par.clist.inrt(i+1,newleaf)
newleaf.par=n2.par
n2.vlist=n2.vlist[:mid]
n2.bro=newleaf
def inrt_node(n):
if not n.isleaf():
if n.isfull():
inrt_node(split_node(n))
el:
p=bict_right(n.ilist,key_value)
inrt_node(n.clist[p])
el:
p=bict_right(n.vlist,key_value)
n.vlist.inrt(p,key_value)
if n.isfull():
split_leaf(n)
el:
return
inrt_node(node)
def arch(lf,mi=None,ma=None):
result=[]
node=lf.__root
leaf=lf.__leaf
if mi is None and ma is None:
rai ParaError,'you need to tup arching range'
elif mi is not None and ma is not None and mi>ma:
rai ParaError,'upper bound must be greater or equal than lower bound' def arch_key(n,k):
if n.isleaf():
p=bict_left(n.vlist,k)
return (p,n)
el:
p=bict_right(n.ilist,k)
return arch_key(n.clist[p],k)
if mi is None:
while True:
for kv in leaf.vlist:
if kv<=ma:
result.append(kv)
el:
return result
if leaf.bro==None:
return result
el:
leaf=leaf.bro
elif ma is None:
index,leaf=arch_key(node,mi)
while True:
if leaf.bro==None:
return result
el:
leaf=leaf.bro
el:
if mi==ma:
i,l=arch_key(node,mi)
i,l=arch_key(node,mi)
try:
if l.vlist[i]==mi:
result.append(l.vlist[i])
return result
el:
return result
except IndexError:
return result
el:
i1,l1=arch_key(node,mi)
i2,l2=arch_key(node,ma)
if l1 is l2:
if i1==i2:
return result
el:
return result
el:
l=l1
while True:
if l.bro==l2:
return result
el:
l=l.bro
def traversal(lf):
result=[]
l=lf.__leaf
while True:
if l.bro==None:
return result
el:
l=l.bro
def show(lf):
print 'this b+tree is:\n'
q=deque()
h=0
q.append([lf.__root,h])
while True:
try:
w,hei=q.popleft()
except IndexError:
return
el:
if not w.isleaf():
print w.ilist,'the height is',hei
if hei==h:
h+=1
el:
print [v.key for v in w.vlist],'the leaf is,',hei
def delete(lf,key_value):
def merge(n,i):
if n.clist[i].isleaf():
n.clist[i].vlist=n.clist[i].vlist+n.clist[i+1].vlist
n.clist[i].bro=n.clist[i+1].bro
el:
n.clist[i].ilist=n.clist[i].ilist+[n.ilist[i]]+n.clist[i+1].ilist n.clist[i].clist=n.clist[i].clist+n.clist[i+1].clist
ve(n.clist[i+1])
ve(n.ilist[i])
ve(n.ilist[i])
if n.ilist==[]:
n.clist[0].par=None
lf.__root=n.clist[0]
del n
return lf.__root
el:
return n
def tran_l2r(n,i):
if not n.clist[i].isleaf():
n.clist[i+1].clist.inrt(0,n.clist[i].clist[-1]) n.clist[i].clist[-1].par=n.clist[i+1]
n.clist[i+1].ilist.inrt(0,n.ilist[i])
n.ilist[i]=n.clist[i].ilist[-1]
n.clist[i].clist.pop()
n.clist[i].ilist.pop()
el:
n.clist[i+1].vlist.inrt(0,n.clist[i].vlist[-1]) n.clist[i].vlist.pop()
n.ilist[i]=n.clist[i+1].vlist[0].key
def 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].ve(n.clist[i+1].clist[0]) n.clist[i+1].ve(n.clist[i+1].ilist[0]) el:
n.clist[i].vlist.append(n.clist[i+1].vlist[0]) n.clist[i+1].ve(n.clist[i+1].vlist[0]) n.ilist[i]=n.clist[i+1].vlist[0].key
def del_node(n,kv):
if not n.isleaf():
p=bict_right(n.ilist,kv)
if p==len(n.ilist):
if not n.clist[p].impty():
return del_node(n.clist[p],kv)
elif not n.clist[p-1].impty():
tran_l2r(n,p-1)
return del_node(n.clist[p],kv)
el:
return del_node(merge(n,p),kv)
el:
if not n.clist[p].impty():
return del_node(n.clist[p],kv)
elif not n.clist[p+1].impty():
tran_r2l(n,p)
return del_node(n.clist[p],kv)
el:
return del_node(merge(n,p),kv)
el:
p=bict_left(n.vlist,kv)
try:
pp=n.vlist[p]
except IndexError:
return -1
el:
if pp!=kv:
return -1
el:
ve(kv)
return 0
del_node(lf.__root,key_value)
def test():
mini=2
