Узел ветвления с k ключами имеет k + 1 дочерний элемент. Таким образом, как бы много узлов не было на уровне l - 1, на уровне l .
должно быть больше узлов.
То есть N + 1 (количество узлов на уровне l ) больше, чем количество узлов на уровне l - 1. Очевидно, фактическое количество узлов на уровне l - 1 больше или равно минимум количество узлов на уровне l - 1. Итак N + 1 & ge; 2⌈ м / 2⌉ л - 1 .