B-tree: insert: Difference between revisions
Jump to navigation
Jump to search
(Created page with "<code> B-TREE-INSERT(''T'', ''k'') 1 ''r'' = ''T.root'' 2 '''if''' ''r.n'' == 2''t'' - 1 3 ''s'' = ALLOCATE-NODE() 4 ''T.root'' = ''s'' 5 ''s.leaf''...") |
No edit summary |
||
| Line 1: | Line 1: | ||
== Pseudocode == | |||
<code> | <code> | ||
B-TREE-INSERT(''T'', ''k'') | B-TREE-INSERT(''T'', ''k'') | ||
| Line 11: | Line 13: | ||
9 B-TREE-INSERT-NONFULL(''s, k'') | 9 B-TREE-INSERT-NONFULL(''s, k'') | ||
10 '''else''' B-TREE-INSERT-NONFULL(''r, k'') | 10 '''else''' B-TREE-INSERT-NONFULL(''r, k'') | ||
</code> | |||
<code> | |||
B-TREE-INSERT-NONFULL(''x'', ''k'') | |||
1 ''i'' = ''x.n'' | |||
2 '''if''' ''x.leaf'' | |||
3 '''while''' ''i ≥ 1 and ''k'' < ''x.key''iiiii | |||
4 ''x.key''iii+111 = ''x.key''iiiii | |||
5 ''i'' = ''i'' - 1 | |||
6 ''x.key''iii+111 = ''k'' | |||
7 ''x.n'' = ''x.n'' + 1 | |||
8 DISK-WRITE(''x) | |||
9 '''else while''' ''i'' ≥ 1 and ''k'' < ''x.key''iiiii | |||
10 ''i'' = ''i'' - 1 | |||
11 ''i'' = ''i'' + 1 | |||
12 DISK-READ(''x.c''iiii) | |||
13 '''if''' ''x.ciiii.n'' == 2''t'' - 1 | |||
14 B-TREE-SPLIT-CHILD(''x, i'') | |||
15 '''if''' ''k'' > ''x.key''iiii | |||
16 ''i'' = ''i'' + 1 | |||
17 B-TREE-INSERT-NONFULL(''x.ciii, k) | |||
</code> | </code> | ||
Revision as of 16:07, 25 September 2014
Pseudocode
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)
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)