Databases Reference
In-Depth Information
Figure 2.1
B+tree configuration (order four, height three).
Example: Determine the Order and Height of a B+tree
To determine the order of a B+tree, let us assume that the database has 500,000 rows of
200 bytes each, the search key is 15 bytes, the tree and data pointers are 5 bytes, and the
index node (and data block size) is 1,024 bytes. For this configuration we have
×
×
Nonleaf index node size = 1,024 bytes =
p
5 + (
p
- 1)
15 bytes.
Solving for the order of the B+tree,
p
, we get:
p
= floor((1,024 + 15)/20) = floor(51.95) = 51,
2.1
where the floor function is the next lower whole number, found by truncating the actual
value to the next lower integer. Therefore, we can have up to
p
- 1 or 50 search key val-
ues in each nonleaf index node. In the leaf index nodes there are 15 bytes for the search
key value and 5 bytes for the data pointer. Each leaf index node has a single pointer to
the next leaf index node to make a scan of the data rows possible without going through
the index-level nodes. In this example the number of search key values in the leaf nodes
is floor ((1,024 - 5)/(15 + 5)) = 50, which is the same number of search key values in
the nonleaf nodes as well.
The height
h
of a B+tree is the number of index levels, including the leaf nodes. It is
computed by noting that the root index node (
i
th level) has
p
pointers, the
i
-1st level
has
p
2
tree pointers,
i
-2nd level has
p
3
tree pointers, and so on. At the leaf level the
number of key entries and pointers is
p
- 1 per index node, but a good approximation
can be made by assuming that the leaf index nodes are implemented with
p
pointers and
