SKEDSOFT

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 key₁[x] ≤ key₂[x] ≤ ··· ≤ key_n[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 c₁[x], c₂[x], ..., c_{n[x] 1}[x] to its children. Leaf nodes have no children, so their c_i fields are undefined.

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

   k₁ ≤ key₁[x] ≤ k₂ ≤ key₂[x] ≤··· ≤ key_n[x][x] ≤ k_{n[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.