B-дерево

B-дерево — дерево поиска, позволяющее проводить поиск, добавление и удаление элементов за [math]O(\log n)[/math].

B-дерево было впервые предложено Р. Бэйером и Е. МакКрейтом в 1970 году.

Структура

B-дерево является идеально сбалансированным, то есть глубина всех его листьев одинакова.

Каждый узел B-дерева, кроме корня, содержит от [math]t - 1[/math] до [math]2t - 1[/math] ключей. Корень содержит от [math]1[/math] до [math]2t - 1[/math] ключей. [math]t[/math] — параметр дерева, не меньший [math]2[/math]. Ключи в каждом узле упорядочены.

Каждый узел дерева, кроме листьев, содержащий ключи [math]k_1, ..., k_n[/math], имеет [math]n + 1[/math] сына. [math]i[/math]-й сын содержит ключи из отрезка [math][k_{i - 1}; k_i],\: k_0 = -\infty,\: k_{n + 1} = \infty[/math].

Назначение

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

Поиск ключа

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

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

Ищем лист, в который можно добавить ключ, совершая проход от корня к листьям. Если найденный узел не заполнен, добавляем в него ключ. Иначе разбиваем узел на два узла, в первый добавляем первые [math]t - 1[/math] ключей, во второй — последние [math]t - 1[/math] ключей. Добавляем ключ в один из этих узлов. Оставшийся средний элемент добавляем в узел родителя, если он заполнен — повторяем пока не встретим не заполненный узел или не дойдем до корня. В последнем случае корень разбивается на два узла и высота дерева увеличивается.

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

Находим ключ, который необходимо удалить

1. Если удаление происходит из листа, смотрим на количество ключей в нем. Если ключей больше [math]t - 1[/math], то просто удаляем ключ. В противном случае, если существует соседний лист, который содержит больше [math]t - 1[/math] ключа, удалим ключ из исходного узла, на его место поставим ключ-разделитель между исходным узлом и его соседом, а на его место поставим первый, если сосед правый, или последний, если сосед левый, ключ соседа. Если все соседи содержат по [math]t - 1[/math] ключу, то объединяем узел с каким-либо из соседей, удаляем ключ и добавляем ключ-разделитель между узлами в объединенный узел. Если в родительском узле осталось меньше [math]t - 1[/math] ключа, аналогичным образом добавляем в него ключи из соседей или объединяем узел в ними.
2. Если удаление происходит не из листа, удаляем самый левый ключ из поддерева следующего дочернего узла или самый правый из поддерева предыдущего дочернего узла и ставим удаленный ключ на место удаляемого ключа в исходном узле.

Ссылки

• T. H. Cormen «Introduction to Algorithms» third edition, Chapter 18

См. также

• 2-3 дерево
• Splay-дерево
• АВЛ-дерево
• Красно-черное дерево