Организация внешнего поиска с помощью Б-деревьев.

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

Предположим, что мы хотим организовать в оперативной памяти дерево поиска с очень большим числом вершин (миллионы и более). Пусть при этом свободной ОП не достаточно для одновременного хранения сразу всех вершин. Часть (и при том весьма существенная) вершин должна оставаться на диске. Возникает задача такой организации дерева, чтобы можно было считывать и обрабатывать сразу группу вершин. Такая группа вершин получила название “страница”. Тем самым, все сверхбольшое дерево поиска разбивается на ряд страниц и чтение вершин с диска выполняется постранично. Это позволяет существенно уменьшить количество обращений к внешней памяти.

В качестве примера рассмотрим обычное дерево поиска из 15 вершин. Пусть для простоты оно является идеально сбалансированным. Выделим в нем 5 элементарных поддеревьев по 3 вершины в каждом и логически объединим эти вершины вместе в виде страниц. Если в дереве необходимо найти какую-либо терминальную вершину, и вершины считываются в ОП по одной, то для этого в обычном дереве потребуется 4 обращения к внешней памяти. А в дереве со страничной организацией потребуется считать из внешней памяти лишь 2 страницы – корневую и одну из терминальных. Даже в этом простейшем примере страничная организация дерева позволяет уменьшить число обращений к диску в два раза. Для сверхбольших деревьев этот эффект становится еще более заметным.

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

Б-дерево порядка m со страничной организацией - это структура данных, удовлетворяющая следующим условиям:

· весь набор из n элементов разбивается на отдельные страницы, причем каждая страница может содержать от m до 2m вершин, за исключением корневой страницы, для которой число вершин может изменяться от 1 до 2m

· каждая страница является либо терминальной (потомков нет), либо имеет ровно на одного потомка больше по сравнению с текущим числом вершин на этой странице

· все терминальные страницы находятся на одном уровне

Пример. Рассмотрим простейшее Б-дерево порядка m=2 с ключами целого типа. В соответствии с приведенными выше правилами, каждая страница такого дерева содержит от 2 до 4 вершин, а корневая – от 1 до 4. Каждая нетерминальная страница может иметь от 3 до 5 потомков. Пример дерева – на рисунке (к сожалению, терминальные страницы приходится располагать на разных уровнях).

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

· на каждой странице элементы упорядочены по возрастанию ключей

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

Последнее свойство является обобщением основного правила дерева поиска. Например, страница с ключами 40, 50 и 60 имеет четырех потомков, причем самый левый потомок содержит ключи меньше 40 (но больше 30), более правая страница содержит ключи в диапазоне от 40 до 50, еще более правая – в диапазоне от 50 до 60, а самая правая – больше 60.

Эффективность использования Б-дерева для поиска ключей в сверхбольших наборах данных можно оценить следующим образом.. Если Б-дерево имеет порядок m, а число элементов – n, то самым наихудшим случаем будет случай, когда на каждой странице находится минимально возможное число элементов, а именно - m. В этом случае высота Б-дерева определяется величиной log_mn, а именно высота и определяет количество обращений к внешней памяти.

Например, если число элементов в наборе данных n = 1 миллион, а порядок Б-дерева m = 100, то log₁₀₀1000000 = 3, т.е. максимум может потребоваться 3 обращения к внешней памяти. С другой стороны, даже в этом наихудшем случае оперативная память используется достаточно эффективно (примерно половина памяти от заявленного объема).