B+-дерево — различия между версиями
Mervap (обсуждение | вклад) |
Mervap (обсуждение | вклад) (→Структура дерева) |
||
| Строка 7: | Строка 7: | ||
В B-дереве во всех вершинах хранятся ключи вместе с сопутствующей информацией. В B<tex>^{+}</tex>-деревьях вся информация хранится в листьях, а во внутренних узлах хранятся только копии ключей. Таким образом удается получить максимально возможную степень ветвления во внутренних узлах. Кроме того, листовой узел может включать в себя указатель на следующий листовой узел для ускорения последовательного доступа, что решает одну из главных проблем B-деревьев. | В B-дереве во всех вершинах хранятся ключи вместе с сопутствующей информацией. В B<tex>^{+}</tex>-деревьях вся информация хранится в листьях, а во внутренних узлах хранятся только копии ключей. Таким образом удается получить максимально возможную степень ветвления во внутренних узлах. Кроме того, листовой узел может включать в себя указатель на следующий листовой узел для ускорения последовательного доступа, что решает одну из главных проблем B-деревьев. | ||
| − | == Структура | + | == Структура == |
Свойства B<tex>^{+}</tex> дерева аналогичны [[B-дерево#Структура| свойствам B-дерева]] | Свойства B<tex>^{+}</tex> дерева аналогичны [[B-дерево#Структура| свойствам B-дерева]] | ||
| Строка 21: | Строка 21: | ||
'''int''' t <span style="color:#008000"> // минимальная степень дерева</span> | '''int''' t <span style="color:#008000"> // минимальная степень дерева</span> | ||
'''Node''' root <span style="color:#008000"> // указатель на корень дерева</span> | '''Node''' root <span style="color:#008000"> // указатель на корень дерева</span> | ||
| − | |||
== Примeчания == | == Примeчания == | ||
<references/> | <references/> | ||
Версия 13:39, 20 марта 2018
B-дерево (англ. B-tree) — структура данных на основе B-дерева, сбалансированное -арное дерево поиска с переменным, но зачастую большим количеством потомков в узле. B-деревья имеют очень высокий коэффициент ветвления (число указателей из родительского узла на дочерние, обычно порядка 100 или более), что снижает количество операций ввода-вывода, требующих поиска элемента в дереве.
Содержание
Где используется
Изначально структура предназначалась для эффективного поиска в блочно-ориентированной среде хранения — в частности, для файловых систем. Структура широко применяется в таких файловых системах, как NTFS[1], ReiserFS[2], NSS[3], JFS[4], ReFS[5]. Различные реляционные системы управления базами данных, такие как Microsoft SQL Server[6], Oracle Database[7], SQLite[8] используют B-деревья для табличных индексов.
Отличия от B-дерева
В B-дереве во всех вершинах хранятся ключи вместе с сопутствующей информацией. В B-деревьях вся информация хранится в листьях, а во внутренних узлах хранятся только копии ключей. Таким образом удается получить максимально возможную степень ветвления во внутренних узлах. Кроме того, листовой узел может включать в себя указатель на следующий листовой узел для ускорения последовательного доступа, что решает одну из главных проблем B-деревьев.
Структура
Свойства B дерева аналогичны свойствам B-дерева
Структура узла
struct Node bool leaf // является ли узел листом int n // количество ключей узла int key[] // ключи узла Node c[] // указатели на детей узла Node next // указатели на следующий элемент (для внутренних вершин = null)
Структура дерева
struct BTree int t // минимальная степень дерева Node root // указатель на корень дерева
