LINUX.ORG.RU

B+-Tree: удаление элемента.

 


0

2

Допустим, удалили ключ K1 из листового блока. Ключ K1 в листовом блоке был первым. Значит в родительском блоке K1 выступал как pivot и показывал на этот блок. Теперь в листовом блоке первым стал некий K2.

(*) Теперь по идее нужно пойти в родительский блок и поменять там pivot K1 на K2.

Но я чё-то пока не понял, что страшного случится, если на это забить и оставить в родительском блоке старый pivot K1. Ну и что, что K1 нет, главное что все ключи большие K1 и меньшие следующего pivot лежат в этом блоке, куда pivot K1 показывает.

Ясно, что если бы гарантия (*) поддерживалась, можно было бы оптимизировать операцию «существует ли K1», выполнив её не доходя до листового блока. Но так себе причина.

слабо представляю, что такое B+, но, может, из-за нарушения этого инварианта при дальнейшем добавлении элементов >K1 дерево начнет разбалансироваться вправо?

MyTrooName ★★★★★ ()
Последнее исправление: MyTrooName (всего исправлений: 1)