B-дерево и его разновидности

B-дерево (читается как «би-дерево», первая латинская буква «B» не означает ничего конкретного) — самобалансирующее дерево поиска, которое проектировалось для эффективного доступа к данным на внешних хранилищах (в 1970 речь идёт о HDD). В отличии от Красно-Чёрного дерева или АВЛ-дерева каждый узел в B-дереве может иметь несколько ключей, которые используются для поиска элемента (здесь и далее иллюстрации приведены из Кормена Т., Алгоритмы. Построение и анализ):

Типичное B-дерево
Рис. 1. B-дерево, ключами которого являются согласные буквы английского алфавита. Любой внутренний узел x, содержащий n ключей, имеет n + 1 дочерних узлов. Все листы находятся на одинаковой глубине. Бледно-серые узлы участвовали в поиске узла с ключём R

Для B-дерева справедливы следующие ограничения:

Для каждого узла дерева справедливы утверждения:

Операции с B-деревом

Поиск элемента

Чтобы найти ключ в дереве достаточно выполнить следующую последовательность действий:

    1. Загрузить очередной блок (узел) в память с диска.
    2. Используя линейный поиск, найти наименьший индекс i ключа для которого справедливо, что k \leqslant x.key_i.
    3. Если при этом k = x.key_i, то искомый элемент найден и алгоритм заканчивает свою работу.
    4. Если узел листовой, то элемент не найден и алгоритм заканчивает работу. В противном случае загрузить блок по адресу c.key_i и перейти к п. 2.

Количество чтений с диска

Поскольку при поиске ключа самой долгой операцией является чтения блоков с диска (где под блоком понимается обычно один узел), необходимо уметь находить количество чтений для n элементов. Оно в точности совпадает с высотой дерева, которую для заданной степени t можно расчитать по формуле:

h \leqslant \log_t\frac{n+1}{2}

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

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

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

Разбиение узла

Типичное B-дерево
Рис. 2. Разбиение узла при t = 4. Узел y = x.c_i распадается на два, а ключ S, являющийся медианой, переносится в родительский узел

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

В качестве упражнение заполните промежуточные операции на приведённой ниже иллюстрации.

Типичное B-дерево
Рис. 3. Разные операции вставки в B-дерево

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

Легко понять, что для удаления ключ из дерева достаточно провести процедуру обратную к добавленю. Важно, что при удалении существует возможность удалить ключ из любого узла, а не только листового. Тогда для удаления ключа необходимо для каждого узла, начиная от корневого, проверять слелующие шаги:

Рис. 4. Исходное дерево

1. Если ключ k находится в узле x, являющийся листом, то удалить ключ k из x:

Рис. 5. Удаление ключа «F» из листового узла

2. Если ключ k находится в узле x, являющийся внутренним узлом, то:

Случай 2a: если дочерний элемент y, который предшествует ключу k в узле x, содержит как минимум t ключей, тогда найти в поддереве узла y элементk', предшествующий k. Рекурсивно удалить k' и заменить k на k' в узле x.

Рис. 6. Удаление ключа «M» и перенос ключа «L» в родительский узел

Случай 2b: если в y меньше t ключей, то проверить дочерний элемент z, который следует за k в узле x. Выполнить аналогичную случаю 2a проверку ключа, который идёт следующий по порядку после ключа x.

Случай 2c: если оба потомка y и z содержат только t - 1 ключ, то добавить k и все ключи z в y, после чего из x пропадают k и ссылка на z, а y содержит теперь ровно 2t - 1 ключей. После чего освободить z и рекурсивно удалить k из y.

Рис. 7. При удалении ключа «G» сначала он переносится так, чтобы создать новый узел «DEGJK», после чего удаляется как обычный ключ из листа

3. Если ключа k нет во внутреннем узле x, то находим поддерево x.c_i, которое должно содержать ключ k (если оно вообще есть в дереве). Если x.c_i содержит только t - 1 ключей, то выполнить 3a или 3b как необходимые шаги, чтобы гарантировать, что мы переходим к узлу, содержащему как миниум t ключей. Затем рекурсивно вызвать удаление ключа k из соответствующего дочернего узла.

Случай 3a: если x.c_i содержит только t - 1 ключ, но при этом имеет непосредственного соседа с не менее чем t ключами, то добавить в x.c_i дополнительный ключ путём переноса ключа из x вниз в x.c_i, а из соседского узла (справа или слева) перенести ключ в x и обновить ссылку.


Рис. 8. Удаление узла B: ключ C опускается влево, а ключ E поднимается выше

Случай 3b: если x.c_i и оба непосредственных соседа x.c_i содержат t - 1 ключ, то объединить x.c_i с одним из соседних узлов, что влечёт перемещение ключа из x вниз в новый объединённый узел и делает его медианным ключом для этого узла.


Рис. 9. Рекурсия не может спуститься к узлу CL поскольку он имеет только 2 ключа, поэтому мы перемещаем P ниже и объединяем с CL и TX, после чего удаляем узел D из листового узла. После чего высота дерева уменьшается на 1.

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

Нашли ошибку в тексте? Выделите ошибку в тексте и нажмите Ctrl + Enter на любой странице сайта.

Сообщить об опечатке

Текст, который будет отправлен нашим редакторам: