Python实现B树的详细解析

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。

由于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=t

def 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 i<len(x.keys)and k>x.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()