B-tree: split: Difference between revisions
Jump to navigation
Jump to search
(Created page with "== Pseudocode == <code> B-TREE-SPLIT-CHILD(''x'', ''i'') 1 ''z'' = ALLOCATE-NODE() 2 ''y'' = ''x''.''c''iiiiiiiiiiiii 3 ''z''.''leaf'' = ''y.leaf'' 4 ''z.n'' = ''t'...") |
|||
| Line 11: | Line 11: | ||
7 '''if''' not ''y.leaf'' | 7 '''if''' not ''y.leaf'' | ||
8 '''for''' ''j'' = 1 to t | 8 '''for''' ''j'' = 1 to t | ||
9 | 9 ''z.c''jjjjj = ''y.c''jjjj+tttt | ||
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 | ||
| Line 17: | Line 17: | ||
13 ''x.c''iiii+1111 = ''z'' | 13 ''x.c''iiii+1111 = ''z'' | ||
14 '''for''' ''j'' = ''x.n'' '''downto''' ''i'' | 14 '''for''' ''j'' = ''x.n'' '''downto''' ''i'' | ||
15 | 15 ''x.key''iiii = ''y.key''jjjj | ||
16 ''x.key''iiii = ''y.key''ttttttt | 16 ''x.key''iiii = ''y.key''ttttttt | ||
17 ''x.n'' = ''x.n'' + 1 | 17 ''x.n'' = ''x.n'' + 1 | ||
Revision as of 17:23, 22 September 2014
Pseudocode
B-TREE-SPLIT-CHILD(x, i)
1 z = ALLOCATE-NODE()
2 y = x.ciiiiiiiiiiiii
3 z.leaf = y.leaf
4 z.n = t - 1
5 for j = 1 to t - 1
6 z.keyjjjjj = y.keyjjjjj+tttt
7 if not y.leaf
8 for j = 1 to t
9 z.cjjjjj = y.cjjjj+tttt
10 y.n = t - 1
11 for j = x.n + 1 downto i + 1
12 x.cjjjj+111 = x.cjjjj
13 x.ciiii+1111 = z
14 for j = x.n downto i
15 x.keyiiii = y.keyjjjj
16 x.keyiiii = y.keyttttttt
17 x.n = x.n + 1
18 DISK-WRITE(y)
19 DISK-WRITE(z)
20 DISK-WRITE(x)