Java Reference
In-Depth Information
privateEfindhelp(BPNode<Key,E>rt,Keyk){
intcurrec=binaryle(rt.keys(),rt.numrecs(),k);
if(rt.isLeaf())
if((((BPLeaf<Key,E>)rt).keys())[currec]==k)
return((BPLeaf<Key,E>)rt).recs(currec);
elsereturnnull;
else
returnfindhelp(((BPInternal<Key,E>)rt).
pointers(currec),k);
}
Figure10.19
Implementation for the B
+
-tree search method.
access to the actual record. To find a record with key value 33 in the B
+
-tree of
Figure 10.18, search begins at the root. The value 33 stored in the root merely
serves as a placeholder, indicating that keys with values greater than or equal to 33
are found in the second subtree. From the second child of the root, the first branch
is taken to reach the leaf node containing the actual record (or a pointer to the actual
record) with key value 33. Figure 10.19 shows a pseudocode sketch of the B
+
-tree
search algorithm.
B
+
-tree insertion is similar to B-tree insertion. First, the leaf L that should
contain the record is found. If L is not full, then the new record is added, and no
other B
+
-tree nodes are affected. If L is already full, split it in two (dividing the
records evenly among the two nodes) and promote a copy of the least-valued key
in the newly formed right node. As with the 2-3 tree, promotion might cause the
parent to split in turn, perhaps eventually leading to splitting the root and causing
the B
+
-tree to gain a new level. B
+
-tree insertion keeps all leaf nodes at equal
depth. Figure 10.20 illustrates the insertion process through several examples. Fig-
ure 10.21 shows a Java-like pseudocode sketch of the B
+
-tree insert algorithm.
To delete record R from the B
+
-tree, first locate the leaf L that contains R. If L
is more than half full, then we need only remove R, leaving L still at least half full.
This is demonstrated by Figure 10.22.
If deleting a record reduces the number of records in the node below the min-
imum threshold (called an underflow), then we must do something to keep the
node sufficiently full. The first choice is to look at the node's adjacent siblings to
determine if they have a spare record that can be used to fill the gap. If so, then
enough records are transferred from the sibling so that both nodes have about the
same number of records. This is done so as to delay as long as possible the next
time when a delete causes this node to underflow again. This process might require
that the parent node has its placeholder key value revised to reflect the true first key
value in each node. Figure 10.23 illustrates the process.
If neither sibling can lend a record to the under-full node (call it N), then N
must give its records to a sibling and be removed from the tree. There is certainly
room to do this, because the sibling is at most half full (remember that it had no
