使用Python实现B树插入操作的原理图解

B树是高度平衡的二叉搜索树，进行插入操作，要先获取插入节点的位置，遵循节点比左子树大，比右子树小，在需要时拆分节点。

一图看懂B树插入操作原理

B树插入算法

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

用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[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()