B-tree: split: Difference between revisions

From Algowiki
Jump to navigation Jump to search
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             ''z.c''jjjjj = ''y.c''jjjj+tttt
   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

Revision as of 17:24, 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)