Поиск элемента в Б-дереве.

Пусть имеется Б-дерево порядка m, в котором требуется найти вершину с ключом x. Алгоритм поиска:

· считываем в ОП корневую страницу и организуем на этой странице поиск заданного элемента; если порядок Б-дерева небольшой, то можно применить обычный поиск прямым перебором; для деревьев большого порядка можно использовать метод двоичного поиска в упорядоченном массиве

· если заданный элемент на корневой странице найден, то обрабатываем его и завершаем поиск

· если заданного элемента на корневой странице нет, то возможно появление одной из трех следующих ситуаций:

Ø искомый элемент меньше самого левого ключа (x<pRoot^.mas[1].key); в этом случае поиск надо продолжить на странице, определяемой самой левой ссылкой (pRoot^.leftPage), для чего в ОП загружается вторая страница и поиск на ней повторяется описанным выше образом

Ø искомый элемент находится между двумя элементами (pRoot^.mas[j].key < x < pRoot^.mas[j+1].key); в этом случае поиск надо продолжить на странице, которая определяется ссылкой pRoot^.mas[j].cPage

Ø искомый элемент больше самого правого элемента (x > pRoot^.mas[nPage].key); поиск продолжаем на странице, определяемой ссылкой в последнем элементе массива (pRoot^.mas[nPage].cPage)

Если при этом какая-либо ссылка на страницу оказывается пустой, то это является признаком того, что искомого элемента в Б-дереве нет.

Для ускорения обработки Б-деревьев рекомендуется корневую страницу постоянно держать в ОП. Поскольку одновременно в ОП может находиться несколько страниц, то это накладывает ограничения на размер страницы и на порядок Б-дерева.

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

Например, для рассмотренного выше Б-дерева поиск элемента с ключом 43 будет выполнен следующим образом:

· заходим на корневую страницу и устанавливаем, что ключ 43 больше всех ключей на корневой странице

· загружаем в ОП новую страницу, определяемую самой правой ссылкой на корневой странице

· организуем поиск ключа 43 среди элементов новой страницы (40, 50, 60) и фиксируем ситуацию расположения ключа 43 между ключами 40 и 50

· загружаем в ОП третью страницу, определяемую ссылкой у элемента 40 и организуем ее просмотр

· на этой странице (41, 42, 43, 44) находим искомый элемент

Наоборот, поиск ключа 45 приведет на последнем шаге к необходимости перехода на страницу, являющуюся самым правым потомком третьей страницы, но соответствующая ссылка является пустой и поиск заканчивается неудачно.