iSSSSSSSSu

РИСУНОК 16.8 РОСТ БОЛЬШОГО В-ДЕРЕВА

В этой имитации мы вставляем элементы со случайными ключами в первоначалыю пустое В-дерево, образованное страницами, которые могут содержать девять ключей и связей. Каждая линия отображает внешние узлы в виде сегментов, длина которых пропорциональна количеству элементов в данном узле. Большинство вставок выполняется во внешних узлах, которые не заполнены, что приводит к увеличению размера данного узла на 1. Когда вставка выполняется в заполненном внешнем узле, узел разделяется на два узла половинного размера.

РИСУНОК 16.9 РОСТ БОЛЬШОГО В-ДЕРЕВА С ОТОБРАЖЕНИЕМ ЗАНЯТОСТИ аРАНИЦ

В этой версии рис. 16.8 показано, как страницы заполняются во время процесса роста В-дерева. Как и в предыдущем случае, большинство вставок приходится на страницы, которые не заполнены, лишь увеличивая их занятость на 1. Когда вставка приходится на полную страницу, страница разделяется на две полупустые страницы.

Мы не сможем также рассмотреть подробности реализаций, поскольку это потребовало бы учета слишком многих зависящих от устройств и систем факторов. Как обычно, детальная разработка таких приложений - рискованное дело, и в современных системах желательно избегать наличия столь прихотливого и непереносимого кода, особенно, когда базовый алгоритм работает вполне успешно.

Упражнения

t> 16.5 Приведите содержимое 3-4-5-6-дерева, образованного в результате вставки ключей EASYQUESTIONWITHPLENTYOFKEYSb указанном порядке в первоначально пустое дерево.

о 16.6 Постройте рисунки, соответствующие рис. 16.5-16.7, иллюстрирующие процесс вставки ключей 516, 177, 143, 632, 572, 161, 774, 470, 411, 706, 461, 612, 761, 474, 774, 635, 343, 461, 351, 430, 664, 127, 345, 171 и 357 в указанном порядке в первоначально пустое дерево при Л/ = 5.

о 16.7 Укажите высоту В-деревьев, образованных в результате вставки в указанном порядке ключей из упражнения 16.6 в первоначально пустое дерево для каждого значения М> 2.

16.8 Нарисуйте В-дерево, образованное в результате вставки 16 одинаковых ключей в первоначально пустое дерево при М = 4.

16,9 Нарисуйте 1-2-дерево, образованное в результате вставки ключей Е А S Y Q UESTIONb первоначально пустое дерево. Объясните, почему 1-2-деревья не представляют практического интереса как сбалансированные деревья.

16.10 Измените реализацию вставки в В-дерево, приведенную в программе 16.3, чтобы в ней выполнялось разделение при перемещении вниз по дереву, подобно реализации вставки в 2-3-4-дереве (программа 13.6).

16.11 Напишите программу для вычисления среднего количества внешних страниц В-дерева порядка М, построенного путем N случайных вставок в первоначально пустое дерево при использовании вероятностного процесса, описанного после леммы 16.1. Выполните программу для Л/= 10, 100 и 1000 и N= 10 10 10 и 10

о 16.12 Предположите, что в трехуровневом дереве а связей могут храниться во внутренней памяти, от b до 2Ь связей - в страницах, представляющих внутренние узлы, и от с до 2с связей - в страницах, представляющих внешние узлы. Определите в виде функции от о, 6 и с максимальное количество элементов, которое может храниться в таком дереве.

о 16.13 Рассмотрите эвристический вариант родственного разделения В-деревьев (или В*-дерево): когда требуется разделить узел, поскольку он содержит М записей, мы объединяем узел с его родственным узлом. Если родственный узел содержит к записей, при к < М - \, мы перераспределяем элементы, помещая и в родственный, и в полный узел приблизительно по (Л/ + к)/2 записей. В противном случае мы создаем новый узел и помещаем в каждый узел дерева приблизительно по 2М/3 записей. Кроме того, мы позволяем корню разрастаться, чтобы в нем могло содержаться около 4Л 3, разделяя его и создавая новый корневой узел с двумя записями, когда его размер достигает этого предельного значения. Укажите верхние пределы количества зондирований, используемых для выполнения поиска