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

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

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

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

Каждый узел может иметь до $m$ дочерних узлов.
Каждый нелистовой узел (кроме корневого) имеет как минимум $\lceil{m/2}\rceil$ узлов.
Корневой узел имеет минимум 2 дочерних узла, за исключением случая, когда он является и листовым.
Нелистовой узел с $k$ дочерними узлами содержит $k - 1$ ключ.
Глубина всех листов одинакова.

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

Ключи узла $x$ — $x.key_1, x.key_2,..., x.key_n$ хранятся в неубывающем порядке: $x.key_1 \leqslant x.key_2 \leqslant ... \leqslant x.key_n$ .
Каждый внутренний узел также содержит $n+1$ указателей $c.key_1, c.key_2,..., c.key_{n+1}$ на дочерние узлы. Листовые узлы не имеют потомков, поэтому не содержат указателей.
Ключи $x.key_i$ ограничивают диапазон возможных ключей, хранящихся в каждом поддереве: пусть $k_i$ произвольный ключ в поддереве некоторого узла $x$ , тогда: $k_1 \leqslant x.key_1 \leqslant k_2 \leqslant x.key_2 \leqslant ... \leqslant x.key_n \leqslant k_{n+1}$
Узел имеет минимальное и максимальное число элементов, которое он может хранить. Определим эти числа через целое число , называемое степенью B-дерева, тогда:
1. Каждый узел кроме корневого должен иметь, по крайней мере, $t-1$ ключей. Каждый внутренний узел кроме корневого в таком случае хранит по крайней мере $t$ узлов. Если дерево непустое, то узел должен иметь как минимум один ключ.
2. Каждый узел может иметь до $2t - 1$ ключей. Поэтому, внутренний узел может содержать максимум $2t$ узлов. Узлы, содержащие ровно $2t - 1$ ключей являются полными

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

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

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

$i$

$k \leqslant x.key_i$

$k = x.key_i$

$c.key_i$

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

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

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

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

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

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

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

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

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

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

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

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 на любой странице сайта.