Удаление ключа из дерева B +

Question

Мой профессор читал лекцию о удалении B + деревьев, и я очень смутился. По его словам, для удаления любого ключа из B + Tree:

1- First navigate to the leaf *L* where it belongs. 
2- If the *L* is at least half full if you can simply delete it. 
3- If it contains d-1 elements then you need to redistribute and merge. 

Если вы видите ниже изображения, здесь я хочу удалить 19 и 20 с B + Tree.

После удаления 19 и 20 из B + Tree.

Вопрос:

Я смущен, почему здесь требуется перераспределение и слияние вообще? Если вы просто просто удаляете 19 и 20 из листовых узлов без какого-либо распространения, он должен работать правильно? Почему здесь происходит перераспределение? Может ли кто-нибудь объяснить?

Это потому, что левая стрелка 24 указывает на 20, но не 19. Вот почему перераспределение требуется для 20, но не 19.

Answer 1

B + дерево не является самобалансировку дерево поиска.

Самобалансирующиеся деревья должны поддерживать максимальную глубину дерева пропорционально некоторому логарифму количества элементов, которые он удерживает.

B + делает это таким образом, с разбиением и добавлением слоев при вставке и перераспределении и удалении узлов при удалении.

Answer 2

Хорошо, я понял проблему.

Свойства дерева B +.

• Все листья должны быть на одной и той же глубине, а элемент mininum в каждом листовом узле должен быть равен глубине дерева. Смотрите пример ниже:

• Все листья находятся в той же самой глубине, и здесь d = 2.

• Каждый лист узел должен содержать d количество элементов, в противном случае перераспределение и слияние должно быть выполнено.
• Все указатели данных содержатся в листовых узлах.
• Все элементы должны содержаться в листовых узлах.
• Должно быть от d до 2*d ключей на узле, за исключением, возможно, корневого.
• Должно быть от d + 1 до 2*d + 1 указателей для детей.

В B + Tree приведены ниже, каждый узел имеет 2 и 2*2 записи данных, за исключением возможного корня. Каждый узел имеет mininum из 2 ключей.

Только корень дерева B + может быть меньше, чем d ключей, это единственное исключение, которое у нас есть.

В моем вопросе, когда вы удаляете 19, свойство B + Tree не нарушается, но при удалении 20 общее количество элементов, содержащихся в узле, меньше d. Следовательно, перераспределение и слияние должны выполняться так, чтобы свойство дерева B + не нарушалось.