B-tree: insert: Difference between revisions
Jump to navigation
Jump to search
| Line 23: | Line 23: | ||
1 ''i'' = ''x.n'' | 1 ''i'' = ''x.n'' | ||
2 '''if''' ''x.leaf'' | 2 '''if''' ''x.leaf'' | ||
3 '''while''' ''i ≥ 1 and ''k'' < ''x.key'' | 3 '''while''' ''i ≥ 1 and ''k'' < ''x.key''<sub>i</sub> | ||
4 ''x.key'' | 4 ''x.key''<sub>i+1</sub>= ''x.key''<sub>i</sub> | ||
5 ''i'' = ''i'' - 1 | 5 ''i'' = ''i'' - 1 | ||
6 ''x.key'' | 6 ''x.key''<sub>i</sub>+111 = ''k'' | ||
7 ''x.n'' = ''x.n'' + 1 | 7 ''x.n'' = ''x.n'' + 1 | ||
8 DISK-WRITE(''x) | 8 DISK-WRITE(''x) | ||
9 '''else while''' ''i'' ≥ 1 and ''k'' < ''x.key'' | 9 '''else while''' ''i'' ≥ 1 and ''k'' < ''x.key''<sub>i</sub> | ||
10 ''i'' = ''i'' - 1 | 10 ''i'' = ''i'' - 1 | ||
11 ''i'' = ''i'' + 1 | 11 ''i'' = ''i'' + 1 | ||
12 DISK-READ(''x.c'' | 12 DISK-READ(''x.c''<sub>i</sub>) | ||
13 '''if''' ''x. | 13 '''if''' ''x.c<sub>i</sub>.n'' == 2''t'' - 1 | ||
14 B-TREE-SPLIT-CHILD(''x, i'') | 14 B-TREE-SPLIT-CHILD(''x, i'') | ||
15 '''if''' ''k'' > ''x.key'' | 15 '''if''' ''k'' > ''x.key''<sub>i</sub> | ||
16 ''i'' = ''i'' + 1 | 16 ''i'' = ''i'' + 1 | ||
17 B-TREE-INSERT-NONFULL(''x. | 17 B-TREE-INSERT-NONFULL(''x.c<sub>i</sub>, k) | ||
</code> | </code> | ||
Revision as of 20:23, 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.c1 = 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.keyi
4 x.keyi+1= x.keyi
5 i = i - 1
6 x.keyi+111 = k
7 x.n = x.n + 1
8 DISK-WRITE(x)
9 else while i ≥ 1 and k < x.keyi
10 i = i - 1
11 i = i + 1
12 DISK-READ(x.ci)
13 if x.ci.n == 2t - 1
14 B-TREE-SPLIT-CHILD(x, i)
15 if k > x.keyi
16 i = i + 1
17 B-TREE-INSERT-NONFULL(x.ci, k)