Почему в 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 дочерних элементов), блок разделяется на два блока, которые затем заменяют исходный блок в индексе его родителя. Число детей в каждом из двух блоков, очевидно, равно n div 2 (при условии, что n четное). Отсюда и нижний предел.

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

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