B-tree: split

From Algowiki
Jump to: navigation, search

Pseudocode

B-TREE-SPLIT-CHILD(x, i)
 1 z = ALLOCATE-NODE()
 2 y = x.ci
 3 z.leaf = y.leaf
 4 z.n = t - 1
 5 for j = 1 to t - 1
 6           z.keyj = y.keyj + t
 7 if not y.leaf
 8          for j = 1 to t
 9              z.cj = y.cj + t
10 y.n = t - 1 
11 for j = x.n + 1 downto i + 1
12           x.cj + 1 = x.cj
13 x.ci + 1 = z
14 for j = x.n downto i
15           x.keyi = y.keyj
16 x.keyi = y.keyt
17 x.n = x.n + 1
18 DISK-WRITE(y)
19 DISK-WRITE(z)
20 DISK-WRITE(x)