B + Tree Поиск Количество записей

Question

Недавно во время моих исследований я наткнулся на вопрос, как этот

Каков минимальный уровень B + дерева и индекс B Tree, необходимые для 5000 ключей и порядка B + дерева узла (P) 10. (Предположим, что P является максимальным указателем, который можно сохранить в дереве B +)

Я рассчитал для Btree, что это 4 уровня. При попытке для дерева B + я оказался в замешательстве. Описанный порядок - это порядок внутренних узлов или порядок узлов листа. если это был внутренний порядок узлов, то как можно вычислить количество уровней, необходимых, если порядок листового узла неизвестен. Может кто-нибудь мне помочь?

Answer 1

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

Как бы то ни было - назовем его L - количество требуемых узловых элементов должно быть ceiling(N/L), потому что слой листового узла должен содержать все данные. Если каждый листовой узел может содержать до 10 записей (элементов данных), мы получаем минимальное количество листовых узлов 500. Если у вас есть необходимое количество листовых узлов, вы можете вычислить требуемую высоту индексной части, как обычно, для B -tree.

В нашем случае нижний слой внутренних узлов (т. Е. Самый нижний слой индексной части дерева B +) должен иметь по меньшей мере 500 исходящих указателей, чтобы достичь каждого листа. ceiling(log(500)/log(10)) - это 3, что дает минимальное количество уровней индекса над набором последовательностей. Следовательно, дерево B + также имеет по крайней мере 4 уровня в этом случае, подобно простому B-дереву.