5.4.5 Variants of B-Trees

B⁺-Trees

• Internal nodes contain the indices to the records corresponding to the key values k₁, k₂,..., k_m stored at the internal node. This obviates the need for repeating these key values and associated indices at the leaf level.
• More efficient than B-Trees in the case of successful searches.

B^*-Trees

• The minimum number of children at each internal node (except the root) is
  $$\left\lceil\vphantom{ \frac{2m}{3}}\right.$$$${\frac{2m}{3}}$$ $$\left.\vphantom{ \frac{2m}{3}}\right\rceil$$

• Pathlengths are smaller for obvious reasons
• Insertions and deletions are more complex.