27
правок
Изменения
Нет описания правки
<wikitex>'''B-дерево''' — (англ. ''B-tree'') {{---}} сильноветвящееся сбалансированное дерево поиска, позволяющее проводить поиск, добавление и удаление элементов за $O(\log n)$. B-дерево с $n$ узлами имеет высоту $O(\log n)$. Количество детей узлов может быть от нескольких до тысяч (обычно степень ветвления B-дерева определяется характеристиками устройства (дисков), на котором производится работа с деревом). В-деревья также могут использоваться для реализации многих операций над динамическими множествами за время $O(\log n)$
B-дерево было впервые предложено Р. Бэйером и Е. МакКрейтом в 1970 году.</wikitex>
'''Node''' c[] <span style="color:#008000"> // указатели на детей узла</span>
=== Структура дерева ===
'''struct''' B-treeBTree
'''int''' t <span style="color:#008000"> // минимальная степень дерева</span>
'''Node''' root <span style="color:#008000"> // указатель на корень дерева</span>
Система в состоянии поддерживать в процессе работы в оперативной памяти только ограниченное количество страниц. Мы будем считать, что страницы, которые более не используются, удаляются из оперативной памяти системой; наши алгоритмы работы с В-деревьями не будут заниматься этим самостоятельно. Поскольку в большинстве систем время выполнения алгоритма, работающего с В-деревьями, зависит в первую очередь от количества выполняемых операций чтения/записи с диском, желательно минимизировать их количество и за один раз считывать и записывать как можно больше информации. Таким образом, размер узла В-дерева обычно соответствует дисковой странице. Количество потомков узла В-дерева, таким образом, ограничивается размером дисковой страницы.
Для больших В-деревьев, хранящихся на диске, степень ветвления обычно находится между <tex>50 </tex> и <tex>2000</tex>, в зависимости от размера ключа относительно размера страницы. Большая степень ветвления резко снижает как высоту дерева, так и количество обращений к диску для поиска ключа. Например, если есть миллиард ключей, и $t=1001$, то поиск ключа займёт две дисковые операции. </wikitex>
== Высота ==
Вставка ключа в B-дерево $T$ высоты $h$ за один нисходящий проход по дереву потребует $O(h)$ обращений к диску и $O(th)=O(t \log_t n)$ процессорного времени.
<code>
'''void''' B-Tree-Insert(T: '''BTree''', k: '''int'''):
r = T.root
'''if''' r.n == 2t 2T.t - 1
s = Allocate-Node()
T.root = s
s.leaf = ''false''
s.n = 0
s.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)
</code>
<code>
'''void''' B-Tree-Insert-Nonfull(x: '''Node''', k: '''int''', t: '''int'''):
i = x.n
'''if''' x.leaf
Disk-Read(x.c[i])
'''if''' x.c[i].n == 2t - 1
B-Tree-Split-Child(x, t, i)
'''if''' k > x.key[i]
i = i + 1
B-Tree-Insert-Nonfull(x.c[i], k, t)
</code>
Функция $\operatorname{B-Tree-Insert-Nonfull}$ вставляет ключ $k$ в узел $x$, который должен быть незаполненным при вызове.
[[Файл:B3splt.PNG|550px|Разбиение узла B-дерева с t=4]]
<code>
'''void''' B-Tree-Split-Child(x: '''Node''', t: '''int''', i: '''int'''):
z = Allocate-Node()
y = x.c[i]
[[Категория:Дискретная математика и алгоритмы]]
[[Категория: Структуры данных]]
[[Категория:Деревья поиска]]
