B-tree: split: Difference between revisions
Jump to navigation
Jump to search
| Line 4: | Line 4: | ||
B-TREE-SPLIT-CHILD(''x'', ''i'') | B-TREE-SPLIT-CHILD(''x'', ''i'') | ||
1 ''z'' = ALLOCATE-NODE() | 1 ''z'' = ALLOCATE-NODE() | ||
2 ''y'' = ''x''.''c'' | 2 ''y'' = ''x''.''c''<sub>i</sub> | ||
3 ''z''.''leaf'' = ''y.leaf'' | 3 ''z''.''leaf'' = ''y.leaf'' | ||
4 ''z.n'' = ''t'' - 1 | 4 ''z.n'' = ''t'' - 1 | ||
5 '''for''' ''j'' = 1 '''to''' ''t'' - 1 | 5 '''for''' ''j'' = 1 '''to''' ''t'' - 1 | ||
6 ''z.key'' | 6 ''z.key''<sub>j</sub> = ''y.key''<sub>j + t</sub> | ||
7 '''if''' not ''y.leaf'' | 7 '''if''' not ''y.leaf'' | ||
8 '''for''' ''j'' = 1 to t | 8 '''for''' ''j'' = 1 to t | ||
9 ''z.c'' | 9 ''z.c''<sub>j</sub> = ''y.c''<sub>j + t</sub> | ||
10 ''y.n'' = ''t'' - 1 | 10 ''y.n'' = ''t'' - 1 | ||
11 '''for''' ''j'' = ''x.n'' + 1 '''downto''' ''i'' + 1 | 11 '''for''' ''j'' = ''x.n'' + 1 '''downto''' ''i'' + 1 | ||
12 ''x.c'' | 12 ''x.c''<sub>j + 1</sub> = ''x.c''<sub>j</sub> | ||
13 ''x.c'' | 13 ''x.c''<sub>i + 1</sub> = ''z'' | ||
14 '''for''' ''j'' = ''x.n'' '''downto''' ''i'' | 14 '''for''' ''j'' = ''x.n'' '''downto''' ''i'' | ||
15 ''x.key'' | 15 ''x.key''<sub>i</sub> = ''y.key''<sub>j</sub> | ||
16 ''x.key'' | 16 ''x.key''<sub>i</sub> = ''y.key''<sub>t</sub> | ||
17 ''x.n'' = ''x.n'' + 1 | 17 ''x.n'' = ''x.n'' + 1 | ||
18 DISK-WRITE(''y'') | 18 DISK-WRITE(''y'') | ||
Revision as of 20:25, 25 September 2014
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)