Предположим, что имеется небольшая база данных Клиентов, которая содер-
жит 10 записей. Вы можете загрузить записи в Б-дерево, чтобы они заполнили каж-
дый сегмент, как показано на рис. 7.21. Это дерево содержит немного свободных
ячеек, но добавление нового элемента немедленно вызывает разбиение блоков.
Поскольку все блоки заполнены, возникнет последовательность дробления сег-
ментов, которая дойдет до корневого узла.
Вместо того чтобы плотно заполнять дерево, вы можете добавить несколько
дополнительных пустых записей в каждый узел, как показано на рис. 7.22. Дерево
становится немного больше, но это позволяет добавлять новые элементы без по-
рождения длинной цепочки разбиений сегментов. После того как дерево некото-
рое время используется, количество свободного пространства может уменьшить-
ся до точки, когда вероятность разбиения сегментов возрастет. Тогда вы можете
перестроить дерево, чтобы добавить большее количество свободных ячеек. Рис. 7.21. Плотное заполнение Б-дереваРис. 7.22. Неплотное заполнение Б-дерева Б-деревья в реальных приложениях обычно имеют намного больший порядок,
чем приведенные здесь деревья. Добавление свободного пространства в дерево со-
кращает необходимость разбиения сегментов и балансировки. Например, если до-
бавить 10% свободного пространства в Б-дерево порядка 10, в каждом узле по-
явится место еще для двух элементов. Вы можете работать с этим деревом очень
долго, прежде чем возникнет необходимость в длинных цепочках дробления сег-
ментов.
Это очередной пример пространственно-временного компромисса. Добавле-
ние свободного пространства в узлы увеличивает размер дерева, но сокращает ве-
роятность разбиений сегментов.
Опубликовал Kest
Октябрь 30 2009 12:42:53 ·
0 Комментариев ·
6562 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.
Главная
Каталог файлов
