Java Reference
In-Depth Information
33
18
23
48
10 12 15
18 19 20 21 22
23
30 31
33 45 47
48 50 52
Figure10.18
Example of a B
+
-tree of order four. Internal nodes must store
between two and four children. For this example, the record size is assumed to be
such that leaf nodes store between three and five records.
node in a B
+
-tree of order m might have enough room to store more or less than
m records. The requirement is simply that the leaf nodes store enough records to
remain at least half full. The leaf nodes of a B
+
-tree are normally linked together
to form a doubly linked list. Thus, the entire collection of records can be traversed
in sorted order by visiting all the leaf nodes on the linked list. Here is a Java-like
pseudocode representation for the B
+
-tree node interface. Leaf node and internal
node subclasses would implement this interface.
/
**
InterfaceforB+Treenodes
*
/
publicinterfaceBPNode<Key,E>{
publicbooleanisLeaf();
publicintnumrecs();
publicKey[]keys();
}
An important implementation detail to note is that while Figure 10.17 shows
internal nodes containing three keys and four pointers, class
BPNode
is slightly
different in that it stores key/pointer pairs. Figure 10.17 shows the B
+
-tree as it
is traditionally drawn. To simplify implementation in practice, nodes really do
associate a key with each pointer. Each internal node should be assumed to hold
in the leftmost position an additional key that is less than or equal to any possible
key value in the node's leftmost subtree. B
+
-tree implementations typically store
an additional dummy record in the leftmost leaf node whose key value is less than
any legal key value.
B
+
-trees are exceptionally good for range queries. Once the first record in
the range has been found, the rest of the records with keys in the range can be
accessed by sequential processing of the remaining records in the first node, and
then continuing down the linked list of leaf nodes as far as necessary. Figure 10.18
illustrates the B
+
-tree.
Search in a B
+
-tree is nearly identical to search in a regular B-tree, except that
the search must always continue to the proper leaf node. Even if the search-key
value is found in an internal node, this is only a placeholder and does not provide
