1632
правки
Изменения
B-дерево
,rollbackEdits.php mass rollback
B-дерево было впервые предложено Р. Бэйером и Е. МакКрейтом в <tex>1970 году.</wikitextex>году.
== Структура ==
B-дерево является идеально сбалансированным, то есть глубина всех его листьев одинакова.
B-дерево имеет следующие свойства (<tex>t<wikitex/tex>Каждый узел — параметр дерева, называемый ''минимальной степенью'' B-дерева, не меньший <tex>2</tex>.):* Каждый узел, кроме корня, содержит от $не менее <tex>t - 1$ до $2t - 1$ ключей. Корень содержит от $1$ до $2t - 1$ </tex> ключей. $t$ — параметр дерева, не меньший $2$. Каждый и каждый внутренний узел, не являющийся корневым, имеет, таким образом, как минимум по меньшей мере <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</wikitextex>-й сын содержит ключи из отрезка <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>50 </tex> и <tex>2000</tex>, в зависимости от размера ключа относительно размера страницы. Большая степень ветвления резко снижает как высоту дерева, так и количество обращений к диску для поиска ключа. Например, если есть миллиард ключей , и $<tex>t=1001$</tex>, то поиск ключа займёт две дисковые операции. </wikitex>
== Высота ==
|proof=
Корень 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 = 01}^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>
== Операции ==
B-деревья представляют собой сбалансированные деревья, поэтому время выполнения стандартных операций в них пропорционально высоте. Однако, как уже было упомянуто выше, алгоритмы B-дерева созданы специально для работы с дисками (или другими носителями информации) и базами данных (или иными видами представления большого количества информация), минимизируя количество операций ввода-вывода.
Если ключ содержится в текущем узле, возвращаем его. Иначе определяем интервал и переходим к соответствующему сыну. Повторяем пока ключ не найден или не дошли до листа.
=== Добавление ключа ===
Добавление ключа в B-дереве может быть осуществлена за один нисходящий проход от корня к листу. Для этого не нужно выяснять, требуется ли разбить узел, в который должен вставляться новый ключ. При проходе от корня к листьям в поисках места для нового ключа будут разбиваться все заполненные узлы, которые будут пройдены (включая и сам лист). Таким образом, если надо разбить какой-то полный узел, гарантируется, что его родительский узел не будет заполнен.
r = T.root
'''if (''' r.n == 2t 2T.t - 1) {
s = Allocate-Node()
T.root = s
s.leaf = FALSE''false''
s.n = 0
s.$C_1$ c[1] = r 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''') {:
i = x.n
'''if ''' x.leaf '''while (''' i $\geqslant$ >= 1) && ('''and''' k $<$ x.$key_i$) {key[i] x.$key_{key[i+1}$ ] = x.$key_i$key[i]
i = i - 1
x.n = x.n + 1
Disk-Write(x)
'''else { ''' '''while (''' i $\geqslant$ >= 1) && ('''and''' k < x.$key_i$)key[i]
i = i - 1
i = i + 1
Disk-Read(x.$c_i$c[i]) '''if ''' x.$c_i$c[i].n == 2t - 1 { B-Tree-Split-Child(x, t, i) '''if ''' k > x.$key_i$key[i]
i = i + 1
=== Разбиение узла ===
[[Файл:B3splt.PNG|550px|Разбиение узла B-дерева с t=4]]
'''void''' B-Tree-Split-Child(x: '''Node''', t: '''int''', i: '''int''') {:
z = Allocate-Node()
y = x.$C_i$c[i]
z.leaf = y.leaf
z.n = t - 1
'''for ''' j = 1 '''to ''' t - 1 z.$key_j$ key[j] = y.$key_{key[j+t}$] '''if ''' not y.leaf '''for ''' j = 1 '''to ''' t z.$c_j$ c[j] = y.$c_{c[j+t}$]
y.n = t - 1
'''for ''' j = x.n + 1 downto '''to''' i + 1 x.$C_{c[j+1}$ ] = x.$C_j$c[j] $x.c_{c[i+1}$ ] = z '''for ''' j = x.n downto '''to''' i x.$key_{key[j+1}$ ] = x.$key_j$key[j] x.$key_i$ key[i] = y.$key_t$key[t]
x.n = x.n + 1
Disk-Write(y)
Disk-Write(z)
Disk-Write(x)
=== Удаление ключа ===
Операция удаления ключа несколько сложнее, нежели добавление оного, так как необходимо убедиться, что удаляемый ключ находится во внутреннем узле. Процесс похож на поиск подходящего места для вставки ключа, с той разницей, что перед спуском в поддерево проверяется, достаточность количества ключей (т.е. <wikitextex>Находим ключ\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> последних потомка корня – то они становятся корнем, а предыдущий корень освобождается.Для удаления требуется время $O[[Файл:B3delin.png|550px|Удаление M и G из внутренних узлов]] ==== Перемещение ключа ====Если выбранное для нисходящего прохода поддерево содержит минимальное количе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 \log_t n-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>. [[Файл:BTMv.png|450px|Перемещение ключа в B-дереве]]Легко убедиться в том, что эти повороты поддерживают структуру B-дерева: для всех ключей <tex>k</tex> на отложенном поддереве до и $O(h)$ дисковых операцийпосле перенесения выполняется условие <tex>x.k_2 \leqslant k \leqslant x.c_3.k_1</wikitextex>. Симметричная операция может производиться для перенесения ключа из предшествующего брата. ==== Слияние ====Ниже будет рассмотрено слияние узлов при удалении ключей, то есть слияние узлов равной степени и высоты. Для произвольных же слияний потребуется приведение сливаемых деревьев к одной степени и высоте.
== Вариации B-дерева ==
=== B+-дерево ===
В B-дереве вместе с ключом может храниться только указатель на другую дисковую страницу, содержащую сопутствующую информацию для данного ключа. Существует распространённая модификация B-дерева, называемая [[B+-дерево|B+-деревом]], в которой, вся сопутствующая информация хранится в листьях, а во внутренних узлах хранятся только ключи и указатели на дочерние узлы. Таким образом удается получить максимально возможную степень ветвления во внутренних узлах.
=== B*-дерево ===
Распространённая модификация B-дерева, в которой каждый внутренний узел должен быть заполнен как минимум на две трети, а не наполовину, как в случае со стандартным B-деревом. Используется в файловых системах HFS и Reiser4. В отличие от B+-деревьев, узел не разбивается на <tex>2 </tex> узла, если полностью заполнен. Вместо этого ищется место в уже существующем соседнем узле, и только после того, как оба узла будут заполнены, они разделяются на три узла.
=== 2-3 дерево ===
Производное от B+-дерева. Каждый узел может иметь либо <tex>2</tex>, либо <tex>3 </tex> ребёнка.==== См.также ====:*[[2-3 дерево]]* [[B+-дерево]]* [[Splay-дерево]]* [[АВЛ-дерево]]* [[Красно-черное дерево]]
== Ссылки Источники информации ==
* T. H. Cormen «Introduction to Algorithms» third edition, Chapter 18
* Т. Кормен «Алгоритмы: построение и анализ» второе издание, глава 18
* Д. Кнут «Искусство программирования. Сортировка и поиск», часть 6.2.4
* [http://habrahabr.ru/post/114154/ Хабрахабрhabrahabr. ru {{---}} B-tree]* [http://de.wikipedia.org/wiki/B-Baum Wikipedia {{---}} B-Baum]
* [http://citforum.ru/programming/theory/sorting/sorting2.shtml#5 Методы сортировки и поиска. Методы поиска во внешней памяти]
* [http://www.ibm.com/developerworks/ru/library/l-data_structures_10/ IBM. developerWorks. «Работа со структурами данных в языках Си и Python: Часть 10. B-деревья и TRIE-деревья»]
* [http://www.minet.uni-jena.de/dbis/lehre/ws2005/dbs1/Bayer_hist.pdf R. Bayer, E. McCreight «Organization and Maintenance of Large Ordered Indexes», Acta Informatica, 1972]
[[Категория:Дискретная математика и алгоритмы]]
[[Категория: Структуры данных]]
[[Категория:Деревья поиска]]