Prinzipdiagramm der Python-Implementierung des B-Tree-Einfügungsalgorithmus

BreeInsertion(T, k)r root[T]if n[r] = 2t - 1
 s = AllocateNode()
 root[T] = s
 leaf[s] = FALSE
 n[s] <- 0
 c1[s] <- r
 BtreeSplitChild(s, 1, r)
 BtreeInsertNonFull(s, k)else BtreeInsertNonFull(r, k)BtreeInsertNonFull(x, k)i = n[x]if leaf[x]
 while i ≥ 1 and k < keyi[x]
 keyi+1 [x] = keyi[x]
 i = i - 1
 keyi+1[x] = k
 n[x] = n[x] + 1else while i ≥ 1 and k < keyi[x]
 i = i - 1
 i = i + 1
 if n[ci[x]] == 2t - 1
 BtreeSplitChild(x, i, ci[x])
 if k &rt; keyi[x]
 i = i + 1
 BtreeInsertNonFull(ci[x], k)BtreeSplitChild(x, i)BtreeSplitChild(x, i, y)z = AllocateNode()leaf[z] = leaf[y]n[z] = t - 1for j = 1 to t - 1
 keyj[z] = keyj+t[y]if not leaf [y]
 for j = 1 to t
 cj[z] = cj + t[y]n[y] = t - 1for j = n[x] + 1 to i + 1
 cj+1[x] = cj[x]ci+1[x] = zfor j = n[x] to i
 keyj+1[x] = keyj[x]keyi[x] = keyt[y]n[x] = n[x] + 1

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[i][0]:
 x.keys[i + 1] = x.keys[i]
 i -= 1
 x.keys[i + 1] = k
 else:
 while i >= 0 and k[0] < x.keys[i][0]:
 i -= 1
 i += 1
 if len(x.child[i].keys) == (2 * self.t) - 1:
 self.split_child(x, i)
 if k[0] > x.keys[i][0]:
 i += 1
 self.insert_non_full(x.child[i], k)
 
 def split_child(self, x, i):
 t = self.t
 y = x.child[i]
 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 main():
 B = BTree(3)
 
 for i in range(10):
 B.insert((i, 2 * i))
 
 B.print_tree(B.root)
 
if __name__ == '__main__':
 main()