Внешний поиск a

Лемма 16.2. Для выполнения поиска или вставки в B-дереве порядка M, содержащем N элементов, требуется от log_MN до log_M/2N проб — на практике это число можно считать постоянным.
Эта лемма следует из наблюдения, что все узлы во внутренней части B-дерева (узлы, которые не являются ни корнем, ни внешними узлами) содержат от M/2 до M ссылок, поскольку они образованы в результате разбиения полного узла, содержащего M ключей, и могут лишь увеличиваться (при разбиении нижележащего узла). В лучшем случае эти узлы образуют полное дерево порядка M, что и дает указанный верхний предел (см. лемму 16.1). В худшем случае получается полное дерево порядка M/2. 
Программа 16.1. Определения типов узлов B-дерева
Каждый узел в B-дереве содержит массив и счетчик количества активных записей в этом массиве. Каждая запись массива представляет собой ключ, элемент и ссылку на узел. Во внутренних узлах используются только ключи и ссылки; во внешних узлах используются только ключи и элементы. Новые узлы создаются пустыми, для чего обнуляется поле счетчика.
template
struct entry
{ Key key; Item item; struct node *next; };
struct node
{ int m; entry b[M];
node() { m = 0; }
};
typedef node *link;
Программа 16.2. Поиск в B-дереве
Как обычно, эта реализация операции найти для B-деревьев выполнена рекурсивной. Для внутренних узлов (имеющих положительную высоту) выполняется поиск ключа, который больше искомого, а затем рекурсивный вызов для поддерева, указанного предыдущей ссылкой. Для внешних узлов (высота которых равно 0) выполняется просмотр, чтобы выяснить, содержат ли они элемент с ключом, равным искомому.
private:
Item searchR(link h, Key v, int ht)
{ int j;
if ( ht == 0)
for (j = 0; j < h->m; j++)
{ if (v == h->b[j].key)
return h->b[j].item;
}
else
for (j = 0; j < h->m; j++)
if ((j + 1 == h->m) || (v < h->b[j + 1].key))
return searchR(h->b[j].next, v, ht-1);
return nullItem;
}
public:
Item search(Key v)
{ return searchR(head, v, HT); }
Программа 16.3. Вставка в B-дерево
При вставке новых элементов большие элементы сдвигаются вправо на одну позицию, как в сортировке вставками. Если вставка приводит к переполнению узла, вызывается функция split для разбиения узла пополам, а затем ссылка на новый узел вставляется во внутренний родительский узел, который также может потребовать разбиения; таким образом, влияние вставки может распространиться вплоть до корня.
private:
link insertR(link h, Item x, int ht)
{ int i, j; Key v = x.key(); entry t;
t.key = v; t.item = x;
if (ht == 0)
for (j = 0; j < h->m; j++)
{ if (v < h->b[j].key) break; }
else
for (j = 0; j < h->m; j++)
if ((j+1 == h->m) || (v < h->b[j+1].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-1];
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 node(); t->m = 2;
t->b[0].key = head->b[0].key;
t->b[1].key = u->b[0].key;
t->b[0].next = head;
t->b[1].next = u;
head = t; HT++;
}
Программа 16.4. Разбиение узла B-дерева
Для разбиения узла в B-дереве создается новый узел, и большая половина ключей перемещается в новый узел, а затем корректируются счетчики, и в середины обоих узлов заносятся сигнальные ключи. В этой программе предполагается, что M четно, а в каждом узле имеется лишняя позиция для элемента, вызвавшего разбиение. То есть максимальное количество ключей в узле равно M-1, а когда количество ключей в узле достигает M, он разбивается на два узла с M/2 ключами в каждом.
link split(link h)
{ link t = new node();
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;
}
Если M равно 1000, то при N, меньшем 125 миллионов, высота дерева меньше трех. В типичных ситуациях можно хранить корневой узел в оперативной памяти и этим уменьшить затраты до двух проб. Для реализаций поиска на диске этот шаг можно предпринимать явно перед запуском любого приложения, связанного с очень большим количеством поисков; в виртуальной памяти с кэшированием корневым узлом будет узел, который вероятнее всего находится в быстрой памяти, т.к. это узел, к которому происходит наибольшее количество обращений.
Вряд ли можно рассчитывать на реализацию поиска, которая сможет гарантировать выполнение менее двух проб для выполнения операций найти и вставить в очень больших файлах, и B-деревья находят широкое применение, поскольку они позволяют приблизиться к этому идеалу. Однако производительность и гибкость достигаются ценой неиспользуемой памяти внутри узлов, что для очень больших файлов может оказаться обременительным.
Лемма 16.3. B-дерево порядка M, построенное из N случайных элементов, предположительно имеет около 1,44 N/M страниц.
Яо (Yao) доказал этот факт в 1979 г., прибегнув к математическому анализу, который выходит за рамки этой книги (см. раздел ссылок). Этот анализ основывается на анализе простой вероятностной модели, описывающей рост дерева. После вставки первых M/2 узлов в любой заданный момент времени имеется tt внешних страниц с i элементами, для   и t_M/2 + ... + t_M = N . Поскольку вероятность попадания случайного ключа в любой интервал между узлами одинакова, вероятность его попадания в узел с i элементами равна t_i /N . В частности, для i < M эта величина равна вероятности того, что количество внешних страниц с i элементами уменьшается на 1, а количество внешних страниц с i + 1 элементами увеличивается на 1. Для i = 2M эта величина равна вероятности того, что количество внешних страниц с 2M элементами уменьшается на 1, а количество внешних страниц с M элементами увеличивается на 2. Такой вероятностный процесс называется цепью Маркова. Результат, полученный Яо, основывается на анализе асимптотических свойств этой цепи. 
Лемму 16.3 можно также проверить, написав программу для моделирования вероятностного процесса (см. упражнение 16.11 и рис. 16.8 и 16.9). Конечно, можно также просто строить случайные B-деревья и измерять их структурные характеристики. Вероятностное моделирование выполнить проще, чем провести математический анализ или создать полную реализацию, кроме того, оно служит важным инструментом изучения и сравнения вариантов алгоритмов (см., например, упражнение 16.16).
Реализации других операций такой таблицы символов аналогичны соответствующим реализациям для других ранее рассмотренных представлений с использованием деревьев и оставлены в качестве упражнений (см. упражнения 16.22—16.25). В частности, реализации операций выбрать и сортировать очевидны, но, как обычно, правильная реализация операции удалить может оказаться сложной задачей. Подобно операции вставить, большинство операций удалить сводятся к простому удалению элемента из внешней страницы и уменьшению значения ее счетчика; но что делать, если необходимо удалить элемент из узла, который имеет только M/2 элементов? Естественный подход — найти для заполнения свободного места элементы в родственных узлах (возможно, с уменьшением количества узлов на единицу), но тогда реализация усложняется, поскольку приходится отслеживать ключи, связанные со всеми перемещаемыми по узлам элементами.