Java Reference
In-Depth Information
24
15
20
33 45 48
10
12
18
21 23
30 31
38
47
50 52 60
Figure10.17
A B-tree of order four.
A B-tree of order m is defined to have the following shape properties:
• The root is either a leaf or has at least two children.
• Each internal node, except for the root, has between dm=2e and m children.
• All leaves are at the same level in the tree, so the tree is always height bal-
anced.
The B-tree is a generalization of the 2-3 tree. Put another way, a 2-3 tree is a
B-tree of order three. Normally, the size of a node in the B-tree is chosen to fill a
disk block. A B-tree node implementation typically allows 100 or more children.
Thus, a B-tree node is equivalent to a disk block, and a “pointer” value stored
in the tree is actually the number of the block containing the child node (usually
interpreted as an offset from the beginning of the corresponding disk file). In a
typical application, the B-tree's access to the disk file will be managed using a
buffer pool and a block-replacement scheme such as LRU (see Section 8.3).
Figure 10.17 shows a B-tree of order four. Each node contains up to three keys,
and internal nodes have up to four children.
Search in a B-tree is a generalization of search in a 2-3 tree. It is an alternating
two-step process, beginning with the root node of the B-tree.
1. Perform a binary search on the records in the current node. If a record with
the search key is found, then return that record. If the current node is a leaf
node and the key is not found, then report an unsuccessful search.
2. Otherwise, follow the proper branch and repeat the process.
For example, consider a search for the record with key value 47 in the tree of
Figure 10.17. The root node is examined and the second (right) branch taken. After
examining the node at level 1, the third branch is taken to the next level to arrive at
the leaf node containing a record with key value 47.
B-tree insertion is a generalization of 2-3 tree insertion. The first step is to find
the leaf node that should contain the key to be inserted, space permitting. If there
is room in this node, then insert the key. If there is not, then split the node into two
and promote the middle key to the parent. If the parent becomes full, then it is split
in turn, and its middle key promoted.
