У меня есть это B+tree. Насколько я знаю, дерево B + имеет все узлы в листьях, но в этом дереве B + некоторые из узлов не находятся в листовых узлах (например, 40 и 10). Почему это?B + дерево с узлами не в листе?
Что произойдет, если я вставил элемент, который уже находится в дереве?
Концептуально дерево B + состоит из двух частей: последовательности (все листья, содержащие ключи и фактические данные) и индекса, который состоит из всех внутренних узлов и содержит только ключи, но не данные. Единственная цель индекса - вести поиск на соответствующей странице листа.
Ключи в индексных узлах не обязательно должны соответствовать любым клавишам, фактически сохраненным в листовых узлах, поскольку они должны только маршрутизировать поиск в правый лист. Другими словами, индексу нужны только ключи разделителя, а не записи ключей.
Когда к индексу нужно добавить новый ключ, приложение может каким-либо образом изменить его, чтобы оно стало более желательным каким-либо образом (например, короче, в случае строк), сохраняя при этом свою способность отделяйте своих левых детей от своих правых детей. Например. «М» отделяет «Леманн» от «Шульце» так же хорошо, как и «Мюллер». Например, в случае числовых клавиш приложение может выбрать среднее арифметическое между максимальным левым дочерним и минимальным правыми дочерними элементами.
Существует еще одна причина, по которой ключи могут встречаться в индексном слое дерева B + без каких-либо соответствующих «записей» в листьях (набор последовательностей), а именно удаление. Когда ключ должен быть удален из дерева B +, он удаляется только из набора последовательностей, в котором хранятся фактические данные, представленные деревом B +. Если есть копия ключа в индексном слое, тогда он остается один, потому что он по-прежнему необходим для маршрутизации трафика.
Если вы вставляете ключ, который уже присутствует в последовательности, то вы нарушаете структурный инвариант дерева B +. Фактические последствия этой коррупции зависят от кода, использующего дерево B +, но код производственного класса защищает инварианты его структур и, скорее всего, выдает исключение в вашем лице.
