Программа 16.3 Вставка в В-дерево

Новые элементы вставляются за счет перемещения больших элементов вправо на одну позицию, как в сортировке вставками. Если вставка приводит к переполнению узла, мы вызываем функцию split для разделения узла на две половины, а затем вставляем связь с новым узлом во внутренний родительский узел, который также может разделяться; таким образом, влияние вставки может распространяться вплоть до корня.

private:

link insertR (link h. Item x, int ht)

{ int i, j; Key v = x.keyO; entry<Item, Key> t; t.key = v; t.item = x; if (ht == 0)

for (j = 0; j < h->ni; j++)

{ if (V < h->b[j].key) break; }

else

for (j = 0; j < h->ni; j++)

if ((j+1 == h->m) II (V < h->b[j+l] .key)) { link u;

u = insertR(h->b[j++].next, x, ht-1);

if (u == 0) return 0;

t.key = u->b[0] .key; t.next = u;

break;

for (i = h->m; i > j; i-) h->b[i] = h->b[i-l] ; h->b[j] = t;

if (++h->m < M) return 0; else return split (h);

public: ST(int maxN)

{ N = 0; HT = 0; head = new node; } void insert(Item item)

{ link u = insertR (head, item, HT) ; if (u == 0) return; link t = new nodeO; t->m = 2; t->b[0].key = head->b[0].key; t->b[l].key = u->b[0].key; t->b[0].next = head; t->b[l].next = u; head = t; HT++;

Код разделения узла показан в профамме 16.4. В нем для переменной М используется четное значение, и каждый узел дерева может содержать только М - 1 элемент. Этот подход позволяет вставлять Л/-тый элемент в узел перед разделением этого узла и значительно упрощает код, не оказывая особого влияния на затраты (см. упражнения 16.20 и 16.21). Для простоты в аналитических выкладках, приведенных далее в разделе, мы ограничиваем сверху количество элементов каждого узла (Л/); действительные же различия весьма несущественны. В нисходящей реализации не прищлось бы прибегать к этой технологии, поскольку в таком случае наличие свободного места для вставки нового узла обеспечивается автоматически.

Программа 16.4 Разделение узла В-дерева

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

link split(link h) { link t = new nodeO; for (int j = 0; j < M/2; j++)

t->b[j] = h->b[M/2+j]; h->m = M/2; t->m = M/2; return t;

Лемма 16.2 Для выполнения поиска или вставки в В-дереве порядка М, содержащем N элементов, требуется от logmN до logM/i зондирований - число, которое на практике можно считать постоянным.

Эта лемма является следствием наблюдения, что все узлы во внутренней части В-дерева (узлы, которые не являются ни корнем, ни внешними узлами) имеют от Л 2 до М связей, поскольку они образованы в результате разделения полного узла, содержащего М ключей, и увеличиваться может только их количество (при разделении нижнего узла). В лучшем случае эти узлы образуют полное дерево порядка Л/, что немедленно дает указанный верхний предел (см. лемму 16.1). В худшем случае мы получаем полное дерево порядка Л 2.

Когда М равно 1000, при Л менее 125 миллионов, высота дерева меньше трех. В типовых ситуациях затраты можно уменьшить до двух зондирований, храня корневой узел во внутренней памяти. Для реализаций поиска на диске этот шаг можно предпринимать явно перед применением любого приложения, связанного с очень большим количеством поисков; в виртуальной памяти с кэшированием корневым узлом будет узел, который, скорее всего, должен храниться в быстрой памяти, поскольку обращение к нему выполняется наиболее часто.

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

Лемма 16.3 В-дерево порядка М, сконструированное из N случайных элементов, предположительно должно иметь около 1.44N/M страниц.

Яо (Yao) доказал это в 1979 г., прибегнув к математическому анализу, который выходит за рамки этой книги {см. раздел ссылок). Этот анализ основывается на анализе простой вероятностной модели, описывающей рост дерева. После того, как вставлены первые М/2 узлов, в любой заданный момент времени имеется t/ вне-

шних страниц с / элементами, при М/2 < i < Мм t + ... + N. Поскольку ве ро51тность попадания случайного ключа в любой интервал между узлами одинакова, вероятность попадания в узел с / элементами равна U/N. В частности, для / < М эта величина равна вероятности того, что количество внешних страниц с / элементами уменьшается на 1, а количество внешних страниц с (/ -ь 1) элементами увеличивается на 1. Для / = 2М эта величина равна вероятности того, что количество внешних страниц с 2Л/элементами уменьшается на 1, а количество внешних страниц с М элементами увеличивается на 2. Такой вероятностный процесс называется Марковской цепью. Результат, полученный Яо, основывается на анализе асимптотических свойств этой цепи.

Лемму 16.3 можно также доказать, написав программу для имитации вероятностного процесса (см. упражнение 16.11 и рис. 16.8 и 16.9). Конечно, можно было бы также просто построить случайные В-деревья и измерить их структурные характеристики. Вероятностную имитацию выполнить проще, чем произвести математический анализ или создать полную реализацию, кроме того, она служит важным инструментом изучения и сравнения вариантов алгоритмов (см., например, упражнение 16.16).

Реализации других операций таблиц символов аналогичны соответствующим реализациям для других ранее рассмотренных представлений с использованием деревьев, поэтому они остаются в качестве упражнений (см. упражнения 16.22-16.25). В частности, реализации операций select и sort очевидны, но, как обычно, правильная реализация операции remove может оказаться сложной задачей. Подобно операции insert, большинство операций remove заключаются в простом удалении элемента из внешней страницы и уменьшении значения ее счетчика, но что делать, если необходимо удалить элемент из узла, который имеет только М/2 элементов? Естественный подход - найти для заполнения свободного места элементы в родственных узлах (возможно, с уменьшением количества узлов на единицу), но реализация усложняется, поскольку приходится отслеживать ключи, связанные с любыми перемещаемыми по узлам элементами. Во встречающихся на практике ситуациях обычно можно использовать значительно более простой подход, оставляя внешние узлы незаполненными, что не особенно снижает производительность (см. упражнение 16.25).

Многие вариации базовой абстракции В-дерева приходят на ум немедленно. Один класс вариаций позволяет экономить время за счет упаковки во внутренние узлы максимально возможного количества ссылок страниц, в результате чего коэффициент ветвления повышается, а дерево становится более плоским. Как уже отмечалось, в современных системах преимущества, получаемые в результате таких изменений, ограничены, поскольку стандартные значения параметров позволяют реализовать операции search и insert при помощи всего двух зондирований - эффективность, которую вряд ли удастся повысить. Другой класс вариантов повышает эффективность использования дискового пространства, перед разделением объединяя узлы с их родственными узлами. Упражнения 16.13-16.16 посвящены такому методу, который при работе со случайными ключами позволяет уменьшить дополнительно используемый объем дискового пространства с 44 до 23 процентов. Как обычно, выбор того или иного варианта зависит от свойств приложения. Помня о широком множестве различных ситуаций, в которых применимы В-деревья, мы не будем подробно рассматривать эти вопросы.