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

Question

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

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

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

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

Answer 1

d это степень дерева B

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