深入解析B树算法及其Python实现

B树，和二叉搜索树很像，每个节点可以包含多个节点，但B树的子节点可以超过两个。

B树数据结构

B树可以在单个节点中存储许多键，并且可以有多个子节点。

B树搜索算法

BtreeSearch(x,k)  i=1  while i≤n[x]and k≥keyi[x]      do i=i+1  if i n[x]and k=keyi[x]      then return(x,i)  if leaf[x]      then return NIL  else      return BtreeSearch(ci[x],k)

B树搜索示例

指定K=17，从根节点开始，将k与根进行比较。

ķ>11，转到根的右子节点；比较k和16，因为>16，比较k和下一个键18。

算家云

高效、便捷的人工智能算力服务平台

37 查看详情

立即学习“Python免费学习笔记（深入）”；

由于k<18，k介于16和18之间。在16的右子节点或18左子节点中搜索，k被发现。

Python实现B树

class BTreeNode:   def __init__(self,leaf=False):   self.leaf=leaf   self.keys=[]   self.child=[]class BTree:   def __init__(self,t):   self.root=BTreeNode(True)   self.t=tdef insert(self,k):   root=self.root   if len(root.keys)==(2*self.t)-1:      temp=BTreeNode()      self.root=temp      temp.child.insert(0,root)      self.split_child(temp,0)      self.insert_non_full(temp,k)   else:      self.insert_non_full(root,k)def insert_non_full(self,x,k):   i=len(x.keys)-1   if x.leaf:      x.keys.append((None,None))      while i>=0 and k[0]<x.keys[0]:         x.keys[i+1]=x.keys         i-=1      x.keys[i+1]=k   else:      while i>=0 and k[0]<x.keys[0]:      i-=1      i+=1   if len(x.child.keys)==(2*self.t)-1:      self.split_child(x,i)   if k[0]>x.keys[0]:      i+=1   self.insert_non_full(x.child,k)def split_child(self,x,i):   t=self.t   y=x.child   z=BTreeNode(y.leaf)   x.child.insert(i+1,z)   x.keys.insert(i,y.keys[t-1])   z.keys=y.keys[t:(2*t)-1]   y.keys=y.keys[0:t-1]   if not y.leaf:      z.child=y.child[t:2*t]      y.child=y.child[0:t-1]def print_tree(self,x,l=0):   print("Level",l,"",len(x.keys),end=":")   for i in x.keys:   print(i,end="")   print()   l+=1   if len(x.child)>0:      for i in x.child:         self.print_tree(i,l)def search_key(self,k,x=None):   if x is not None:      i=0      while ix.keys[0]:      i+=1   if i<len(x.keys)and k==x.keys[0]:      return(x,i)   elif x.leaf:      return None   else:      return self.search_key(k,x.child)   else:      return self.search_key(k,self.root)def main():   B=BTree(3)   for i in range(10):        B.insert((i,2*i))   B.print_tree(B.root)   if B.search_key(8)is not None:      print("nFound")   else:      print("nNot Found")if __name__=='__main__':   main()