# B-tree

## General information

Abstract data structure: Sorted sequence

Implementation Invariant:

1. There is a number $M\in\mathbb{N}$, $M\gt 1$, which is specific for the B-tree object and is constant throughout the life time of the B-tree object. This value $M$ is called the order of the B-tree.
2. A B-tree of order $M$ is a multi-way search tree with $2M-1$ slots for keys and, consequently, $2M$ slots for children pointers, in each node.
1. The slots for keys are denoted keys$[1],\ldots,$keys$[2M\!-\!1]$.
2. The slots for children are denoted children$[0],\ldots,$children$[2M-1]$.
3. The attribute $n$ of a node stores the number of filled key slots in this node.
4. In each tree node except for the root, it is $n\geq M-1$; for the root, it is $n\geq 1$.
5. The filled key slots are the ones at positions $1,\ldots,n$; the filled children slots are the ones at positions $0,\ldots,n$ (except for leaves, of course, where no child slot is filled at all).
6. The keys appear in ascending order in a B-tree node, that is, keys$[i]\leq$ keys$[i\!+\!1]$ for all $i\in\{1,\ldots,n-1\}$.
7. The children pointers appear in the order as used in the definition of multi-way search trees. In other words, for $R$ the range of the considered node and for $i\in\{0,\ldots,n\}$, the range of the node to which children points is
1. $R\cap\{K\in\mathcal{K}\,|\,K\leq$ keys$[1]\,\}$ for $i=0$;
2. $R\cap\{K\in\mathcal{K}\,|\,$ keys$[i\!-\!1]\leq K\leq$ keys$[i]\,\}$ for $i\in\{1,\ldots,n-1\}$;
3. $R\cap\{K\in\mathcal{K}\,|\,K\geq$ keys$[n]\,\}$ for $i=n$.
8. All leaves of a B-tree are on the same height level.

## Depth of a B-tree

Statement: The height of a B-tree of order $M$ with $N$ currently stored keys is $\lceil\log_M(N/(2\cdot(M-1))) \rceil+1\in\Theta(\log N)$ in the worst case.

Proof: It suffices to show that the minimum total number of keys on height level $i\gt 0$ is $2\cdot M^{i-1}\cdot(M-1)$. We apply an induction on $i$.

1. Induction basis: Since the root contains at least one key, there are at least two tree nodes on height level $i=1$, each containing at least $M-1$ keys.
2. Induction step: As all leaves are on the same height level, the minimum number of tree nodes on level $i$ is $M$ times the minimum number of tree nodes on level $i-1$. Therefore, the minimum number of keys on height level $i$ is $M$ times the minimum number of keys on height level $i-1$.