18.1 Definition of B-trees

| < Day Day Up > |

## 18.1 Definition of B-trees

To keep things simple, we assume, as we have for binary search trees and red-black trees, that any "satellite information" associated with a key is stored in the same node as the key. In practice, one might actually store with each key just a pointer to another disk page containing the satellite information for that key. The pseudocode in this chapter implicitly assumes that the satellite information associated with a key, or the pointer to such satellite information, travels with the key whenever the key is moved from node to node. A common variant on a B-tree, known as a B+- tree, stores all the satellite information in the leaves and stores only keys and child pointers in the internal nodes, thus maximizing the branching factor of the internal nodes.

A B-tree T is a rooted tree (whose root is root[T]) having the following properties:

1. Every node x has the following fields:

   1. n[x], the number of keys currently stored in node x,

   2. the n[x] keys themselves, stored in nondecreasing order, so that key1[x] ≤ key2[x] ≤ ··· ≤ keyn[x][x],

   3. leaf [x], a boolean value that is TRUE if x is a leaf and FALSE if x is an internal node.

2. Each internal node x also contains n[x]+ 1 pointers c1[x], c2[x], ..., cn[x]+1[x] to its children. Leaf nodes have no children, so their ci fields are undefined.

3. The keys keyi[x] separate the ranges of keys stored in each subtree: if ki is any key stored in the subtree with root ci [x], then

   k1 ≤ key1[x] ≤ k2 ≤ key2[x] ≤··· ≤ keyn[x][x] ≤ kn[x]+1.

4. All leaves have the same depth, which is the tree's height h.

5. There are lower and upper bounds on the number of keys a node can contain. These bounds can be expressed in terms of a fixed integer t ≥ 2 called the minimum degree of the B-tree:

   1. Every node other than the root must have at least t - 1 keys. Every internal node other than the root thus has at least t children. If the tree is nonempty, the root must have at least one key.

   2. Every node can contain at most 2t - 1 keys. Therefore, an internal node can have at most 2t children. We say that a node is full if it contains exactly 2t - 1 keys.[1]

The simplest B-tree occurs when t = 2. Every internal node then has either 2, 3, or 4 children, and we have a 2-3-4 tree. In practice, however, much larger values of t are typically used.

#### The height of a B-tree

The number of disk accesses required for most operations on a B-tree is proportional to the height of the B-tree. We now analyze the worst-case height of a B-tree.

Theorem 18.1

If n ≥ 1, then for any n-key B-tree T of height h and minimum degree t ≥ 2,

Proof If a B-tree has height h, the root contains at least one key and all other nodes contain at least t - 1 keys. Thus, there are at least 2 nodes at depth 1, at least 2t nodes at depth 2, at least 2t2 nodes at depth 3, and so on, until at depth h there are at least 2th-1 nodes. Figure 18.4 illustrates such a tree for h = 3. Thus, the number n of keys satisfies the inequality

Figure 18.4: A B-tree of height 3 containing a minimum possible number of keys. Shown inside each node x is n[x].

By simple algebra, we get th ≤ (n + 1)/2. Taking base-t logarithms of both sides proves the theorem.

Here we see the power of B-trees, as compared to red-black trees. Although the height of the tree grows as O(lg n) in both cases (recall that t is a constant), for B-trees the base of the logarithm can be many times larger. Thus, B-trees save a factor of about lg t over red-black trees in the number of nodes examined for most tree operations. Since examining an arbitrary node in a tree usually requires a disk access, the number of disk accesses is substantially reduced.

Exercises 18.1-1

Why don't we allow a minimum degree of t = 1?

Exercises 18.1-2

For what values of t is the tree of Figure 18.1 a legal B-tree?

Exercises 18.1-3

Show all legal B-trees of minimum degree 2 that represent {1, 2, 3, 4, 5}.

Exercises 18.1-4

As a function of the minimum degree t, what is the maximum number of keys that can be stored in a B-tree of height h?

Exercises 18.1-5

Describe the data structure that would result if each black node in a red-black tree were to absorb its red children, incorporating their children with its own.

[1]Another common variant on a B-tree, known as a B*-tree, requires each internal node to be at least 2/3 full, rather than at least half full, as a B-tree requires.

| < Day Day Up > |