285
правок
Изменения
→Высота
Каждый узел дерева, кроме листьев, содержащий ключи <tex>k_1, ..., k_n</tex>, имеет <tex>n + 1</tex> сына. <tex>i</tex>-й сын содержит ключи из отрезка <tex>[k_{i - 1}; k_i],\: k_0 = -\infty,\: k_{n + 1} = \infty</tex>.
== Высота ==
<wikitex>
Количество обращений к диску, необходимое для выполнения большинства операций с В-деревом, пропорционально его высоте. Проанализируем высоту В-дерева в наихудшем случае.
{{Теорема|statement=Если $n \geqslant 1$, то для B-дерева $T$ c $n$ узлами и минимальной степенью $t \geqslant 2$ имеется следующее неравенство:
:$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)\sum\limits_{i = 0}^h 2t^{i-1} $
:::$=1+2(t-1)(\frac{t^h-1}{t-1})$
:::$=2t^h-1$.
Простейшее преобразование дает нам неравенство $t^h \leqslant (n+1)/2$. Логарифмирование по основанию $t$ обеих частей неравенства доказывает теорему
}}
</wikitex>
== Назначение ==
