Дублируются ли ключи в узлах B-дерева при разделении узла?

Question

Когда узел в B-дереве разделяется, дублируются ли ключи от исходного узла в новых узлах? Какова цель сделать это? Разве это не неэффективно?

Answer 1

Нет. Это все сделано с помощью указателей. Половина указателей перемещена в новый узел.

Конечно, не существует такой вещи, как "B-дерево". Существует множество различных реализаций. Я мог бы представить себе тот, в котором ключи на самом деле хранятся в узлах, таких как дерево, где ключи являются целочисленными. Но они все равно не будут «дублированы», только скопированные данные.

Если ваша говядина - это хранилище, оставшееся в разделяемом узле, то это еще один вариант оптимизации: освободить и перераспределить меньше или нет. Вероятно, нет, поскольку может появиться больше вставок, которые входят в половину пространства ключа этого узла.

Answer 2

Я думаю, что вы имеете в виду дерево B +.

В B + дереве, которое я написал, я дублировал значения ключей в родительском узле во время разделения. ключ [pos] в родительском элементе был установлен на самое низкое значение левого узла и указывал на левый узел. Наименьшее значение правого узла стало ключом [pos + 1] в родительском элементе.