Количество поддеревьев корневого узла в дереве B

Question

Определение B дерева я читал в различных всех книг содержит следующую

• Каждый узел, за исключением корневого узла должен быть по крайней мере наполовину
• Если корневой узел является узлом индекса, он должен содержать не менее двух детей.

Я предполагаю, что второй особый случай - позволить дереву B иметь, скажем, только один ключ и быть действительным. Однако, если в дереве B много узлов, разрешено ли корневому узлу иметь только два поддерева? Разве это не нарушит гарантию дерева B, как легкое разделение и соединение?

Answer 1

Однако, если в дереве B имеется много узлов, разрешено ли корневому узлу иметь только два поддерева?

Да, корень имеет специальную обложку, потому что каждый другой внутренний узел имеет братьев и сестер, с которыми он может слиться.

Предположим, что мы удаляем ключ, и в результате у некоторого внутреннего узла слишком мало детей. У нас есть два варианта в обычных алгоритмах B-дерева: пусть этот узел возьмет детей от своих братьев и сестер или просто слияет с братьями и сестрами прямо (возможно, распространяет недостаток к корню). Для корня также нет возможности, поэтому мы просто освобождаем его от минимального требования к детям. Это увеличивает максимальную высоту для заданного количества ключей не более чем на один, поэтому асимптотическое время работы операций не изменяется.