Строительство B+ деревьев

Question

Строительство B+ деревьев

Предположим, меня попросили построить дерево B+ из:

i) n = x. 

ii) order = x.

iii) degree = x.

iv) p = x.

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

1

algorithm data-structures tree b-tree

Источник

user980411 01 май '12 в 06:24

1 ответ

Решение

Другие вопросы по тегам algorithm data-structures tree b-tree

user806418 01 май '12 в 18:14 2012-05-01 18:14 · Accepted Answer · 2012-05-01 18:14

В дереве B+ порядок обозначает максимальное количество дочерних указателей для каждого внутреннего узла, т. Е. Если порядок дерева B+ равен m, то каждый внутренний узел может иметь не более m дочерних элементов (впоследствии m-1 количество ключей) и по меньшей мере CEIL.(m/2) количество дочерних указателей (кроме корня).

Для степени дерева B+ из этого я получил информацию о том, что если d является степенью дерева B, то каждый узел может содержать до 2d элементов (ключей). Теперь и дерево B, и дерево B+ являются множественным деревом, и, следовательно, я полагаю, определение степени не изменится. Проверьте также $LINK, указанный как Комментарий, который указывает на тот же факт.

Для n, как упомянул JustinDanielson, это может быть общее количество ключей, хранящихся в узле, для которых указатель количества дочерних элементов будет n+1 (=x+1 для вашего вопроса)