Skip to content

Definition of the B tree

Jump to bottom
Zbigniew Romanowski edited this page Apr 11, 2018 · 1 revision

Definition of the B-tree

Let h >= 0 be an integer, and k a natural number. A directed tree T is in the class (k, h) of B-trees if T is either empty (i.e. h=0) or has the following properties:

  • Each path from the root to any leaf has the same length h, also called the height of T, i.e. h is eequal to the number of nodes in path.

  • Each node except the root and the leaves has at least (k + 1) sons. The root is a leaf or has at least two sons.

  • Each node has at most (2k + 1) sons.

Clone this wiki locally