27
правок
Изменения
Нет описания правки
* Ключи в каждом узле упорядочены по неубыванию.
* Все листья находятся на одном уровне.
=== Структура узла ===
'''struct''' Node
'''bool''' leaf <span style="color:#008000"> // является ли узел листом</span>
'''int''' n <span style="color:#008000"> // количество ключей узла</span>
'''int''' key[] <span style="color:#008000"> // ключи узла</span>
'''Node''' c[] <span style="color:#008000"> // указатели на детей узла</span>
=== Структура дерева ===
'''struct''' B-tree
'''int''' t <span style="color:#008000"> // минимальная степень дерева</span>
'''Node''' root <span style="color:#008000"> // указатель на корень дерева</span>
== Назначение ==
<wikitex>B-деревья разработаны для использования на дисках (в файловых системах) или иных энергонезависимых носителях информации с прямым доступом, а также в базах данных. B-деревья похожи на красно-чёрные деревья (например, в том, что все В-деревья с $n$ узлами имеют высоту $O(\log n)$), но они лучше минимизируют количество операций чтения-записи с диском.</wikitex>
<wikitex>Количество обращений к диску, необходимое для выполнения большинства операций с В-деревом, пропорционально его высоте. Проанализируем высоту В-дерева в наихудшем случае.
{{Теорема|statement=Если $n \geqslant 1$, то для B-дерева $T$ c $n$ узлами и минимальной степенью $t \geqslant 2$ имеется следующее неравенство:
:$h \leqslant$ $\log_t\fracdfrac{n+1}{2}$
|proof=
Корень B-дерева $T$ содержит по меньшей мере один ключ, а все остальные узлы — хотя бы $t - 1$ ключей. Так, T, высота которого $h$, имеет хотя бы $2$ узла на глубине $1$, хотя бы $2t$ узла на глубине $2$, хотя бы $2t^2$ узла на глубине $3$, и так далее, до глубины $h$, оно имеет по меньшей мере $2t^{h-1}$ узлов. Так, число ключей $n$ удовлетворяет неравенству:
::$n \geqslant 1+(t-1)\sum\limits_{i = 1}^h 2t^{i-1} $
:::$=1+2(t-1)(\fracdfrac{t^h-1}{t-1})$
:::$=2t^h-1$.
Вставка ключа в B-дерево $T$ высоты $h$ за один нисходящий проход по дереву потребует $O(h)$ обращений к диску и $O(th)=O(t \log_t n)$ процессорного времени.
<code> '''void''' B-Tree-Insert(T, k)
r = T.root
'''if ''' r.n == 2t - 1
s = Allocate-Node()
T.root = s
s.leaf = FALSEfalse
s.n = 0
s.c[1] = r
B-Tree-Split-Child(s, 1)
B-Tree-Insert-Nonfull(s, k)
'''else'''
B-Tree-Insert-Nonfull(r, k)
</code><code> '''void''' B-Tree-Insert-Nonfull(x, k)
i = x.n
'''if ''' x.leaf '''while (''' i >= 1) '''and (''' k < x.key[i]):
x.key[i+1] = x.key[i]
i = i - 1
x.n = x.n + 1
Disk-Write(x)
'''else ''' '''while (''' i >= 1) '''and (''' k < x.key[i]):
i = i - 1
i = i + 1
Disk-Read(x.c[i])
'''if ''' x.c[i].n == 2t - 1
B-Tree-Split-Child(x, i)
'''if ''' k > x.key[i]
i = i + 1
B-Tree-Insert-Nonfull(x.c[i], k)
</code>
Функция $\operatorname{B-Tree-Insert-Nonfull}$ вставляет ключ $k$ в узел $x$, который должен быть незаполненным при вызове.
Использование функции $\operatorname{B-Tree-Split-Child}$ гарантирует, что рекурсия не встретится с заполненным узлом.
[[Файл:B3splt.PNG|550px|Разбиение узла B-дерева с t=4]]
<code> '''void''' B-Tree-Split-Child(x, i)
z = Allocate-Node()
y = x.c[i]
z.leaf = y.leaf
z.n = t - 1
'''for ''' j = 1 '''to ''' t - 1:
z.key[j] = y.key[j+t]
'''if ''' not y.leaf '''for ''' j = 1 '''to ''' t:
z.c[j] = y.c[j+t]
y.n = t - 1
'''for ''' j = x.n + 1 '''to ''' i + 1:
x.c[j+1] = x.c[j]
x.c[i+1] = z
'''for ''' j = x.n '''to ''' i:
x.key[j+1] = x.key[j]
x.key[i] = y.key[t]
Disk-Write(z)
Disk-Write(x)
</code>
</wikitex>
=== 2-3 дерево ===
Производное от B+-дерева. Каждый узел может иметь либо 2, либо 3 ребёнка.
== Ссылки См. также ==* [[2-3 дерево]]* [[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]
[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Деревья поиска]]
