A B-tree is an M-way search tree with two special properties:

- It is perfectly balanced: every leaf node is at the same depth.
- Every node, except perhaps the root, is at least half-full, i.e. contains M/2 or more values (of course, it cannot contain more than M-1 values). The root may have any number of values (1 to M-1).

And here is a 5-way B-tree (each node other than the root must contain between 2 and 4 values):

In the descriptions of our algorithms, we assume that M is odd; therefore each node (other than the root) must contains between (M-1)/2 and M-1 values.