B-tree: split: Difference between revisions

From Algowiki
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''iiiiiiiiiiiii
   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''jjjjj = ''y.key''jjjjj+tttt
   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''jjjjj = ''y.c''jjjj+tttt
   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''jjjj+111 = ''x.c''jjjj
  12          ''x.c''<sub>j + 1</sub> = ''x.c''<sub>j</sub>
  13 ''x.c''iiii+1111 = ''z''
  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''iiii = ''y.key''jjjj
  15          ''x.key''<sub>i</sub> = ''y.key''<sub>j</sub>
  16 ''x.key''iiii = ''y.key''ttttttt
  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)