Java Reference
In-Depth Information
4.
All nonleaf nodes (except the root) have between
⎡
M
/2
⎤
and
M
chil-
dren.
5.
All leaves are at the same depth and have between
⎡
L
/2
⎤
and
L
data
items, for some
L
(the determination of
L
is described shortly).
An example of a B-tree of order 5 is shown in Figure 19.84. Note that all
nonleaf nodes have between three and five children (and thus between two
and four keys); the root could possibly have only two children. Here,
L
= 5,
which means that
L
and
M
are the same in this example, but this condition is
not necessary. Because
L
is 5, each leaf has between three and five data items.
Requiring nodes to be half full guarantees that the B-tree does not degenerate
into a simple binary tree. Various definitions of B-trees change this structure,
mostly in minor ways, but the definition presented here is one of the most
commonly used.
Nodes must be half
full to guarantee
that the tree does
not degenerate into
a simple binary
tree.
Each node represents a disk block, so we choose
M
and
L
on the basis of the
size of the items being stored. Suppose that one block holds 8,192 bytes. In our
Florida example, each key uses 32 bytes, so in a B-tree of order
M,
we would
have
M
- 1 keys, for a total of 32
M
- 32 bytes plus
M
branches. Because each
branch is essentially a number of another disk block, we can assume that a
branch is 4 bytes. Thus the branches use 4
M
bytes, and the total memory
requirement for a nonleaf node is 36
M
- 32. The largest value of
M
for which
36
M
- 32 is no more than 8,192 is 228, so we would choose
M
= 228. As each
data record is 256 bytes, we would be able to fit 32 records in a block. Thus we
would choose
L
= 32. Each leaf has between 16 and 32 data records, and each
internal node (except the root) branches in at least 114 ways. For the 10,000,000
records, there are at most 625,000 leaves. Consequently, in the worst case,
leaves would be on level 4. In more concrete terms, the worst-case number of
accesses is given by approximately log
M
/2
N,
give or take 1.
We choose the
maximum
M
and
L
that allow a node to
fit in one disk block.
41
66
87
8
18
26
35
48
51
54
72
78
83
92
97
2
4
6
8
10
12
14
16
18
20
22
24
26
28
30
31
32
35
36
37
38
39
41
42
44
46
48
49
50
51
52
53
54
56
58
59
66
68
69
70
72
73
74
76
78
79
81
83
84
85
87
89
90
92
93
95
97
98
99
figure 19.84
A B-tree of order 5
Search WWH ::
Custom Search