B-tree

A B-tree of $m$ is a balanced (http://planetmath.org/BalancedTree) search tree inwhich

• every node has at most $m$ children,

• every node, other than a root or leaf, has at least $m/2$ children,

• the root has at least 2 children if it is not a leaf,

• all leaf nodes appear on the same level

• a nonleaf node with $k$ children has $k-1$ keys.

If the tree has $n$ nodes its height is $O(lo{g}_2(n))$.