A B-Tree of order M is either the empty tree or it is an M-way search tree T with the following properties:
(i) The root of T has at least two subtrees and at most M subtrees.
(ii) All internal nodes of T (other than its root) have between [M / 2] and M subtrees.
(iii) All external nodes of T are at the same level.
Just as AVL trees are balanced binary search trees, B-trees are balanced M-way search trees. By imposing a balance condition, the shape of an AVL tree is constrained in a way which guarantees that the search, insertion, and withdrawal operations are all O(log n), where n is the number of items in the tree. The shapes of B-Trees are constrained for the same reasons and with the same effect.
