Б-деревья. Определение Алгоритмы поиска, включения и исключения. Необходимость их применения.

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

Предположим, что мы решили помещать на странице 100 узлов, тогда дерево поиска, содержащее миллион элементов, потребует в среднем только =3 обращения к страницам вместо 20. Но если дерево растет «случайным образом», то наихудший случай может потребовать даже обращений. Поэтому в случае сильно ветвящихся деревьев почти обязательна схема управления их ростом.

Критерии Р.Бэйера для управления ростом дерева:

1) каждая страница содержит не более 2n элементов (ключей);

2) каждая страница, кроме корневой, содержит не менее n элементов;

3) каждая страница является либо листом, т.е. не имеет потомков, либо имеет m+1 потомков, где m – число находящихся на ней ключей;

4) все листья находятся на одном и том же уровне.

В дереве с N элементами и максимальном размере страницы 2n узлов наихудший случай потребует обращений к страницам.

Если необходимо найти элемент x среди ключей k₁, …, k_m мы имеем одну из следующих ситуаций:

1) k_i<x<k_i+1 для 1<=i<m. Мы продолжаем поиск на странице p_i^;

2) x>k_m. Продолжаем поиск на странице p_m^;

3) x<k₁. Продолжаем поиск на странице p₀^.

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