Java Reference
In-Depth Information
33
18
23
48
101215
19 2021 22
23 30 31
33 45
47
48 50 52
Figure10.22
Simple deletion from a B
+
-tree. The record with key value 18 is
removed from the tree of Figure 10.18. Note that even though 18 is also a place-
holder used to direct search in the parent node, that value need not be removed
from internal nodes even if no record in the tree has key value 18. Thus, the
leftmost node at level one in this example retains the key with value 18 after the
record with key value 18 has been removed from the second leaf node.
33
19
23
48
101518
19 20 21 22
23 30 31
33 45 47
48 50 52
Figure10.23
Deletion from the B
+
-tree of Figure 10.18 via borrowing from a
sibling. The key with value 12 is deleted from the leftmost leaf, causing the record
with key value 18 to shift to the leftmost leaf to take its place. Note that the parent
must be updated to properly indicate the key range within the subtrees. In this
example, the parent node has its leftmost key value changed to 19.
records to contribute to the current node), and N has become less than half full
because it is under-flowing. This merge process combines two subtrees of the par-
ent, which might cause it to underflow in turn. If the last two children of the root
merge together, then the tree loses a level. Figure 10.24 illustrates the node-merge
deletion process. Figure 10.25 shows Java-like pseudocode for the B
+
-tree delete
algorithm.
The B
+
-tree requires that all nodes be at least half full (except for the root).
Thus, the storage utilization must be at least 50%. This is satisfactory for many
implementations, but note that keeping nodes fuller will result both in less space
required (because there is less empty space in the disk file) and in more efficient
processing (fewer blocks on average will be read into memory because the amount
of information in each block is greater). Because B-trees have become so popular,
many algorithm designers have tried to improve B-tree performance. One method
for doing so is to use the B
+
-tree variant known as the B
-tree. The B
-tree is
identical to the B
+
-tree, except for the rules used to split and merge nodes. Instead
of splitting a node in half when it overflows, the B
-tree gives some records to its
