Блог им. Сталинко

В этой статье хочу поведать вам об одном старом, известном и неумирающем алгоритме поиска — о B-деревьях. B-деревья позволяют быстро находить целые блоки данных по заданному ключу. Кроме того они решают сразу целый букет проблем: поиск,  добавление,  удаление. Благодаря этим достоинствам, они получили широкую популярность в базах данных, в частности в ISAM и MyISAM от MySQL.

В интернете вы можете найти много информации про B-деревья. Например, хорошие статьи есть на Википедии. Я же постарался рассказать кратко, наглядно и максимально полно о B-деревьях. Итак, поехали…

Вступление

B-дерево – это структура хранения данных, являющаяся разновидностью дерева поиска. Впервые была предложена Р. Бэйером и Е. МакКрейтом в 1970 году. Особенностями В-деревьев является: сбалансированность, ветвистость, отсортированность и логарифмическое время работы всех стандартных операций (поиск, вставка, удаление). Сбалансированность означает, что все листы находятся на одинаковом расстоянии от корня. В отличие от бинарных деревьев В-деревья допускают большое число потомков для любого из узлов. Это свойство называется ветвистостью. Благодаря ветвистости, В-деревья очень удобны для хранения крупных последовательных блоков данных, поэтому такая структура часто находит применение в базах данных и файловых системах.

Описание

Рис. 1. Стрелки идут к потомкам. В ключах записаны числа

Для описания В-деревьев прежде всего придется разобраться с терминологией. К сожалению, в литературе нет устоявшейся нормы. Начнём с того, что определим число m – порядок В-дерева – это максимальное число потомков для любого узла. Кроме узлов в дереве присутствует ещё одна сущность – ключи. Именно в них и содержится вся полезная информация. Каждый узел дерева можно представить в виде упорядоченной последовательности ”потомок1; ключ1; потомок2; ключ2; … потомок(N-1); ключ(N-1); потомокN”. Важно заметить, что ключи располагаются между ссылками на потомков и, таким образом, ключей всегда на 1 меньше. В организации В-дерева можно выделить несколько ключевых правил:

1. Каждый узел содержит строго меньше m (порядок дерева) потомков.
2. Каждый узел содержит не менее m/2 потомков.
3. Корень может содержать меньше m/2 потомков.
4. У корневого узла есть хотя бы 2 потомка, если он не является листом.
5. Все листья находятся на одном уровне и содержат только данные (ключи).

Алгоритмы для работы с В-деревом

1. Поиск

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

Пусть мы ищем значение X в заданном В-дереве.

1. Начинаем от корня
2. Если X – это один из ключей текущего узла, то СТОП, ключ найден.
3. Иначе находим пару соседних ключей Y, Z, таких что X лежит в интервале от Y до Z
4. Переходим к потомку между Y и Z
5. Идём на шаг 2.
6. Если мы дошли до листа и Х не содержится среди ключей, то СТОП, такого значения в дереве нет.

2. Добавление ключа

Рис. 2. Процесс вставки ключа

Введём определение: дерево потомков некоего узла — это поддерево, состоящее из этого узла и его потомков.

Вначале определим функцию, которая добавляет ключ K к дереву потомков узла x. После выполнения функции во всех пройденных узлах, кроме, может быть, самого узла x, будет меньше 2t – 1 (число t связано с m так: m = 2(t – 1)), но не меньше t – 1 ключей.

1. Если х — не лист
   1. Определяем интервал, где должен находиться K. Пусть y — соответствующий сын.
   2. Рекурсивно добавляем K к дереву потомков y.
   3. Если узел y полон, то есть содержит 2t − 1 ключей, расщепляем его на два. Узел y1 получает первые t − 1 из ключей y и первые t его потомков, а узел y2 — последние t − 1 из ключей y и последние t его потомков. Медианный из ключей узла y попадает в узел х, а указатель на y в узле x заменяется указателями на узлы y1 и y2.
2. Если x — лист, просто добавляем туда ключ K.

Теперь определим добавление ключа K ко всему дереву. Буквой R обозначается корневой узел.

1. Добавим K к дереву потомков R.
2. Если R содержит теперь 2t − 1 ключей, расщепляем его на два. Узел R1 получает первые t − 1 из ключей R и первые t его потомков, а узел R2 — последние t − 1 из ключей R и последние t его потомков. Медианный из ключей узла R попадает вo вновь созданный узел, который становится корневым. Узлы R1 и R2 становятся его потомками.

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

Существует одна уловка, позволяющая ускорить в некоторых ситуациях вставку данных: вокруг каждого блока данных можно зарезервировать свободное место. Все такие записи будут помечены как «удалённые». И таким образом, перестраивать дерево придётся гораздо реже – только в тех случаях, когда кончается зарезервированное место.

3. Удаление ключа

При удалении ключа могут возникнуть две проблемы:

1. Удалённый ключ мог быть разделителем потомков внутри какого-либо нелистового узла
2. После удаления ключа в узле может остаться менее допустимого m/2 числа потомков

Для того чтобы избежать эти проблемы при удалении ключа, также, как и при вставке, требуется перебалансировка дерева. Существуют две стратегии: перебалансировка после удаления ключа и заранее. Мы будем рассматривать первый вариант. Алгоритм:

1. Если корень одновременно является листом, то есть в дереве всего один узел, мы просто удаляем ключ из этого узла. В противном случае сначала находим узел, содержащий ключ, запоминая путь к нему. Пусть этот узел — x.
2. Если x — лист, удаляем оттуда ключ.
   1. Если в узле x осталось не меньше t − 1 ключей, мы на этом останавливаемся. Иначе мы смотрим на количество ключей в следующем, а потом в предыдущем узле.
   2. Если следующий узел есть, и в нём не менее t ключей, мы добавляем в x ключ-разделитель между ним и следующим узлом, а на его место ставим первый ключ следующего узла, после чего останавливаемся.
   3. Если это не так, но есть предыдущий узел, и в нём не менее t ключей, мы добавляем в x ключ-разделитель между ним и предыдущим узлом, а на его место ставим последний ключ предыдущего узла, после чего останавливаемся.
   4. Наконец, если и с предыдущим ключом не получилось, мы объединяем узел x со следующим или предыдущим узлом, и в объединённый узел перемещаем ключ, разделяющий два узла. При этом в родительском узле может остаться только t − 2 ключей. Тогда, если это не корень, мы выполняем аналогичную процедуру с ним.
   5. Если мы в результате дошли до корня, и в нём осталось от 1 до t − 1 ключей, делать ничего не надо, потому что корень может иметь и меньше t − 1 ключей.
   6. Если же в корне не осталось ни одного ключа, исключаем корневой узел, а его единственный потомок делаем новым корнем дерева.
3. Если x — не лист, а K — его i-й ключ, удаляем самый правый ключ из поддерева потомков i-го сына x, или, наоборот, самый левый ключ из поддерева потомков i + 1-го сына x.
   1. После этого заменяем ключ K удалённым ключом. Удаление ключа происходит так, как описано в п.2.

4. Конструирование с нуля

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

Правило: изначально все узлы кроме последнего содержат один дополнительный элемент (то есть m+1 потомков в сумме), который будет использован для построения внутренних узлов.

Для наглядности рассмотрим алгоритм на примере. Пусть количество потомков для каждого листового узла у нас не более 4, то есть число m = 5. На вход подана последовательность чисел от 1 до 24. Разобьём их на блоки по заданному правилу:

1|2|3|4|5   6|7|8|9|10   11|12|13|14|15   16|17|18|19|20   21|22|23|24

Из слоя листовых узлов мы строим следующий уровень путём вынесения туда лишних (в данном случае пятых) элементов на уровень выше. И новый уровень также разбиваем в соответствии с правилом. Пусть для внутренних (нелистовых) узлов у нас будет ограничение 2 на количество потомков. Тогда мы получим:

5|10|15   20

1|2|3|4   6|7|8|9   11|12|13|14   16|17|18|19   21|22|23|24

Продолжаем процесс, пока не получим корень.

15

5|10   20

1|2|3|4   6|7|8|9   11|12|13|14   16|17|18|19   21|22|23|24

Осталось добавить ссылки и получится готовое В-дерево!

Основные достоинства

• Во всех случаях полезное использование пространства вторичной памяти занимает свыше 50 %. С ростом степени полезного использования памяти не происходит снижения качества обслуживания.
• Произвольный доступ к записи реализуется посредством малого количества подопераций (обращения к физическим блокам).
• В среднем достаточно эффективно реализуются операции включения и удаления записей; при этом сохраняется естественный порядок ключей с целью последовательной обработки, а также соответствующий баланс дерева для обеспечения быстрой произвольной выборки.
• Неизменная упорядоченность по ключу обеспечивает возможность эффективной пакетной обработки.

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