Изменения

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

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

B-дерево имеет следующие свойства ($<tex>t$ </tex> — параметр дерева, называемый ''минимальной степенью'' B-дерева, не меньший $<tex>2$</tex>.):* Каждый узел, кроме корня, содержит не менее $<tex>t - 1$ </tex> ключей, и каждый внутренний узел имеет по меньшей мере $<tex>t$ </tex> дочерних узлов. Если дерево не является пустым, корень должен содержать как минимум один ключ. * Каждый узел, кроме корня, содержит не более $<tex>2t - 1$ </tex> ключей и не более чем $<tex>2t$ </tex> сыновей во внутренних узлах* Корень содержит от $<tex>1$ </tex> до $<tex>2t - 1$ </tex> ключей, если дерево не пусто и от $<tex>2$ </tex> до $<tex>2t$ </tex> детей при высоте большей <tex>0</tex>.* Каждый узел дерева, кроме листьев, содержащий ключи $<tex>k_1, ..., k_n$</tex>, имеет $<tex>n + 1$ </tex> сына. $<tex>i$</tex>-й сын содержит ключи из отрезка $<tex>[k_{i - 1}; k_i],\: k_0 = -\infty,\: k_{n + 1} = \infty$</tex>.

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

Для того чтобы снизить время ожидания, связанное с механическим перемещением, при обращении к диску выполняется обращение одновременно сразу к нескольким элементам, хранящимся на диске. Информация разделяется на несколько страниц одинакового размера, которые хранятся последовательно друг за другом в пределах одного цилиндра (набора дорожек на дисках на одном расстоянии от центра), и каждая операция чтения или записи работает сразу с несколькими страницами. Для типичного диска размер страницы варьируется от $<tex>2$ </tex> до $<tex>16$ </tex> КБайт. После того, как головка установлена на нужную дорожку, а диск поворачивается так, что головка становится на начало интересующей нас страницы, чтение и запись становятся полностью электронными процессами, не зависящими от поворота диска, и диск может быстро читать или писать крупные объёмы данных.

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

{{Теорема|statement=Если $<tex>n \geqslant 1$</tex>, то для B-дерева $<tex>T$ </tex> c $<tex>n$ </tex> узлами и минимальной степенью $<tex>t \geqslant 2$ </tex> имеется следующее неравенство::$<tex>h \leqslant$ $</tex> <tex>\log_t\dfrac{n+1}{2}$</tex>

Корень B-дерева $<tex>T$ </tex> содержит по меньшей мере один ключ, а все остальные узлы — хотя бы $<tex>t - 1$ </tex> ключей. Так, <tex>T</tex>, высота которого $<tex>h$</tex>, имеет хотя бы $<tex>2$ </tex> узла на глубине $<tex>1$</tex>, хотя бы $<tex>2t$ </tex> узла на глубине $<tex>2$</tex>, хотя бы $<tex>2t^2$ </tex> узла на глубине $<tex>3$</tex>, и так далее, до глубины $<tex>h$</tex>, оно имеет по меньшей мере $<tex>2t^{h-1}$ </tex> узлов. Так, число ключей $<tex>n$ </tex> удовлетворяет неравенству:::$<tex>n \geqslant 1+(t-1)\sum\limits_{i = 1}^h 2t^{i-1} $</tex>:::$<tex>=1+2(t-1)(\dfrac{t^h-1}{t-1})$</tex>:::$<tex>=2t^h-1$</tex>.

Простейшее преобразование дает нам неравенство $<tex>t^h \leqslant (n+1)/2$</tex>. Логарифмирование по основанию $<tex>t$ </tex> обеих частей неравенства доказывает теорему

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

[[Файл:B3inssp.png|550px|Разбиение корня с <tex>t = 4</tex>. Корневой узел <tex>r </tex> разделяется на два узла, и создаётся новый корень <tex>s</tex>. Новый корень содержит средний ключ <tex>r </tex> и две половины <tex>r </tex> в качестве детей. Разбиением узла высота дерева увеличивается на единицу]]

Вставка ключа в B-дерево $<tex>T$ </tex> высоты $<tex>h$ </tex> за один нисходящий проход по дереву потребует $<tex>O(h)$ </tex> обращений к диску и $<tex>O(th)=O(t \log_t n)$ </tex> процессорного времени.

Функция $<tex>\operatorname{B-Tree-Insert-Nonfull}$ </tex> вставляет ключ $<tex>k$ </tex> в узел $<tex>x$</tex>, который должен быть незаполненным при вызове. Использование функции $<tex>\operatorname{B-Tree-Split-Child}$ </tex> гарантирует, что рекурсия не встретится с заполненным узлом.Ниже показана вставка ключей <tex>B</tex>, <tex>Q</tex>, <tex>L </tex> и <tex>F </tex> в дерево с $<tex>t = 3$</tex>, т.е. узлы могут содержать не более <tex>5 </tex> ключей

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

[[Файл:B3splt.PNG|550px|Разбиение узла B-дерева с <tex>t=4</tex>]]

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

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

[[Файл:B3dell.PNG|550px|Удаление <tex>F </tex> из листа]]В противном случае, если существует соседний лист с тем же родителем, который содержит больше $<tex>t - 1$ </tex> ключа, выберем ключ-разделитель из соседа разделяющий оставшиеся ключи соседа и ключи исходного узла (то есть не больше всех из одной группы и не меньше всех из другой). Обозначим этот ключ как $<tex>k_1$</tex>. Выберем другой ключ из родительского узла, разделяющий исходный узел и его соседа, который был выбран ранее. Этот ключ обозначим $<tex>k_2$</tex>. Удалим из исходного узла лист, который нужно было удалить, спустим в этот узел $<tex>k_2$</tex>, а вместо $<tex>k_2$ </tex> в родительском узле поставим $<tex>k_1$</tex>. Если все соседи содержат по $<tex>t - 1$ </tex> ключу, то [[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|переместим]] в новый узел.

Рассмотрим удаление из внутреннего узла. Имеется внутренний узел $<tex>x$ </tex> и ключ, который нужно удалить, $<tex>k$</tex>. Если дочерний узел, предшествующий ключу $<tex>k$</tex>, содержит больше $<tex>t - 1$ </tex> ключа, то находим $<tex>k_1$ </tex> – предшественника $<tex>k$ </tex> в поддереве этого узла. Удаляем его. Заменяем $<tex>k$ </tex> в исходном узле на $<tex>k_1$</tex>. Проделываем аналогичную работу, если дочерний узел, следующий за ключом $<tex>k$</tex>, имеет больше $<tex>t - 1$ </tex> ключа. Если оба (следующий и предшествующий дочерние узлы) имеют по $<tex>t - 1$ </tex> ключу, то [[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|переносим]] в них $<tex>k$</tex>, а далее удаляем $<tex>k$ </tex> из нового узла. Если [[B-дерево#.D0.A1.D0.BB.D0.B8.D1.8F.D0.BD.D0.B8.D0.B5|сливаются]] <tex>2 </tex> последних потомка корня – то они становятся корнем, а предыдущий корень освобождается.

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

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

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

Итак, если выбранное для спуска поддерево $<tex>x.c_2$ </tex> и предшествующий и следующий узел-брат содержит минимальное количество ключей, то перемещение не возможно. На иллюстрации приводится слияние выбранного поддерева с предшествующим или следующим братом для такого случая. Для этого откладывается ключ из родительского узла $<tex>x$</tex>, который разделяет ключи на два сливаемых узла, в то время средний ключ перемещается в слитый узел. Ссылки на слитые дочерние узлы заменяются ссылкой на новый узел.

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

Распространённая модификация B-дерева, в которой каждый внутренний узел должен быть заполнен как минимум на две трети, а не наполовину, как в случае со стандартным B-деревом. Используется в файловых системах HFS и Reiser4. В отличие от B+-деревьев, узел не разбивается на <tex>2 </tex> узла, если полностью заполнен. Вместо этого ищется место в уже существующем соседнем узле, и только после того, как оба узла будут заполнены, они разделяются на три узла.

Производное от B+-дерева. Каждый узел может иметь либо <tex>2</tex>, либо <tex>3 </tex> ребёнка.