X. Предполагая, что страница считана в оперативную , мы можем использовать известные методы поиска и ключей ku . -, km- Если т достаточно велико, можно вменить бинарный поиск, если оно сравнительно небольшое.

[ойдет простой последовательный поиск. (Заметим, что

[2T 7 8j [13141518] 22 24 [26 27 28 [523538 4142 454б| Рис 4.4Ь. Б-дерево порядка 2

Время, требующееся для поиска в оперативной памяти, вероятно, пренебрежимо мало по сравнению со временем, которое занимает считывание страницы с внешнего устройства

Рис, 4.46. Страница Б-дерева, содержащая от ключей.

В оперативную память). Если поиск неудачен, мы имеем одну из следующих ситуаций:

А,-<: л: <;для \i<im. Мы продолжаем поиск на

странице р,. 2- km < X. Поиск продолжается на странице рт\. - < kl. Поиск продолжается на странице ро\.

Если в каком-то случае ссылка равна nil, т. е. нет соответствующего потомка, то элемента с ключом х нет во всем де-1>£ве и поиск заканчивается.

К удивлению, включение в Б-дерево также выполняется сравнительно просто. Если элемент вставляется в страницу, Держащую т<2п элементов, то процесс включения огра- чивается этой страницей. Лишь включение в уже заполнен-jyio страницу влияет на структуру дерева и может вызвать Явление новых страниц. Чтобы понять, что происходит Том случае, рассмотрим рис. 4.47, на котором показано

включение ключа 22 в Б-дерево порядка 2. Оно состоит

следующих этапов:

1. Выясняется, что ключ 22 отсутствует. Включение в стп ницу С невозможно, так как С уже заполнена.

2. Страница С расщепляется на две страницы, т. е. раз^, щается новая страница D.

3. Количество m + I ключей поровну распределяется на г и D, а средний ключ перемещается на один уровень вверх на страницу-предка А.

Эта весьма элегантная схема сохраняет все основные свой-ства Б-деревьев. В частности, при расщеплении получаются

А (20 30 I

Рис. 4.47. Включение ключа 22 в Б-дерево.

страницы, содержащие ровно п элементов. Разумеется, включение элемента в страницу-предка может вновь вызвать переполнение этой страницы, что приведет к распространению расщепления. В экстремальном случае оно может распространиться до корня. Это и есть единственный случай увеличения высоты Б-дерева. Следовательно, Б-дерево растет странным способом: от листьев к корню.

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

Прежде всего нужно сформулировать описание страницы. Мы выбираем расположение элементов в виде массива:

type page = record т: index;, рО: ref;

е\ array[l.. ии] olitem

(4.81)

const т - 2*п;

type ref = page; , index ~ 0.. им

tyitem = t&coxAkey: integer,

p: ref; 4 g2)

count: integer

Здесь вновь компонента count заменяет всевозможную фочую информацию, которая может быть связана с каждым цементом, но не играет никакой роли в самом процессе носка. Заметим, что каждая страница содержит пространство ля 2п элементов. Поле т указывает, сколько элементов раз-ещено в действительности. Поскольку п (за исключе-ием страницы-корня), использование памяти гарантируется [О крайней мере на 50 %.

Алгоритм поиска с включением по Б-дереву является шстью программы 4.7; он оформлен в виде процедуры searcli. iro основная структура проста и напоминает структуру про-юго поиска по бинарному дереву, с той разницей, что даль-ейший путь выбирается не из двух возможных ветвей, место этого поиск внутри страницы оформлен как бинар-1ЫЙ поиск в массиве.

Алгоритм включения сформулирован в виде отдельной про-ВДуры лишь для ясности. Эта процедура вызывается после ого, как search указывает, что элемент нужно передать вверх о дереву (в направлении к корню). Для указания исполь-уется булевский параметр-результат h, он играет роль, по-обную h в алгоритме включения в сбалансированное дерево, № Он сообщает, что поддерево выросло. Если h истинно, то орой параметр-результат и представляет передаваемый *ерх элемент. Отметим, что включение начинается с гипоте- ческих страниц, а именно специальных узлов (см. с. 4.19); новый элемент сразу отправляется через параметр ва страницу-лист для включения. Набросок схемы приведен (4.83).

Если после вызова search в основной программе параметр истинен, это означает расщепление страницы-корня. По-*льку эта страница играет особую роль, процесс нужно %ограммировать отдельно. Он состоит из размещения но-корневой страницы и включения в нее одного элемента, анного через параметр и. Следовательно, новая стра-