B-tree ialah pokok carian binari yang sangat seimbang Untuk melakukan operasi sisipan, anda mesti mendapatkan kedudukan nod yang disisipkan terlebih dahulu untuk menjadi lebih besar daripada subpohon kiri dan lebih kecil daripada subpohon kanan apabila perlu.
<code>BreeInsertion(T, k)r root[T]if n[r] = 2t - 1<br/> s = AllocateNode()<br/> root[T] = s<br/> leaf[s] = FALSE<br/> n[s] <- 0<br/> c1[s] <- r<br/> BtreeSplitChild(s, 1, r)<br/> BtreeInsertNonFull(s, k)else BtreeInsertNonFull(r, k)BtreeInsertNonFull(x, k)i = n[x]if leaf[x]<br/> while i ≥ 1 and k < keyi[x]<br/> keyi+1 [x] = keyi[x]<br/> i = i - 1<br/> keyi+1[x] = k<br/> n[x] = n[x] + 1else while i ≥ 1 and k < keyi[x]<br/> i = i - 1<br/> i = i + 1<br/> if n[ci[x]] == 2t - 1<br/> BtreeSplitChild(x, i, ci[x])<br/> if k &rt; keyi[x]<br/> i = i + 1<br/> 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<br/> keyj[z] = keyj+t[y]if not leaf [y]<br/> for j = 1 to t<br/> cj[z] = cj + t[y]n[y] = t - 1for j = n[x] + 1 to i + 1<br/> cj+1[x] = cj[x]ci+1[x] = zfor j = n[x] to i<br/> keyj+1[x] = keyj[x]keyi[x] = keyt[y]n[x] = n[x] + 1</code>
<code>class BTreeNode:<br/> def __init__(self, leaf=False):<br/> self.leaf = leaf<br/> self.keys = []<br/> self.child = []<br/> <br/>class BTree:<br/> def __init__(self, t):<br/> self.root = BTreeNode(True)<br/> self.t = t<br/> <br/> def insert(self, k):<br/> root = self.root<br/> if len(root.keys) == (2 * self.t) - 1:<br/> temp = BTreeNode()<br/> self.root = temp<br/> temp.child.insert(0, root)<br/> self.split_child(temp, 0)<br/> self.insert_non_full(temp, k)<br/> else:<br/> self.insert_non_full(root, k)<br/> <br/> def insert_non_full(self, x, k):<br/> i = len(x.keys) - 1<br/> if x.leaf:<br/> x.keys.append((None, None))<br/> while i >= 0 and k[0] < x.keys[i][0]:<br/> x.keys[i + 1] = x.keys[i]<br/> i -= 1<br/> x.keys[i + 1] = k<br/> else:<br/> while i >= 0 and k[0] < x.keys[i][0]:<br/> i -= 1<br/> i += 1<br/> if len(x.child[i].keys) == (2 * self.t) - 1:<br/> self.split_child(x, i)<br/> if k[0] > x.keys[i][0]:<br/> i += 1<br/> self.insert_non_full(x.child[i], k)<br/> <br/> def split_child(self, x, i):<br/> t = self.t<br/> y = x.child[i]<br/> z = BTreeNode(y.leaf)<br/> x.child.insert(i + 1, z)<br/> x.keys.insert(i, y.keys[t - 1])<br/> z.keys = y.keys[t: (2 * t) - 1]<br/> y.keys = y.keys[0: t - 1]<br/> if not y.leaf:<br/> z.child = y.child[t: 2 * t]<br/> y.child = y.child[0: t - 1]<br/> <br/> def print_tree(self, x, l=0):<br/> print("Level ", l, " ", len(x.keys), end=":")<br/> for i in x.keys:<br/> print(i, end=" ")<br/> print()<br/> l += 1<br/> if len(x.child) > 0:<br/> for i in x.child:<br/> self.print_tree(i, l)<br/> <br/>def main():<br/> B = BTree(3)<br/> <br/> for i in range(10):<br/> B.insert((i, 2 * i))<br/> <br/> B.print_tree(B.root)<br/> <br/>if __name__ == '__main__':<br/> main()</code>
Atas ialah kandungan terperinci Gambar rajah prinsip pelaksanaan Python bagi algoritma sisipan B-tree. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!