}
else
B-Tree-Insert-Nonfull(r, k) } B-Tree-Insert-Nonfull(x, k) { i = x.n if x.leaf while (i $\geqslant$ 1) && (k $<$ x.$key_i$) { x.$key_{i+1}$ = x.$key_i$ i = i - 1 } x.$key_{i+1}$ = k x.n = x.n + 1 Disk-Write(x) else { while (i $\geqslant$ 1) && (k < x.$key_i$) i = i - 1 i = i + 1 Disk-Read(x.$c_i$) if x.$c_i$.n == 2t - 1 { B-Tree-Split-Child(x, i) if k > x.$key_i$ i = i + 1 } B-Tree-Insert-Nonfull(x.$c_i$, k) }
}
