B-Tree - Почему не может быть узла с четным числом ключей?
Я ' Я пытаюсь реализовать B-Tree в соответствии с главой «B-Trees» в разделе «Введение в алгоритмы». 1290 То, что я не совсем понимаю, это «минимальная степень». В книге говорится, что степень - это число , которое выражает нижнюю / верхнюю границу для количества ключей, которые может содержать узел . Далее говорится, что:
- Каждый некорневой узел хранит не менее
t - 1ключей и имеетtдочерних . - Каждый узел хранит не более
2 * t - 1ключей и имеет2 * tдетей .
Таким образом, вы получите для t = 2:
t - 1= 1 ключ и t = 2 детей2 * t - 1= 3 ключа и 4 детей
Для t = 3
t - 1= 2 ключа и t = 3 детей2 * t - 1= 5 ключей и 6 детей
Теперь здесь Проблема: Кажется, что узлы в B-дереве могут хранить нечетное нечетное количество ключей, когда они заполнены.
Почему не может быть узла с, скажем, максимум 4 ключами и 5 дочерними элементами? Это как-то связано с разбиением узла?
2 ответа
Кажется, что узлы B-Tree могут хранить только нечетное количество ключей?
Определенно нет. Введенные вами числа представляют собой минимальное и максимальное количество ключей соответственно, поэтому для t = 2 разрешены узлы с 1, 2, 3 ключами. Для t = 3 разрешены узлы с 2, 3, 4, 5 ключами.
Более того, корень дерева может иметь только 1 ключ.
Можно определить (и реализовать) деревья, например, у которых есть. 1 или 2 ключа в узле (так называемые 2-3 дерева). Причина, по которой B-деревья определены для размещения еще одного, заключается в том, что это приводит к более высокой производительности. В частности, это позволяет амортизировать O (1) (подсчет операций разделения и объединения) операций удаления и вставки.
это не невозможно, но неоптимально. как разделить узел с нечетным числом дочерних элементов?