5.4.1 Definition of B-Trees

A B-tree of order m is an m-ary search tree with the following properties:

• The root is either a leaf or has at least two children
• Each node, except for the root and the leaves, has between $\lceil$m/2$\rceil$ and m children
• Each path from the root to a leaf has the same length.
• The root, each internal node, and each leaf is typically a disk block.
• Each internal node has up to (m - 1) key values and up to m pointers (to children)
• The records are typically stored in leaves (in some organizations, they are also stored in internal nodes)


Figure 5.26 shows a B-tree of order 5 in which at most 3 records fit into a leaf block .
 
 

Figure 5.26: An example of a B-tree


• A B-tree can be viewed as a hierarchical index in which the root is the first level index.
• Each non-leaf node is of the form 

                                        (p₁, k₁, p₂, k₂,..., k_{m - 1}, p_m)

where

p_i

is a pointer to the i^th child, 1 $\leq$i $\leq$m

k_i

Key values, 1 $\leq$i $\leq$m - 1, which are in the sorted order, k₁ < k₂ < ^... < k_{m - 1}, such that

• all keys in the subtree pointed to by p₁ are less than k₁
• For 2 $\leq$i $\leq$m - 1, all keys in the subtree pointed to by p_i are greater than or equal to k_{i - 1} and less than k_i
• All keys in the subtree pointed to by p_m are greater than (or equal to) k_{m - 1}

Figure 5.27: Insertion and deletion in B-trees: An example