Нелистовой узел в дереве B +

Question

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

Answer 1

Если вы не применяете правило полуобполнения, вы можете получить (эффективно) неуравновешенное дерево, например.

     [root] 
        / \_________________________ 
        /        \ 
      [branch]         [branch] 
     /  \        ____/ | \___ 
     /  \       /  |  \ 
[1-record leaf] [1-record leaf] [100-record leaf] [100-record leaf] [100-record leaf] 

Это займет гораздо меньше времени, чтобы найти первую или вторую запись в этом дереве, чем найти любого из других 300 записей.

Если вы позволите листьям иметь всего одну запись, а ветви имеют всего лишь один ключ (и, следовательно, двое детей), я считаю, что несоответствие времени поиска может быть столь же плохим, как log (m) (где m - порядок дерева). Поиск записи по пути с полными узлами занимает время Θ (log (N) * log (m)) (где N = общее количество записей, поэтому log (N) пропорционален высоте дерева), при просмотре запись по пути узлов минимального размера занимает только время Θ (log (N)) (потому что вы выполняете ровно одно сравнение в каждой ветви и ни одного в листе).

Применяя правило полуобполнения, вы гарантируете, что все времена поиска равны Θ (log (N) * log (m)) и постоянным коэффициентом друг друга.