285
правок
Изменения
→Высота
:$h \leqslant$ $\log_t\frac{n+1}{2}$
|proof=
Корень B-дерева $T$ содержит по меньшей мере один ключ, а все остальные узлы — хотя бы $t - 1$ ключей. Так, T, высота которого $h$, имеет хотя бы $2$ узла на глубине $1$, хотя бы $2t$ узла на глубине $2$, хотя бы $2t^2$ узла на глубине $3$, и так далее, до глубины $h$ , оно имеет хотя бы по меньшей мере $2t^{h-1}$ узлов. Так, число ключей $n$ удовлетворяет неравенству:::$n \geqslant (1+(t-1)\sum\limits_{i = 01}^h 2t^{i-1} $
:::$=1+2(t-1)(\frac{t^h-1}{t-1})$
:::$=2t^h-1$.
