B-деревья: общие сведения

На практике широко распространены модели данных в виде B-деревьев. Использование В-дерева обеспечивает высокое быстродействие поиска при удалении, добавлении и чтении записей без осуществления сортировки всего содержимого файла после каждого изменения. Отличительной особенностью деревьев данного вида является то, что в них допускается более двух ветвей, исходящих из одной вершины.

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

Основные достоинства В-дерева:

1. Во всех случаях полезное использование памяти для хранения индексов составляет свыше 50%. Обеспечивается динамическое распределение и использование памяти. С ростом степени полезного использования памяти не происходит снижения качества обслуживания пользовательских запросов.

2. Произвольный доступ к записи реализуется посредством небольшого количества подопераций (обращений к физическим блокам) и по эффективности сопоставим с методами перемешивания.

3. В среднем достаточно эффективно реализуются операции включения и добавления записей. При этом сохраняется естественный порядок ключей с целью последовательной обработки, а также соответствующий баланс дерева для обеспечения быстрой произвольной выборки.

4. Упорядоченность по ключу обеспечивает возможность эффективной пакетной обработки.

Основной недостаток В-деревьев состоит в отсутствии для них средств выборки данных по вторичному ключу.

В-дерево степени k ( ) обладает следующими свойствами:

1. Все пути от корневой вершины до вершин-листьев имеют одинаковую длину h, называемую также высотой В-дерева (т.е. h есть количество вершин от корня до листа включительно).

2. Для каждой вершины, за исключением корня и листьев, количество подчиненных ей вершин (вершин-преемников) должно быть не меньше k+1 и не больше 2k+1.

3. Для корневой вершины количество подчиненных ей вершин должно быть не меньше двух и не больше 2k+1.

4. В каждой вершине, за исключением корня, количество ключей должно быть не меньше k и не больше 2k. В корне допускается только один ключ. В общем случае любая неконечная (ветвящаяся) вершина с j ключами должна иметь j+1 подчиненных вершин.

На основании этих свойств легко видеть, что B-дерево степени 1, в котором из каждой вершины выходят в точности две ветви, представляет собой полностью сбалансированное бинарное дерево поиска. Вследствие переменного количества ключей в вершинах B-деревья оказываются более гибкими в сравнении с бинарными деревьями. Так, многие операции включения и удаления можно выполнять без последующего преобразования дерева.

Физическая организация ветвящейся вершины В-дерева подобна физически последовательной структуре, как показано на рис. 2.9.

Рис.2.9

Структура ветвящейся вершины B-дерева с n ключами

При реализации каждый блок (или страница), как правило, содержит только одну вершину. Поэтому в блоке 2k-n ключевых позиций и соответствующих им указателей свободны. Ключевые значения обозначены через k_i, указатели индекса - p_i, а соответствующие указатели данных - α_i.

На рис. 2.10 приведены примеры В-деревьев степеней 1, 2 и 3. В явном виде показаны действительные ключевые значения, а указатели ветвей изображены стрелками, обозначающими направление путей доступа. Ассоциированные данные, соответствующие вершинам B-дерева, на рисунке не показаны. Все листья располагаются в В-дереве на одинаковом уровне, поскольку любое B-дерево полностью сбалансировано по высоте. Отметим также, что независимо от степени дерева его корень может иметь самое меньшее один ключ.

Рис.2.10

Возможные конфигурации В-дерева для файла с 12 ключами:

а) дерево степени 1 (h=3);

б) дерево степени 2 (h=2);

в) дерево степени 3 (h=2).

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

Алгоритм поиска для В-дерева аналогичен алгоритму поиска в бинарном дереве. Выполняется просмотр упорядоченных ключей в вершине с целью поиска хранимого ключа (индекса), равного или большего аргумента поиска. Если найден ключ, равный аргументу поиска, поиск считается завершившимся удачно и для определения местоположения записи используется значение указателя данных. Если в некоторой позиции найден ключ k_i, больший аргумента поиска, то осуществляется переход на вершину следующего уровня в соответствии со значением предыдущего указателя индекса p_i-1 и просмотр ключей в данной вершине. Если же все хранимые в вершине ключи меньше аргумента поиска, то осуществляется переход на следующий уровень в соответствии со значением самого правого указателя индекса p_n. Если аргумент поиска не найден в вершине-листе, то поиск заканчивается неудачно. Так, на рис. 2.10 поиск ключа 25 потребует: в случае а – трех обращений к блокам, в случае б – одного обращения к блоку и в случае в – двух обращений к блокам.