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(lo{g}_2(n))$.

Title	B-tree
Canonical name	Btree
Date of creation	2013-03-22 17:22:08
Last modified on	2013-03-22 17:22:08
Owner	Mathprof (13753)
Last modified by	Mathprof (13753)
Numerical id	9
Author	Mathprof (13753)
Entry type	Definition
Classification	msc 68P10
Classification	msc 68P05
Defines	order