Сколько ключей может содержаться на уровне листьев в B+ Tree

Question

Сколько ключей может содержаться на уровне листьев в B+ Tree

В моем классе базы данных мой профессор рассказывал об удалении ключей из дерева B+. Если вы видите изображение ниже:

Я полностью понял все, кроме одной части, где он сказал, что leaf level узлы могут содержать только 3 ключи максимум. В соответствии с моим пониманием, в зависимости от глубины B+ tree, общее количество ключей определяется на уровне листа, варьируется от d в 2*d где d - глубина дерева. Так как здесь d для листа равно 2, почему узлы уровня листа не могут иметь 4 ключи. Куда я иду не так?

Общее количество ключей, содержащихся на корневом уровне, также имеет значение здесь? Может ли кто-нибудь объяснить, пожалуйста

1

tree computer-science delete-row b-tree tree-balancing

Источник

user4593743 08 дек '15 в 02:30

1 ответ

Решение

Другие вопросы по тегам tree computer-science delete-row b-tree tree-balancing

user207421 08 дек '15 в 03:41 2015-12-08 03:41 · Accepted Answer · 2015-12-08 03:41

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

Если он действительно сказал это, он не прав. Это 4, так же, как порядок дерева B+. Его собственная картина доказывает это: см. Нижний правый узел.

Насколько я понимаю, в зависимости от глубины дерева B+ общее количество ключей определяется на уровне листьев, варьируется от d до 2*d, где d - глубина дерева.

Совершенно неправильно. Глубина дерева не имеет к этому никакого отношения. Количество ключей на узел находится между N/2 и N, за исключением корневого узла, который может иметь меньше.