B-дерево

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

Название «В-дерево» можно объяснить двумя способами:

а) от слова Balanced – сбалансированное дерево, в котором все листья имеют один и тот же уровень;

б) от Bayer – автора данной структуры.

Введем определение В-дерева.

Определение:

В-деревом порядка n называется структура, обладающая следующими свойствами:

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

2. В каждой вершине дерева, за исключением корня, должно располагаться минимум n, максимум 2n ключей.

3. В корне В-дерева может располагаться минимум 1, максимум 2n ключей.

4. Любая вершина дерева, за исключением листьев, имеющая j ключей, должна иметь j+1 подчиненную вершину.

Последнее условие означает, что промежуточные вершины В-дерева имеют от n+1 до 2n+1 указателей на подчиненные вершины, а корень дерева – от 2 до 2n+1 указателей.

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

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

Структура вершины В-дерева

Обозначим записи, размещенные в одной вершине дерева, через R₁, R₂, …, R_j, а указатели на подчиненные вершины через P₀, P₁, P₂, …, P_j. Тогда структура вершины будет следующей:

P₀ R₁ P₁ R₂ P₂ … P_j-1 R_j P_j

Правила следования:

1. Ключи записей в текущей вершине упорядочены по возрастанию, т.е. ключ записи R₁ меньше ключа записи R₂, который, в сою очередь, меньше ключа записи R₃, и т.д.

1. Записи в подчиненной вершине, на которую указывает P₀, имеют ключи, меньшие, чем ключ записи R₁.

2. Записи в подчиненной вершине, на которую указывает P_j, имеют ключи, большие, чем ключ записи R_j.

Записи в подчиненной вершине, на которую указывает P_i (0 < i < j), имеют ключи, большие, чем ключ записи R_i, и меньшие, чем ключ записи R_i+1.

Ниже приведены примеры В-деревьев порядка 1 и порядка 2 (Рис. 7.6).

Рис. 7.6. Примеры В-деревьев

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

Операции включения и удаления должны:

1. сохранять сбалансированность В-дерева и степень заполнения его вершин;

2. не нарушать упорядоченности записей;

3. свести к минимуму перемещение информации.

Операция вставки

Операции вставки предшествует поиск, который должен завершиться не успешно.

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

Когда целевая вершина (лист) В-дерева будет найдена, можно столкнуться со следующими ситуациями.

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

Пусть, например, имеется следующий фрагмент В-дерева порядка 2 (Рис. 7.7, а; для удобства, на рисунке листья В-дерева пронумерованы). Необходимо вставить элемент с ключом 7. Новый элемент должен быть размещен в листе с номером 2, в котором есть свободные позиции. В результате выполнения операции вставки получим новое В-дерево (Рис. 7.7, б).

Рис. 7.7. Реализация операции вставки в В-дерево

2. Случай переполнения вершины: найденный целевой лист заполнен полностью. При вставке нового элемента в целевой лист получим последовательность из 2n+1 ключей, тогда как в листе могут находиться максимум 2n ключей. В этом случае выполняется операция расщепления листа: ключ из средней позиции переносится в родительскую вершину, а на уровне листьев появляются два новых листа.

Рассмотрим пример. Пусть в представленное выше дерево порядка 2 (Рис. 7.8, а) вставляется элемент с ключом 37. Поэтому получим последовательность ключей: 7, 10, 15, 23, 37. В средней позиции находится элемент с ключом 15; он перемещается в родительскую вершину, и появляются два новых листа (Рис. 7.8, б).

Рис. 7.8. Появление новых листьев при вставке в В-дерево

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

Рассмотрим пример вставки нескольких значений в В-дерево порядка 1.

Пусть вставляется следующая последовательность элементов: 20, 12, 48, 3, 5, 70, 101.

1. Первые два элемента заполняют первый лист, который является одновременно и корнем В-дерева (Рис. 7.9).

Рис. 7.9. Вставка первых элементов в В-дерево

2. Вставляется следующий элемент – 48. Получаем переполнение: 12, 20, 48. Элемент из средней позиции поднимается вверх и создает новую вершину – корень В-дерева, которой подчинены два листа (Рис. 7.10).

Рис. 7.10. Вставка элемента 48 в В-дерево

3. Элемент с ключом 3 вставляется в самый левый лист (Рис. 7.11).

Рис. 7.11. Вставка элемента 3 в В-дерево

4. Элемент с ключом 5 также должен быть вставлен в самый левый лист; получаем переполнение – 3, 5, 12, и элемент из средней позиции перемещается в родительскую вершину, в которой есть свободное место (Рис. 7.12).

Рис. 7.12. Вставка элемента 5 в В-дерево

5. Следующий элемент (70) вставляется в самый правый лист, в котором есть свободная позиция (Рис. 7.13).

Рис. 7.13. Вставка элемента 70 в В-дерево

6. В тот же лист должен быть вставлен следующий элемент с ключом 101; получаем переполнение – 48, 70, 101, и элемент из средней позиции перемещается в родительскую вершину. В родительской вершине также возникает переполнение – 5, 20, 70; в результате перемещения элемента из средней позиции образуется новая вершина – корень В-дерева (Рис. 7.14), и высота дерева увеличивается на 1.

Рис. 7.14. Вставка элемента 101 в В-дерево

Процесс вставок можно продолжать, включая в дерево новые элементы.

Таким образом, при вставке элементов в дерево В-дерево растет вверх – появляется новый корень, хотя новый элемент вставляется в лист дерева.

Удаление элемента

Ключ из В-дерева индексов удаляется из-за удаления записи из таблицы (из области данных). Операции удаления ключа предшествует успешный поиск вершины, в которой размещается удаляемый ключ.

Прежде всего, рассмотрим следующие две ситуации.

1. Искомый ключ находится в листе дерева. В этом случае операция удаления не затрагивает глобально структуру В-дерева.

2. Искомый ключ находится в промежуточной вершине. Удаление ключа не должно разрушить структуру В-дерева, поэтому в такой ситуации обычно используется один из двух (равноправных) подходов:

а) удаляемый ключ замещается элементом с минимальным значением ключа из правого поддерева, подчиненного удаляемому элементу;

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

И в том, и в другом случае в итоге приходим к необходимости удалить элемент из листа дерева. Поэтому в дальнейшем будем рассматривать все примеры, удаляющие элементы из листьев дерева.

Конкретный алгоритм удаления должен использовать какой-то один из двух подходов. Будем использовать подход а).

При удалении элемента из листа также можно столкнуться с двумя ситуациями.

1. Простейшая ситуация, когда в листе находится более чем n элементов (n – порядок В-дерева). В этом случае удаление элемента не нарушает структуру В-дерева и заканчивается сразу же.

Рассмотрим пример. Пусть имеется следующий фрагмент В-дерева порядка 2 (Рис. 7.15).

Рис. 7.15. Фрагмент В-дерева порядка 2 до удаления элемента

Пусть требуется удалить элемент с ключом 20. Удаляемый элемент находится в промежуточной вершине В-дерева. В правом поддереве, подчиненном удаляемому элементу, находим минимальный элемент – это 21, и перемещаем его на место удаляемого элемента. Поскольку лист был заполнен более чем наполовину, после перемещения элемента в нем осталось необходимое количество элементов. В итоге получим следующее состояние В-дерева (Рис. 7.16).

Рис. 7.16. Фрагмент В-дерева порядка 2 после удаления элемента

2. Случай антипереполнения вершины: в целевом листе находится минимально допустимое количество элементов. При удалении элемента в листе остается недостаточное количество элементов – возникает антипереполнение, которое должно быть устранено.

Антипереполнение устраняется одним из двух способов: с помощью перераспределения элементов или с помощью сцепления вершин. Рассмотрим эти способы.

Перераспределение элементов

Рассматриваются соседние вершины дерева (слева или справа), подчиненные той же вершине и тому же ключу, что и целевая. Если хотя бы в одной из них имеется более n записей (где n – порядок В-дерева), выполняется перераспределение элементов.

Для этого объединяются оставшиеся элементы из целевой вершины (в количестве n – 1), выбранной соседней вершины (в количестве n + 1 + m, где m ≥ 0) и их общий корень. В результате объединения будет получено (n – 1) + (n + 1 + m) + 1 = 2n + 1 + m вершин, где m ≥ 0. Эти элементы перераспределяются между целевой и соседней вершинами так, что в каждой из них появится минимум n элементов, и один элемент поднимется в родительскую вершину. Отсюда видно, что операция перераспределения обратна операции расщепления, выполняемой при вставке элементов.

Рассмотрим пример. Пусть дан следующий фрагмент В-дерева порядка 3 (Рис. 7.17).

Рис. 7.17. Фрагмент В-дерева порядка 3 до удаления элемента

Пусть удаляется элемент с ключом 276. В целевой вершине остается 2 элемента, что недостаточно.

В соседней вершине имеется 5 элементов, поэтому можно выполнить перераспределение элементов. В результате объединения получим 5 (левый лист) + 1 (родительская вершина) + 2 (целевой лист) = 8 элементов. Эти элементы могут быть перераспределены между вершинами, например, так, как показано на Рис. 7.18.

Рис. 7.18. Фрагмент В-дерева порядка 3 после удаления элемента

В результате получена структура, удовлетворяющая определению В-дерева.

Сцепление вершин

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

Рассмотрим пример. Пусть дан следующий фрагмент В-дерева порядка 2 (Рис. 7.19).

Рис. 7.19. Фрагмент В-дерева порядка 2 до слияния листьев

Удаляется элемент 15. В результате сцепления получим один лист и один указатель на него (Рис. 7.20).

Рис. 7.20. Фрагмент В-дерева порядка 2 после слияния листьев

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

Рассмотрим пример. Пусть дано В-дерево порядка 1 (Рис. 7.21).

Рис. 7.21. Пример В-дерева порядка 1

Удаляется элемент 150. В соседней вершине только один элемент, поэтому выполняется сцепление. В результате возникло антипереполнение в родительской вершине (Рис. 7.22).

Рис. 7.22. Промежуточное состояние В-дерева после слияния листьев

Для данной вершины также выполняется сцепление, в результате которого в корне В-дерева не осталось ни одного элемента (Рис. 7.23). В такой ситуации пустая вершина – корень В-дерева удаляется, и высота дерева уменьшается на 1.

Рис. 7.23. Состояние В-дерева после слияния промежуточных вершин

Таким образом, можно указать следующие основные свойства В-дерева:

1. Ключи и ассоциированные с ними данные хранятся во всех вершинах В-дерева.

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

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

1. В+ дерево

Чтобы устранить недостатки, свойственные В-дереву при выполнении последовательной выборки данных, было введено В+ дерево.

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

Различие между В+ деревом от В-деревом заключается в следующем.

В В-дереве все вершины дерева равноправны и содержат ключи и ассоциированные с ними данные.

В В+ дереве выделяются два типа вершин: промежуточные вершины индексов и листья. Ключи и ассоциированные с ними данные размещаются только в листьях. Листья объединяются в связанное последовательное упорядоченное множество. Это позволяет эффективно выполнять последовательные запросы. Доступ к листьям осуществляется через промежуточные вершины В+ дерева, организованные в виде обычного В-дерева индексов (Рис. 7.24).

Рис. 7.24. Структура В+ дерева

Исходя из этого, В+ дерево можно определить (используя введенное ранее определение В-дерева) следующим образом.

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

2. Все ключи в В+ дереве хранятся в листьях. Для обеспечения правильного доступа отдельные ключи могут дублироваться и в промежуточных вершинах индексов.

3. Доступ к информации в В+ дереве выполняется всегда за h шагов, где h – высота В+ дерева.

4. Выполнение операций включения и удаления в В+ дереве несколько отличается от выполнения соответствующих операций в В-дереве.

Операция включения

В+ дерево также растет от листьев к корню. Включение начинается с листьев. Также в случае переполнения выполняется расщепление вершины, но в В+ дереве по-разному выполняется расщепление листа и расщепление промежуточной вершины дерева. При расщеплении листа в В+ дереве ключ, расположенный в средней позиции листа, перемещается в родительскую вершину и остается в листе – в правом или левом, но в каком-то одном для всех операций вставки. Расщепление промежуточной вершины В+ дерева выполняется точно так же, как и в В-дереве.

Рассмотрим особенности выполнения операции включения на примере. Пусть в В+ дерево порядка 1 включаются те же элементы и в том же порядке, что и в В-дерево, рассмотренное ранее (Рис. 7.9 – Рис. 7.14): 20, 12, 48, 3, 5, 70, 101.

1. Включение первых двух элементов ничем не отличается от их включения в В-дерево (Рис. 7.25).

Рис. 7.25. Включение первых двух элементов в В+ дерево

2. Включение третьего элемента вызывает переполнение листа: 12, 20, 48. Элемент из средней позиции перемещается в родительскую вершину, в результате чего создается новый корень В+ дерева (Рис. 7.26). Но так как в В+ дереве все ключи должны находиться в листьях, перемещаемый элемент остается и в одном из двух листьев – например, в левом (примем для определенности).

Рис. 7.26. Включение элемента 48 в В+ дерево

3. Включение следующего элемента (3) также вызывает переполнение левого листа: 3, 12, 20. Элемент из средней позиции перемещается в родительскую вершину, в которой есть свободная позиция, и остается в левом листе (Рис. 7.27).

Рис. 7.27. Включение элемента 3 в В+ дерево

4. Элемент 5 также должен быть размещен в левом листе – возникает переполнение: 3, 5, 12. В результате расщепления вершины элемент из средней позиции перемещается в родительскую вершину, в которой возникает переполнение: 5, 12, 20, и сохраняется в левом листе. Переполнение родительской вершины обрабатывается по правилам В-дерева – образуются две вершины с элементами 5 в левой и 20 в правой, а элемент 12 перемещается в родительскую вершину – создается новый корень В+ дерева (Рис. 7.28).

Рис. 7.28. Включение элемента 5 в В+ дерево

5. Элемент 70 должен быть размещен в самом правом листе – в нем есть свободная позиция, поэтому реорганизация дерева не происходит (Рис. 7.29).

Рис. 7.29. Включение элемента 70 в В+ дерево

6. Включение последнего элемента (101) вызывает переполнение: 48, 70, 101. В результате расщепления вершины появляются два новых листа, элемент 70 сохраняется в левом листе и дублируется в родительской вершине, в которой есть свободная позиция (Рис. 7.30).

Рис. 7.30. Включение элемента 101 в В+ дерево

Удаление элемента

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

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

Рассмотрим пример. Пусть дан следующий фрагмент В+ дерева порядка 2 (Рис. 7.31).

 

Рис. 7.31. Фрагмент В+ дерева порядка 2 до удаления элемента

Если удаляется элемент 31 – он просто удаляется из листа. Так как при этом антипереполнение в листе не возникает, операция удаления заканчивается, и ключ 31 сохраняется в промежуточной вершине В-дерева индексов ().

Рис. 7.32. Фрагмент В+ дерева порядка 2 после удаления элемента

Если на следующем этапе удаляется элемент 22, в листе возникает антипереполнение. Поскольку соседний лист содержит минимально допустимое количество элементов, выполняется слияние двух листов. При этом ключ 31 из промежуточной вершины В-дерева индексов удаляется (Рис. 7.33).

Рис. 7.33. Слияние листьев при удалении элемента из В+ дерева

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

Рассмотрим следующий фрагмент В+ дерева порядка 2 (Рис. 7.34), полученный также после удаления элемента 31.

Рис. 7.34. Фрагмент В+ дерева порядка 2

Если теперь удаляется элемент 22, в листе возникает антипереполнение. Поскольку соседний лист содержит максимально возможное количество элементов, выполняется перераспределение: объединяются данные из левого листа (17), родительской вершины (31) и правого листа (51, 62, 68, 73), при этом ранее удаленный элемент 31 удаляется. Для полученной последовательности ключей (17, 51, 62, 68, 73) средний элемент перемещается в родительскую вершину и остается в левом листе. В результате получаем следующий фрагмент В+ дерева (Рис. 7.35).

Рис. 7.35. Перераспределение элементов при удалении из В+ дерева