B-tree挿入アルゴリズムのPython実装の原理図

<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>