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

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

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+.

введите здесь описание изображения

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

введите здесь описание изображения

Вопрос:

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

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


delete-row tree computer-science database-indexes b-tree
person python    schedule 06.12.2015    source источник

Ответы (2)


arrow_upward
1
arrow_downward

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

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

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

person dimm    schedule 06.12.2015
comment
Хотя это не отвечает на мой вопрос. Не могли бы вы ответить на мой конкретный вопрос? Как эта теория связана с этим. - person python; 06.12.2015
comment
Рассмотрим случай, когда вы удаляете, скажем, половину элементов без какого-либо перераспределения. Вы получите неоптимальное дерево, потому что у вас по-прежнему будет три слоя, но вы можете поместить все элементы только в два слоя. - person dimm; 06.12.2015
comment
Какое это имеет значение в моем вопросе? Глубина дерева останется неизменной независимо от того, переставляете вы его или нет. Текущая глубина равна 3, и она не собирается меняться. - person python; 06.12.2015

arrow_upward
0
arrow_downward

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

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

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

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

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

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

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

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

введите здесь описание изображения

person python    schedule 06.12.2015