Максимальное количество ключей в B-дереве

Question

Я использую следующее определение B-дерева (согласно википедии: https://en.wikipedia.org/wiki/B-tree):

Каждый узел содержит от d до 2d ключей.

Я сейчас ищу формулу, как рассчитать максимальное количество ключей в B-дереве с высотой = h. Как я могу это сделать?

Кстати: в чем смысл d? Могу ли я сказать, что это степень дерева?

Answer 1

d - степень дерева B.

Только внутренние узлы ограничены d, правило не применяется к корню. Поскольку корень может иметь больше ключей, чем 2d - 1, я бы сказал, что максимальное количество ключей в дереве B не ограничено.