Изменения

<wikitex>'''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 году.</wikitextex>году.

<wikitex>B-дерево является идеально сбалансированным, то есть глубина всех его листьев одинакова.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$.</wikitextex>.

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

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

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

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

<wikitex>Количество обращений к диску, необходимое для выполнения большинства операций с В-деревом, пропорционально его высоте. Проанализируем высоту В-дерева в наихудшем случае. {{Теорема|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\fracdfrac{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)(\fracdfrac{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> раз меньшего количества узлов по сравнению с красно-черными деревьями в большинстве операций. Поскольку исследование узла дерева обычно требует обращения к диску, количество дисковых операций при работе с В-деревьями оказывается существенно сниженным.</wikitex>

<wikitex>Ищем лист, в который можно добавить ключ, совершая проход от корня к листьям. Если найденный узел незаполнен, добавляем в него ключ. Иначе разбиваем узел на два узла, в первый добавляем первые <tex>t - 1</tex> ключей, во второй — последние <tex>t - 1</tex> ключей. Добавляем После добавляем ключ в один из этих узлов. Оставшийся средний элемент добавляется в родительский узел, где становится разделительной точкой для двух новых поддеревьев. [[Файл:B3inssp.png|550px|Разбиение корня с t = 4. Корневой узел r разделяется на два узла, и создаётся новый корень s. Новый корень содержит средний ключ r и две половины r в качестве детей. Разбиением узла высота дерева увеличивается на единицу]]  Если и родительский узел заполнен заполнен — повторяем пока не встретим незаполненный узел или не дойдем до корня. В последнем случае корень разбивается на два узла и высота дерева увеличивается.

[[Файл:B3inssp.png|550px|Разбиение корня с t = 4. Корневой узел r разделяется на два узла, и создаётся новый корень s. Новый корень содержит средний ключ r и две половины r в качестве детей. Разбиением узла высота дерева увеличивается на единицу]] Вставка ключа в B-дерево $<tex>T$ </tex> высоты $<tex>h$ </tex> за один нисходящий проход по дереву потребует $<tex>O(h)$ </tex> обращений к диску и $<tex>O(th)=O(t \log_t n)$ </tex> процессорного времени.  '''void''' B-Tree-Insert(T: '''BTree''', k: '''int'''):

'''if ''' r.n == 2t 2T.t - 1

s.leaf = FALSE''false''

B-Tree-Split-Child(s, T.t, 1) B-Tree-Insert-Nonfull(s, k, T.t) '''else''' B-Tree-Insert-Nonfull(r, k, T.t)

'''void''' B-Tree-Insert-Nonfull(x: '''Node''', k: '''int''', t: '''int'''):

'''if ''' x.leaf '''while (''' i >= 1) '''and (''' k < x.key[i]):

'''else ''' '''while (''' i >= 1) '''and (''' k < x.key[i]):

'''if ''' x.c[i].n == 2t - 1 B-Tree-Split-Child(x, t, i) '''if ''' k > x.key[i]

B-Tree-Insert-Nonfull(x.c[i], k, t)

Функция $<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> ключей[[Файл:B3insa.png|550px]]

Функция <wikitextex>Функция $\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-дерева можно только разбиением.

  '''void''' B-Tree-Split-Child(x: '''Node''', t: '''int''', i: '''int'''):

'''for ''' j = 1 '''to ''' t - 1:

'''if ''' not y.leaf '''for ''' j = 1 '''to ''' t:

'''for ''' j = x.n + 1 '''to ''' i + 1:

'''for ''' j = x.n '''to ''' i:

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

<wikitex>Если удаление происходит из листа, смотрим на количество ключей в нем. Если ключей больше $<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|переместим]] в новый узел.</wikitex>

<wikitex>Рассмотрим удаление из внутреннего узла. Имеется внутренний узел $<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|Удаление M и G из внутренних узлов]]</wikitex>

<wikitex>Если выбранное для нисходящего прохода поддерево содержит минимальное количе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>. Симметричная операция может производиться для перенесения ключа из предшествующего брата.</wikitex>

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

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

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

В B-дереве вместе с ключом может храниться только указатель на другую дисковую страницу, содержащую сопутствующую информацию для данного ключа. Существует распространённая модификация B-дерева, называемая [[B+-дерево|B+-деревом]], в которой, вся сопутствующая информация хранится в листьях, а во внутренних узлах хранятся только ключи и указатели на дочерние узлы. Таким образом удается получить максимально возможную степень ветвления во внутренних узлах.

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

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

== Ссылки См. также ==* [[2-3 дерево]]* [[B+-дерево]]* [[Splay-дерево]]* [[АВЛ-дерево]]* [[Красно-черное дерево]] == Источники информации ==

* [http://habrahabr.ru/post/114154/ Хабрахабрhabrahabr. ru {{---}} B-tree]* [http://de.wikipedia.org/wiki/B-Baum Wikipedia {{---}} B-Baum]