Изменения
Отмена правки 84045, сделанной 185.220.100.252 (обсуждение)
'''B<tex>B^{+}</tex>-дерево''' (англ. ''B<tex>B^{+}</tex>-tree'') {{---}} структура данных на основе [[B-дерево|B-дерева]], сбалансированное <tex>n</tex>-арное дерево поиска с переменным, но зачастую большим количеством потомков в узле. B<tex>B^{+}</tex>-деревья имеют очень высокий коэффициент ветвления (число указателей из родительского узла на дочерние, обычно порядка <tex>100 </tex> или более), что снижает количество операций ввода-вывода, требующих поиска элемента в дереве. == Где используется ==Изначально структура предназначалась для эффективного поиска в блочно-ориентированной среде хранения {{---}} в частности, для файловых систем. Структура широко применяется в таких файловых системах, как NTFS<ref>[[wikipedia:NTFS |Wikipedia {{---}} NTFS]]</ref>, ReiserFS<ref>[[wikipedia:ReiserFS |Wikipedia {{---}} ReiserFS]]</ref>, NSS<ref>[[wikipedia:Novell Storage Services |Wikipedia {{---}} NSS]]</ref>, JFS<ref>[[wikipedia:JFS (file system) |Wikipedia {{---}} JFS]]</ref>, ReFS<ref>[[wikipedia:ReFS |Wikipedia {{---}} ReFS]]</ref>. Различные реляционные системы управления базами данных, такие как Microsoft SQL Server<ref>[[wikipedia:Microsoft SQL Server|Wikipedia {{---}} Microsoft SQL Server]]</ref>, Oracle Database<ref>[[wikipedia:Oracle Database|Wikipedia {{---}} Oracle Database]]</ref>, SQLite<ref>[[wikipedia:SQLite|Wikipedia {{---}} SQLite]]</ref> используют B<tex>^{+}</tex>-деревья для табличных индексов.
== Отличия от B-дерева ==
В <tex>B</tex>-дереве во всех вершинах хранятся ключи вместе с сопутствующей информацией. В B<tex>B^{+}</tex>-деревьях вся информация хранится в листьях, а во внутренних узлах хранятся только копии ключей. Таким образом удается получить максимально возможную степень ветвления во внутренних узлах. Кроме того, листовой узел может включать в себя указатель на следующий листовой узел для ускорения последовательного доступа, что решает одну из главных проблем <tex>B</tex>-деревьев.
== Структура ==
Свойства B<tex>B^{+}</tex> дерева аналогичны [[B-дерево#Структура| свойствам <tex>B</tex>-дерева]] (с учетом отличий описанных выше).
=== Структура узла ===
'''struct''' Node
'''bool''' leaf <span style="color:#008000"> // является ли узел листом</span> '''int''' key_num <span style="color:#008000"> // количество ключей узла</span> '''int''' key[] <span style="color:#008000"> // ключи узла</span> '''Node''' p parent <span style="color:#008000"> // указатель на отца</span> '''Node''' cchild[] <span style="color:#008000"> // указатели на детей узла</span> '''Info''' pointers[] <span style="color:#008000">// если лист {{---}} указатели на данные</span> '''Node''' next left<span style="color:#008000"> // указатели указатель на следующий элемент (для внутренних вершин левого брата</span> '''Node''' right <span style= null)"color:#008000"> // указатель на правого брата</span>
=== Структура дерева ===
'''struct''' BPlusTree
'''int''' t <span style="color:#008000"> // минимальная степень дерева</span> '''Node''' root <span style="color:#008000"> // указатель на корень дерева</span>
== Оценка высоты дерева ==
{{Теорема|statement=Если <tex>n \geqslant 1</tex>, то для B<tex>B^{+}</tex>-дерева c <tex>n</tex> узлами и минимальной степенью <tex>t \geqslant 2</tex>высота
:<tex>h \leqslant \log_t\dfrac{n}{2} + 1</tex>
|proof=
Так как <tex>n \geqslant 1</tex>, то корень B<tex>B^{+}</tex>-дерева <tex>T</tex> содержит хотя бы один ключ, а все остальные узлы — хотя бы <tex>t - 1</tex> ключей. <tex>T</tex> имеет хотя бы <tex>2</tex> узла на высоте <tex>1</tex>, не менее <tex>2t</tex> узлов на глубине <tex>2</tex>, и так далее. То есть на глубине <tex>h</tex>, оно имеет хотя бы <tex>2t^{h-1}</tex> узлов. Так как сами ключи хранятся только в листах, а во внутренних вершинах лишь их копии, то для <tex>n</tex> ключей
<tex>n \geqslant 2t^{h-1}</tex>
}}
Как можно заметить, высота B<tex>B^{+}</tex>-дерева не более чем на <tex>1 </tex> отличается от [[B-дерево#Высота|высоты <tex>B</tex>-дерева]], то есть хранение информации только в листах почти не ухудшает эффективность дерева
== Операции ==
=== Поиск ===
'''Nodebool''' finddelete(T: '''BPlusTree''', kkey: '''int'''): leaf = find_key(T, key) pos = 0 '''if''' key <tex>\notin</tex> leaf '''return false''' '''else''' delete_in_node(leaf, key) <span style="color:#008000"> // Удалить ключ из вершины</span> '''return true''' '''void''' delete_in_node(tec: '''Node now ''', key: '''int'''): '''if''' key <tex>\notin</tex> tec '''return''' <span style="color:#008000">// Ищем позицию удаляемого ключа </span> pos = 0 '''while''' pos < tec.key_num '''and''' tec.key[pos] < key ++pos <span style="color:#008000">// Удаляем ключ</span> '''for''' i = pos '''to''' tec.key_num - 1 tec.key[i] = Ttec.key[i + 1] tec.pointers[i] = tec.rootpointer[i + 1] '''whilefor''' i = pos + 1 '''to''' !nowtec.key_num tec.child[i] = tec.child[i + 1] --tec.key_num '''if''' leaf.key_num < t - 1 right_sibling = tec.right left_sibling = tec.left '''if''' left_sibling <tex>\neq</tex> null '''and''' left_sibling.key_num > t - 1 --left_sibling.key_num ++tec.key_num <span style="color:#008000">// Перемещаем максимальный из left_sibling ключ на первую позицию в tec </span> '''for''' i = 0 1 '''to''' tec.key_num - 1 tec.key[i] = tec.key[i - 1] tec.pointers[i] = tec.pointer[i - 1] tec.child[i] = tec.child[i - 1] tec.child[tec.key_num] = tec.child[tec.key_num - 1] tec.key[0] = left_sibling.key[left_sibling.key_num] tec.pointers[0] = left_sibling.numpointers[left_sibling.key_num] tec.child[0] = left_sibling.child [left_sibling.key_num + 1] update(tec) <span style="color:#008000"> // Обновить ключи на пути к корню</span> '''else if''' i right_sibling <tex>\neq</tex> null '''and''' right_sibling.key_num > t - 1 --right_sibling.key_num ++tec.key_num <span style="color:#008000">// Перемещаем минимальный из right_sibling ключ на последнюю позицию в tec </span> tec.key[tec.key_num - 1] =right_sibling.key[0] tec.pointers[tec.key_num - 1] = nowright_sibling.child[0] tec.child[tec.key_num - 1] = right_sibling.pointers[0] update(tec) <span style="color:#008000"> // Обновить ключи на пути к корню</span> '''else''' '''if''' left_sibling <tex>\neq</tex> null <span style="color:#008000">// Сливаем tec и left_sibling</span> '''orfor''' i = 0 to tec.key_num - 1 left_sibling.key < now[left_sibling.key_num] = tec.key[i] left_sibling.pointers[left_sibling.key_num] = tec.pointers[i] left_sibling.child[left_sibling.key_num + 1] = tec.child[i] ++left_sibling.key_num now left_sibling.child[left_sibling.key_num + 1] = nowtec.chchild[itec.key_num] <span style="color:#008000">// Перенаправляем right и left указатели</span> left_sibling.right = tec.right tec.right.left = left_sibling update(left_sibling) <span style="color:#008000"> // Обновить ключи на пути к корню</span> delete_in_node(left_sibling.parent, min_key(tec)) <span style="color:#008000"> // Удаляем разделительный ключ в отце</span> '''else''' <span style="color:#008000">// Сливаем tec и right_sibling</span> '''breakfor'''i = 0 to tec.key_num - 1 tec.key[tec.key_num] = right_sibling.key[i] tec.pointers[tec.key_num] = right_sibling.pointers[i] tec.child[tec.key_num + 1] = right_sibling.child[i] ++tec.key_num tec.child[tec.key_num + 1] = right_sibling.child[right_sibling.key_num] <span style="color:#008000">// Перенаправляем right и left указатели</span> right_sibling.right.left = tec tec.right = right_sibling.right update(tec) <span style="color:#008000"> // Обновить ключи на пути к корню</span> delete_in_node(tec.parent, min_key(right_sibling)) <span style="color:#008000"> // Удаляем разделительный ключ в отце</span> '''returnif''' nowT.root.key_num == 1 T.root = T.root.child[0] == Где используется ==Изначально структура предназначалась для эффективного поиска в блочно-ориентированной среде хранения {{---}} в частности, для файловых систем. Структура широко применяется в таких файловых системах, как NTFS<ref>[[wikipedia:NTFS |Wikipedia {{---}} NTFS]]</ref>, ReiserFS<ref>[[wikipedia:ReiserFS |Wikipedia {{---}} ReiserFS]]</ref>, NSS<ref>[[wikipedia:Novell Storage Services |Wikipedia {{---}} NSS]]</ref>, JFS<ref>[[wikipedia:JFS (file system) |Wikipedia {{---}} JFS]]</ref>, ReFS<ref>[[wikipedia:ReFS |Wikipedia {{---}} ReFS]]</ref>. Различные реляционные системы управления базами данных, такие как Microsoft SQL Server<ref>[[wikipedia:Microsoft SQL Server|Wikipedia {{---}} Microsoft SQL Server]]</ref>, Oracle Database<ref>[[wikipedia:Oracle Database|Wikipedia {{---}} Oracle Database]]</ref>, SQLite<ref>[[wikipedia:SQLite|Wikipedia {{---}} SQLite]]</ref> используют <tex>B^{+}</tex>-деревья для табличных индексов. == См. также ==* [[B-дерево]]* [[2-3 дерево]]
== Примeчания ==
<references/>
== Источники информации ==
* Д. Кнут «Искусство программирования. Сортировка и поиск», часть 6.2.4
* [https://en.wikipedia.org/wiki/B%2B_tree Wikipedia {{---}} B Plus tree]
* [https://en.wikipedia.org/wiki/B-tree Wikipedia {{---}} B tree]
* [https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html B plus tree visualization]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Структуры данных]]
[[Категория: Деревья поиска]]