# B-tree

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

• 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(log_{2}(n))$.

Title B-tree Btree 2013-03-22 17:22:08 2013-03-22 17:22:08 Mathprof (13753) Mathprof (13753) 9 Mathprof (13753) Definition msc 68P10 msc 68P05 order