B-tree: insert

Pseudocode

B-TREE-INSERT(T, k)
 1 r = T.root
 2 if r.n == 2t - 1
 3      s = ALLOCATE-NODE()
 4      T.root = s
 5      s.leaf = FALSE
 6      s.n = 0
 7      s.c1111 = r
 8      B-TREE-SPLIT-CHILD(s, 1)
 9      B-TREE-INSERT-NONFULL(s, k)
10 else B-TREE-INSERT-NONFULL(r, k)   

B-TREE-INSERT-NONFULL(x, k)
 1 i = x.n
 2 if x.leaf
 3      while i ≥ 1 and k < x.keyiiiii
 4              x.keyiii+111 = x.keyiiiii
 5              i = i - 1
 6      x.keyiii+111 = k
 7      x.n = x.n + 1
 8      DISK-WRITE(x)
 9 else while i ≥ 1 and k < x.keyiiiii
10             i = i - 1
11        i = i + 1
12        DISK-READ(x.ciiii)
13        if x.ciiii.n == 2t - 1
14               B-TREE-SPLIT-CHILD(x, i)
15               if k > x.keyiiii
16                       i = i + 1
17         B-TREE-INSERT-NONFULL(x.ciii, k)