Изменения

<wikitex>'''B-дерево''' (англ. ''B-tree'') {{---}} сильноветвящееся сбалансированное дерево поиска, позволяющее проводить поиск, добавление и удаление элементов за $O(\log n)$. B-дерево с $n$ узлами имеет высоту $O(\log n)$. Количество детей узлов может быть от нескольких до тысяч (обычно степень ветвления B-дерева определяется характеристиками устройства (дисков), на котором производится работа с деревом). В-деревья также могут использоваться для реализации многих операций над динамическими множествами за время $O(\log n)$

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

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

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

<wikitex>B-деревья разработаны для использования на дисках (в файловых системах) или иных энергонезависимых носителях информации с прямым доступом, а также в базах данных. B-деревья похожи на красно-чёрные деревья (например, в том, что все В-деревья с $n$ узлами имеют высоту $O(\log n)$), но они лучше минимизируют количество операций чтения-записи с диском.</wikitex>

<wikitex>Кроме оперативной памяти, в компьютере используется внешний носитель, как правило, представляющий собой магнитные диски (или твердотельный накопитель). Хотя диски существенно дешевле оперативной памяти и имеют высокую емкость, они гораздо медленнее оперативной памяти из-за механического построения считывания.

Для больших В-деревьев, хранящихся на диске, степень ветвления обычно находится между <tex>50</tex> и <tex>2000</tex>, в зависимости от размера ключа относительно размера страницы. Большая степень ветвления резко снижает как высоту дерева, так и количество обращений к диску для поиска ключа. Например, если есть миллиард ключей, и $t=1001$, то поиск ключа займёт две дисковые операции. </wikitex>

<wikitex>Количество обращений к диску, необходимое для выполнения большинства операций с В-деревом, пропорционально его высоте. Проанализируем высоту В-дерева в наихудшем случае.

Здесь мы видим преимущества B-деревьев над красно-черными деревьями. Хотя высота деревьев растет как $O(\log t)$ в обоих случаях (вспомним, что t — константа), в случае B-деревьев основание логарифмов имеет гораздо большее значение. Таким образом, В-деревья требуют исследования примерно в $\log t$ раз меньшего количества узлов по сравнению с красно-черными деревьями в большинстве операций. Поскольку исследование узла дерева обычно требует обращения к диску, количество дисковых операций при работе с В-деревьями оказывается существенно сниженным.</wikitex>

<wikitex>Ищем лист, в который можно добавить ключ, совершая проход от корня к листьям. Если найденный узел незаполнен, добавляем в него ключ. Иначе разбиваем узел на два узла, в первый добавляем первые <tex>t - 1</tex> ключей, во второй — последние <tex>t - 1</tex> ключей. После добавляем ключ в один из этих узлов. Оставшийся средний элемент добавляется в родительский узел, где становится разделительной точкой для двух новых поддеревьев.

<wikitex>Функция $\operatorname{B-Tree-Split-Child}$ получает в качестве входного параметра незаполненный внутренний узел $x$ (находящийся в оперативной памяти), индекс $t$ и узел $y$ (также находящийся в оперативной памяти), такой что $y = c_i[x]$ является заполненным дочерним узлом $x$. Процедура разбивает дочерний узел на два и соответствующим образом обновляет поля $x$, внося в него информацию о новом дочернем узле. Для разбиения заполненного корневого узла мы сначала делаем корень дочерним узлом нового пустого корневого узла, после чего можно вызвать функцию. При этом высота дерева увеличивается на 1. Отметим, что увеличить высоту B-дерева можно только разбиением.

<wikitex>Операция удаления ключа несколько сложнее, нежели добавление оного, так как необходимо убедиться, что удаляемый ключ находится во внутреннем узле. Процесс похож на поиск подходящего места для вставки ключа, с той разницей, что перед спуском в поддерево проверяется, достаточность количества ключей (т.е. $\geqslant t$) в нем, а также возможность провести удаление, не нарушив структуры B-дерева. Таким образом, удаление аналогично вставке, и его проведение не потребует последующего восстановления структуры B-дерева. Если поддерево, выбранное поиском для спуска, содержит минимальное количество ключей $t-1$, производится либо перемещение, либо слияние. Удаление из листа и из внутреннего узла рассмотрено, а также операции слияния поддеревьев и перемещения ключей при удалении ключа рассмотрены ниже.Для удаления требуется время $O(t \log_t n)$ и $O(h)$ дисковых операций.</wikitex>

<wikitex>Если удаление происходит из листа, смотрим на количество ключей в нем. Если ключей больше $t - 1$, то просто удаляем ключ.

В противном случае, если существует соседний лист с тем же родителем, который содержит больше $t - 1$ ключа, выберем ключ-разделитель из соседа разделяющий оставшиеся ключи соседа и ключи исходного узла (то есть не больше всех из одной группы и не меньше всех из другой). Обозначим этот ключ как $k_1$. Выберем другой ключ из родительского узла, разделяющий исходный узел и его соседа, который был выбран ранее. Этот ключ обозначим $k_2$. Удалим из исходного узла лист, который нужно было удалить, спустим в этот узел $k_2$, а вместо $k_2$ в родительском узле поставим $k_1$. Если все соседи содержат по $t - 1$ ключу, то [[B-дерево#.D0.A1.D0.BB.D0.B8.D1.8F.D0.BD.D0.B8.D0.B5|объединяем]] узел с каким-либо из соседей, удаляем ключ, и ключ из родительского узла, который был разделителем разделённых соседей, [[B-дерево#.D0.9F.D0.B5.D1.80.D0.B5.D0.BC.D0.B5.D1.89.D0.B5.D0.BD.D0.B8.D0.B5_.D0.BA.D0.BB.D1.8E.D1.87.D0.B0|переместим]] в новый узел.</wikitex>

<wikitex>Рассмотрим удаление из внутреннего узла. Имеется внутренний узел $x$ и ключ, который нужно удалить, $k$. Если дочерний узел, предшествующий ключу $k$, содержит больше $t - 1$ ключа, то находим $k_1$ – предшественника $k$ в поддереве этого узла. Удаляем его. Заменяем $k$ в исходном узле на $k_1$. Проделываем аналогичную работу, если дочерний узел, следующий за ключом $k$, имеет больше $t - 1$ ключа. Если оба (следующий и предшествующий дочерние узлы) имеют по $t - 1$ ключу, то [[B-дерево#.D0.A1.D0.BB.D0.B8.D1.8F.D0.BD.D0.B8.D0.B5|объединяем]] этих детей, [[B-дерево#.D0.9F.D0.B5.D1.80.D0.B5.D0.BC.D0.B5.D1.89.D0.B5.D0.BD.D0.B8.D0.B5_.D0.BA.D0.BB.D1.8E.D1.87.D0.B0|переносим]] в них $k$, а далее удаляем $k$ из нового узла. Если [[B-дерево#.D0.A1.D0.BB.D0.B8.D1.8F.D0.BD.D0.B8.D0.B5|сливаются]] 2 последних потомка корня – то они становятся корнем, а предыдущий корень освобождается.

[[Файл:B3delin.png|550px|Удаление M и G из внутренних узлов]]</wikitex>

<wikitex>Если выбранное для нисходящего прохода поддерево содержит минимальное количеcтво ключей $t-1$, и предшествующие и следующие узлы-братья имеют по меньшей мере $t$ ключей, то ключ перемещается в выбранный узел. Поиск выбрал для спуска $x.c_2$ ($x.k_1<k_{delete}<x.k_2$). Этот узел имеет лишь $t-1$ ключ (красная стрелка). Так как следующий брат $x.c_3$ содержит достаточное количество ключей, самый маленький ключ $x.c_3.k_1$ может перемещаться оттуда в родительский узел, чтобы перестить, в свою очередь, ключ $x.k_2$ как дополнительный ключ в выбранный для спуска узел. Левое поддерево $x.c_3.k_1$ — новое правое поддерево перемещённого ключа $x.k_2$.

Легко убедиться в том, что эти повороты поддерживают структуру B-дерева: для всех ключей $k$ на отложенном поддереве до и после перенесения выполняется условие $x.k_2 \leqslant k \leqslant x.c_3.k_1$. Симметричная операция может производиться для перенесения ключа из предшествующего брата.</wikitex>

<wikitex>Ниже будет рассмотрено слияние узлов при удалении ключей, то есть слияние узлов равной степени и высоты. Для произвольных же слияний потребуется приведение сливаемых деревьев к одной степени и высоте.

Так как алгоритм гарантирует, что узел, в который будет совершаться спуск, содержит по меньшей мере $t$ ключей вместо требуемых условиями B-дерева $t - 1$ ключей, родительский узел $x$ содержит достаточное количество ключей, чтобы выделить ключ для слияния. Это условие может быть нарушено, только в том случае, если два ребенка корня сливаются, так как поиск начинается с этого узла. По условиям B-дерева у корня должен быть как минимум один ключ, если дерево не пусто. При слиянии двух последних детей корня последний ключ перемещается во вновь возникшего единственного ребёнка, что приводит к пустому корневому узлу в не пустом дереве. В этом случае пустой узел корня удаляется и заменяется на единственного ребенка.</wikitex>