высота Проанализировав б дерева

Question

Я читал о B-деревьев в следующем месте

http://www.brpreiss.com/books/opus4/

Здесь автор анализирует высоту B-дерева.

Минимальное количество ключей в B-дереве порядка М> = 2 и высота> = 0 Nk = 2 * потолок (М/2)^ч -1

: Доказательство Очевидно, B-дерево с нулевой высотой содержит по крайней мере один узел. Рассмотрим порядок B-дерева M и высоту h> 0. По определению каждый внутренний узел (кроме корневого) имеет подпоследовательность по крайней мере потолок (M/2). Это означает, что минимальное количество ключей, содержащихся во внутреннем узле, равно celing (M/2) -1. Минимальное количество ключей - нулевой уровень 1; на уровне один, 2 (кельн (M/2) -1), на уровне 2 2 (потолок (м/2) -1)

Мой вопрос заключается в том, как автор пришел к выводу, что уровень 1 минимальное количество Kesy являются 2 (celing (М/2) -1) и для уровня 2?

, например, если М 2, то минимальное количество ключей в ровном1 грядет как 0, является то, что правильно?

Answer 1

Look Man, ни один из ключей на уровне 1 не будет минимальным, если корневой узел имеет два поддерева. Так что на первом уровне у нас есть два узла. Поэтому минимальное количество ключей на уровне 1 = 2 (кельн (M/2) -1) . Теперь, учитывая уровень 2. Как

1) Есть 2 (потолок (м/2)) под деревья (минимум) для узлов на уровне 1.

2) там минимальное количество ключей на уровне 2 равно 2 (потолок (м/2)) * (потолок (м/2) -1).

Просто прочитайте основы, если вы все еще не получите его.