Первый метод позволяет перестраивать элементы в пределах
узла и сестринских узлов, чтобы избежать разбиения сегментов. Используя вто-
рой, можно загружать или перезагружать данные, чтобы добавлять в дерево сво-
бодные ячейки. Это сокращает вероятность разбиения сегментов впоследствии.
Перебалансирование без дробления сегментов
При добавлении элемента заполненный блок разбивается на два. Можно из-
бежать разбиения сегмента, если перебалансировать узел с одним из его сестрин-
ских. Например, добавление нового элемента Q к Б-дереву, изображенному слева
на рис. 7.20, обычно вызывает дробление сегмента. Избежать этого можно, переба-
лансировав узел, содержащий J, К, L и N, с его левым сестринским, содержащим
В и Е. В результате получится дерево, изображенное справа на рис. 7.20. Рис. 7.20. Перебалансирование без разбиений сегментов
Этот тип балансировки имеет пару преимуществ. Во-первых, сегменты ис-
пользуются более эффективно. В них находится меньше пустых ячеек, поэтому
сокращается трата памяти. Во-вторых, если вы не разбиваете сегмент, то нет необ-
ходимости перемещать элемент в родительский сегмент. Это гарантирует, что если
каскад разбиений сегментов и возникнет, то он не будет слишком длительным.
С другой стороны, сокращение числа пустых ячеек уменьшает объем потра-
ченной впустую памяти, но увеличивает вероятность разбиения сегментов в буду-
щем. Поскольку в дереве остается меньше свободных ячеек, возрастает вероят-
ность, что при добавлении нового элемента узлы будут переполнены.
Опубликовал Kest
October 30 2009 09:37:18 ·
0 Комментариев ·
6374 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.
Главная
Каталог файлов
