Binary search trees - Data Structures and Problem Solving Using Java - page 757

occur, and the typical case is very close to log N . Thus a red-black tree would
use about 25 disk accesses on average, requiring 4 sec.

We want to reduce disk accesses to a very small constant number, such as three or
four. We are willing to write complicated code to do so because machine instructions
are essentially free, so long as we are not ridiculously unreasonable. A binary search
tree does not work because the typical red-black tree is close to optimal height, and
we cannot go below log N with a binary search tree. The solution is intuitively simple:
If we have more branching, we have less height. Thus, whereas a perfect binary tree
of 31 nodes has five levels, a 5-ary tree of 31 nodes has only three levels, as shown in
Figure 19.83. An M-ary search tree allows M -way branching, and as branching
increases, the depth decreases. Whereas a complete binary tree has height that is
roughly log 2 N, a complete M -ary tree has height that is roughly log M N .
We can create an M -ary search tree in much the same way we created a
binary search tree. In a binary search tree, we need one key to decide which of
two branches to take. In an M -ary search tree, we need M - 1 keys to decide
which branch to take. To make this scheme efficient in the worst case, we
need to ensure that the M -ary search tree is balanced in some way. Otherwise,
like a binary search tree, it could degenerate into a linked list. Actually, we
want an even more restrictive balancing condition. That is, we do not want an
M -ary search tree to degenerate to even a binary search tree because then we
would be stuck with log N accesses.
One way to implement this is to use a B-tree, which is the most popular
data structure for disk-bound searching. Here, we describe the basic B-tree; 3
many variations and improvements exist, and an implementation is somewhat
complex because quite a few cases must be addressed. However, in principle
this technique guarantees only a few disk accesses.

An M-ary search
tree allows M- way
branching. As
branching
increases, the
depth decreases.

The B-tree is the
most popular data
structure for disk-
bound searching.

A B-tree of order M is an M -ary tree with the following properties. 4

The B-tree has a
host of structure
properties.

1. The data items are stored at leaves.

2. The nonleaf nodes store as many as M - 1 keys to guide the search-

ing; key i represents the smallest key in subtree i + 1.

3. The root is either a leaf or has between 2 and M children.

figure 19.83
A 5-ary tree of 31
nodes has only three
levels

3. What we describe is popularly known as a B + -tree.

4. Properties 3 and 5 must be relaxed for the first L insertions. ( L is a parameter used in property 5.)