B-деревья

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

B-деревом[4] порядка m называется страничное дерево поиска, удовлетворяющее следующим условиям.

1. Каждая страница дерева содержит не более m ключей, причем m – четное число.

2. Каждая страница, кроме, быть может, корневой страницы дерева, содержит не менее m/2 ключей.

3. Все страницы-листья находятся на одинаковом расстоянии от корня.

Условие 1 означает всего лишь, что максимальное число ключей, которые можно разместить на странице, является четным. Условие 2 более существенно: оно означает, что каждая страница дерева (за исключением, может быть, корневой) заполнена по крайней мере наполовину. Условие 3 гарантирует невырожденность дерева.

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

Насколько высота B-дерева (т.е. время поиска ключа) может превышать минимально возможную высоту страничного дерева? Ясно, что высота будет тем больше, чем меньше ключей на каждой странице. Однако можно показать, что при достаточно большом порядке страницы высота наихудшего B-дерева (с одним ключом на корневой странице и m/2 ключами на каждой из остальных страниц) будет лишь на 1-2 уровня превышать высоту наилучшего дерева (с m ключами на каждой странице).

Рассмотрим теперь, как выполняется добавление новых ключей в B-дерево и каким образом при этом достигается соблюдение условий 1 – 3.

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

На рис. 4.9 показано небольшое B-дерево порядка 4, в которое последовательно вставляются три ключа.

Рис. 4.9. Добавление ключей в B-дерево

На верхнем рисунке – исходное B-дерево. При вставке на шаге 1 ключа 4 поиск приведет на крайнюю левую страницу-лист и, поскольку на странице есть свободное место, ключ добавляется без проблем.

На шаге 2 ключ 6 должен быть вставлен на ту же страницу, но места там уже нет. В этом случае должна быть выполнена операция расщепления страницы. Она заключается в следуюшем. Создается новая страница дерева. Те m ключей, которые были на заполненной странице (2, 4, 5 и 7), плюс вставляемый ключ 6, распределяются так: меньшие m/2 ключей (2 и 4) остаются не прежней странице, большие m/2 (6 и 7) переносятся на новую. Средний по значению ключ 5 переносится на страницу уровнем выше и используется как разделитель двух нижних страниц.

Из приведенного описания становится понятно, откуда взялось число m/2 в определении B-дерева.

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

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

Заметим, что на шаге 3 можно было бы избежать расщепления страниц, воспользовавшись операцией переливания ключей на соседнюю неполную страницу. Рядом со страницей, содержащей ключи (11, 12, 16, 19), имелась страница с ключами (25, 26). При добавлении ключа 18 на старой странице можно было бы оставить ключи (11, 12, 16, 18), ключ 19 перешел бы вверх на место ключа 20, который сдвинулся бы вниз: (20, 25, 26). Если использовать переливание, то расщепление страницы будет необходимым только тогда, когда ни слева, ни справа от переполняющейся страницы нет страницы со свободным местом.

Удаление ключа из B-дерева можно рассматривать как обратную операцию по отношению к вставке, однако здесь имеются некоторые дополнительные сложности. При удалении ключа надо обязательно сделать попытку переливания с одной из соседних страниц и только в случае невозможности следует объединять две страницы в одну, перенося вниз разделяющий их ключ со страницы верхнего уровня. Переливание выполняется не только для страниц-листьев, но и для внутренних страниц, если число ключей стало меньше m/2.

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

Можно также повысить порядок внутренних страниц B-дерева, если отказаться от хранения данных на всех страницах, кроме листьев. Тогда внутренние страницы будут содержать только ключи и указатели на нижележащие страницы, а листья – ключи и связанные с ними данные. При этом, очевидно, листья будут содержать все записи таблицы, т.е. все ключи и их данные, а внутренние листья тогда должны содержать дубликаты некоторых ключей, позволяющие спуститься к нужному листу. Такая структура данных называется B+-деревом. Пример B+-дерева показан на рис. 4.10.

Рис. 4.10. Структура B⁺-дерева

На рисунке серым заштрихованы области памяти, отведенные для хранения данных, связанных с ключами. Можно отметить, что каждый ключ, расположенный во внутреннем узле дерева, является дубликатом ключа ближайшей к нему справа записи, расположенной в листе дерева[5].

В тех случаях, когда объем внешней памяти ограничен и потому нежелателен двойной перерасход памяти, допускаемый моделью B-деревьев, можно использовать такую модификацию, как B * -деревья. Они отличаются иным алгоритмом вставки (и удаления) ключей. В этом алгоритме при переполнении страницы обязательно используется переливание на одну из соседних страниц. Когда соседние страницы заполнены, выполняется расщепление не одной страницы, а двух соседних страниц. На новую страницу переносится треть ключей с каждой из двух заполненных страниц, так что каждая страница B*-дерева будет заполнена по крайней мере на 2/3, а не на 1/2, как для обычного B-дерева. Корневая страница B*-дерева должна при этом быть большего размера, чем остальные, и она может быть заполнена не более чем на 4/3 от объема обычной страницы. При расщеплении корня он дает две обычные страницы, заполненные на 2/3, а новый корень, как и для B-деревьев, содержит только один ключ.

Модель B*-деревьев позволяет сократить расход внешней памяти примерно на 25 %, но при этом добавление и удаление ключей выполняется заметно сложнее, чем для B-деревьев.