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

Обозначим записи, размещенные в одной вершине дерева, через Rp R₂, ..., Rp а указатели на подчиненные вершины через Р₀, Р_р Р₇, ..., Р.. Кдждая запись Rj содержит соответствующие значения ключа Kj и Rowldj. Тогда структура вершины будет следующей:

Р₀ R_l Р, R₂ Р₂ ••• Pj.j Rj Pj-

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

• 1. Ключи записей в текущей вершине упорядочены по возрастанию, т.е. ключ записи Я, меньше ключа записи Я₂, который, в свою очередь, меньше ключа записи и т.д.
• 2. Записи в подчиненной вершине, на которую указывает Р₀, имеют ключи, меньшие, чем ключ записи
• 3. Записи в подчиненной вершине, на которую указывает имеют ключи, большие, чем ключ записи Я..
• 4. Записи в подчиненной вершине, на которую указывает Р₁
• (О < [ < ]), имеют ключи, большие, чем ключ записи и мень

шие, чем ключ записи Я₁₊₁.

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

а)дерево порядка 1

6} дерево порядка 2

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

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

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

• • сохранять сбалансированность В-дерева и степень заполнения его вершин;
• • не нарушать упорядоченности записей;
• • свести к минимуму перемещение информации.

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

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

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

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

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

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

а) до всгваки

6} посла »ставки

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

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

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

• а) переполнение листа
• 15
• 37

5) после расщепления листа

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

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

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

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

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

а} б)

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

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

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

• 3. Элемент с ключом 3 вставляется в самый левый лист (рис. 9.11).
• 4. Элемент с ключом 5 также должен быть вставлен в самый левый лист; получаем переполнение — 3, 5, 12, и элемент из средней позиции перемещается в родительскую вершину, в которой есть свободное место (рис. 9.12).
• 5. Следующий элемент (70) вставляется в самый правый лист, в котором есть свободная позиция (рис. 9.13).

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

5) расцепление листа

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

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

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

а) результат расщепления листа

б) результат расщепления промежуточной вершины

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В соседней вершине имеется 5 элементов, поэтому можно выполнить перераспределение элементов. В результате объединения полу-

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

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

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

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

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

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

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

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

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

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

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

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

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

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

листьев

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

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

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

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

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

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