B樹(shù)是高度平衡的二叉搜索樹(shù)，進(jìn)行插入操作，要先獲取插入節(jié)點(diǎn)的位置，遵循節(jié)點(diǎn)比左子樹(shù)大，比右子樹(shù)小，在需要時(shí)拆分節(jié)點(diǎn)。
一圖看懂B樹(shù)插入操作原理
B樹(shù)插入算法
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登錄后復(fù)制
用Python實(shí)現(xiàn)B樹(shù)插入算法
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()登錄后復(fù)制
