Допустимо ли это дерево B+?

В дереве B+ может ли существовать не-листовой узел, у которого значение ключа удалено? Это означает, что дерево B+ имеет значение в своем промежуточном не листовом узле, но не в любом из его листовых узлов.

Рассмотрим следующую структуру. Я столкнулся с этим, изучая деревья B+. В этой структуре 13 не является конечным узлом. Но это не листовой узел. (На самом деле он был удален в предыдущих инструкциях. Ссылка на картинку . По этой ссылке переходим в нижнюю часть Страница)

Образ дерева я не понимаю

Если да, то как происходит удаление данных?

Это ошибка или я что-то упускаю?

1 2
data-structures b-tree

1 ответ:

Изображение, которое вы разместили, действительно. Единственное, что возвращает это дерево, - это то, что вы найдете в последней строке. Поскольку 13 был удален из дерева, он был удален из последней строки. Тот факт, что 13 существует в не-листовом узле, не имеет никакого значения для ваших результатов, это просто должно быть сопоставимое значение при переходе вниз по дереву. В этом случае дерево не будет вести себя иначе, если 13 будет изменено на 16 (на основе вышеупомянутого соглашения).

Дуглас Фишер сделал исчерпывающий видеоряд о деревьях B+, который может быть легче изучить, чем читать статьи. Часть 1 можно найти здесь.

Edit : мой ответ в комментариях был слишком длинным, поэтому я помещу его здесь. Плюс это полезная информация.

Если вы ищете 12, и достигнете 13, вы будете сравнивать это 12 < 13 или 13 <= 12, левый истинен, поэтому вы перейдете вниз к левому листу. Это произошло бы независимо от того, был ли 13 16, потому что это тоже верно 12 < 16.

Если вы ищете 16 и достигаете 13, вы будете сравнивать 16 < 13 или 13 <= 16, правильное выражение верно, поэтому вы перейдете вниз к правому листу. Тогда вы найдете значение 16 там.

Если вы ищете 13 (который не существует), вы спросите, является ли 13 < 13 или 13 <= 13, правильное выражение истинно, поэтому вы перейдете к правому листу и обнаружите, что там нет 13, и вы выбьете это укажите, что 13 не имеет значения.

1