Java Reference
In-Depth Information
33
1012 233348
10
12
23
33
48
50
(A)
(B)
18
33
48
1012
15
18 20 2123 31
33 45 47
48 50
52
(C)
33
18
23
48
10
12
15
18 20 21
23 30 31
33 45 47
48 50 52
(D)
Figure10.20
Examples of B
+
-tree insertion. (a) A B
+
-tree containing five
records. (b) The result of inserting a record with key value 50 into the tree of (a).
The leaf node splits, causing creation of the first internal node. (c) The B
+
-tree of
(b) after further insertions. (d) The result of inserting a record with key value 30
into the tree of (c). The second leaf node splits, which causes the internal node to
split in turn, creating a new root.
privateBPNode<Key,E>inserthelp(BPNode<Key,E>rt,
Keyk,Ee){
BPNode<Key,E>retval;
if(rt.isLeaf())//Atleafnode:inserthere
return((BPLeaf<Key,E>)rt).add(k,e);
//Addtointernalnode
intcurrec=binaryle(rt.keys(),rt.numrecs(),k);
BPNode<Key,E>temp=inserthelp(
((BPInternal<Key,E>)root).pointers(currec),k,e);
if(temp!=((BPInternal<Key,E>)rt).pointers(currec))
return((BPInternal<Key,E>)rt).
add((BPInternal<Key,E>)temp);
else
returnrt;
}
Figure10.21
A Java-like pseudocode sketch of the B
+
-tree insert algorithm.
