B-Tree - Почему не может быть узла с четным количеством ключей?

Question

Я пытаюсь реализовать B-Tree в соответствии с главой "B-Trees" в разделе "Введение в алгоритмы".

То, что я не совсем понимаю, это «минимальная степень».В книге говорится, что градус - это число , которое выражает нижнюю / верхнюю границу для количества ключей, которые может содержать узел .Далее говорится, что:

1. Каждый некорневой узел хранит как минимум t - 1 ключей и имеет t дочерних элементов .
2. Каждыйузел хранит не более 2*t - 1 ключей и имеет 2*t дочерних .

. Таким образом, вы получаете за t = 2:

1. t - 1 = 1 ключии t = 2 детей
2. 2*t - 1 = 3 ключа и 4 детей

Для t = 3

1. t - 1 = 2 ключа и т= 3 детей
2. 2*t - 1 = 5 ключей и 6 детей

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

Почему не может быть узла с, скажем, максимум 4 ключами и 5 дочерними элементами?Это как-то связано с разбиением узла?

Answer 1

Кажется, что узлы в B-дереве могут хранить только нечетное количество ключей?

Определенно нет.Числа, которые вы написали, являются минимальным и максимальным количеством ключей соответственно, поэтому для t = 2 допускаются узлы с 1, 2, 3 ключами.Для t = 3 допускаются узлы с ключами 2, 3, 4, 5.

Кроме того, корню дерева разрешено иметь только 1 ключ.

Можно определить(и реализовать) деревья, которые имеют, например.1 или 2 ключа в узле (так называемые 2-3 дерева).Причина, по которой B-деревья определены для размещения еще одного, заключается в том, что это приводит к более высокой производительности.В частности, это позволяет амортизировать O(1) (считая операции разделения и объединения) операции удаления и вставки.

Answer 2

это не невозможно, но неоптимально. как разделить узел с нечетным числом детей?