2. B-trees: Perfectly Height-balanced M-way search trees
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).
The 3-way search tree above is
clearly not a B-tree. Here is a 3-way B-tree containing the
same values:
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.