B-tree: insert: Difference between revisions

From Algowiki
Jump to navigation Jump to search
No edit summary
Line 1: Line 1:
== Pseudocode ==  
== Pseudocode ==  


= B-TREE-INSERT(''T'',''k'') =
<code>
<code>
  B-TREE-INSERT(''T'', ''k'')
  B-TREE-INSERT(''T'',''k'')
   1 ''r'' = ''T.root''
   1 ''r'' = ''T.root''
   2 '''if''' ''r.n'' == 2''t'' - 1
   2 '''if''' ''r.n'' == 2''t'' - 1
Line 15: Line 16:
</code>
</code>


= B-TREE-INSERT-NONFULL(''x'',''k'') =
<code>
<code>
  B-TREE-INSERT-NONFULL(''x'', ''k'')
  B-TREE-INSERT-NONFULL(''x'',''k'')
   1 ''i'' = ''x.n''
   1 ''i'' = ''x.n''
   2 '''if''' ''x.leaf''
   2 '''if''' ''x.leaf''

Revision as of 17:44, 25 September 2014

Pseudocode

B-TREE-INSERT(T,k)

B-TREE-INSERT(T,k)
 1 r = T.root
 2 if r.n == 2t - 1
 3      s = ALLOCATE-NODE()
 4      T.root = s
 5      s.leaf = FALSE
 6      s.n = 0
 7      s.c1111 = r
 8      B-TREE-SPLIT-CHILD(s, 1)
 9      B-TREE-INSERT-NONFULL(s, k)
10 else B-TREE-INSERT-NONFULL(r, k)   

B-TREE-INSERT-NONFULL(x,k)

B-TREE-INSERT-NONFULL(x,k)
 1 i = x.n
 2 if x.leaf
 3      while i ≥ 1 and k < x.keyiiiii
 4              x.keyiii+111 = x.keyiiiii
 5              i = i - 1
 6      x.keyiii+111 = k
 7      x.n = x.n + 1
 8      DISK-WRITE(x)
 9 else while i ≥ 1 and k < x.keyiiiii
10             i = i - 1
11        i = i + 1
12        DISK-READ(x.ciiii)
13        if x.ciiii.n == 2t - 1
14               B-TREE-SPLIT-CHILD(x, i)
15               if k > x.keyiiii
16                       i = i + 1
17         B-TREE-INSERT-NONFULL(x.ciii, k)