Properties of the B tree

Properties of the B-tree

• Each page holds between k and 2k keys (index elements) except the root page which may hold between 1 and 2k keys.

• Let the number of keys on a page P, which is not a leaf, be L. Then P has L+1 sons.

• Within each page P the keys are sequential in increasing order: x₁, x₂, ... x_L, where k <= L <= 2k except for the root page for which 1 <= L <= 2k.

• Furthermore, P contains (L + 1) pointers P₀, P₁ ... P_L to the sons of P. On leaf pages these pointers are undefined (i.e. null pointers).

• Let P(p_i) be the page to which P_i points, let K(P_i) be the set of keys on the pages of that maximal subtree of which P(P_i) is the root. Then for the B-trees considered here the following conditions shall always hold:

  1. for each y in K(p₀) y < x_i
  2. for each y in K(p_i) x_i < y < x_i+1 for i = 1,2,...,L-1
  3. for each y in K(p_L) x_L < y