Почему в B-tree и B+_tree хранятся от наполовину до полного в каждом неконечном узле

Question

Я только что изучил B-дерево и B+-дерево в СУБД. Я не понимаю, почему нествольный узел в дереве имеет между [n/2] и n дочерними элементами, когда n является фиксированным для определенного дерева.

Это почему? а преимущество в этом?

Спасибо!

Answer 1

Это функция, которая делает сбалансированными B+ и B-дерево, и благодаря этому мы можем легко вычислить сложность операций на дереве и привязать ее к O(logn) [где n - количество элементов в наборе данных ].

• Если бы узел мог иметь больше, чем B сыновей, мы могли бы создать дерево с глубиной 2: корень, а все остальные узлы будут листьями от корня. поиск элемента будет тогда O(n), а не желаемым O(logn).
• Если бы у узла могло быть меньше сыновей B/2, мы могли бы создать дерево, которое на самом деле является связанным списком [n узлов, каждый с 1 сыном], с высотой n - и операция поиска снова будет O (n) вместо O (LOGN)

Небольшое сокращение: у каждого неконечного узла - кроме корня, есть дочерние элементы от B/2 до B. один корень может иметь меньше сыновей B/2.

Answer 2

Основное предположение этой структуры - иметь фиксированный размер блока, поэтому каждый внутренний блок имеет n Слоты для индексации своих детей.

Когда необходимо добавить дочерний элемент в блок, который заполнен (имеет точно n children), блок разбивается на два блока, которые затем заменяют исходный блок в индексе своего родителя. Количество детей в каждом из двух блоков, очевидно, n div 2 (при условии, n даже). Отсюда и нижний предел.

Если родитель заполнен, операция повторяется, возможно, вплоть до самого корня.

Операция разделения и учета n/2Заполненные блоки позволяют большинству вставок / удалений вызывать только локальные изменения, а не перебалансировать огромные части дерева.