B+-дерево — различия между версиями
Mervap (обсуждение | вклад) (→Структура дерева) |
Mervap (обсуждение | вклад) (→Структура дерева) |
||
Строка 18: | Строка 18: | ||
'''Node''' next <span style="color:#008000"> // указатели на следующий элемент (для внутренних вершин = null)</span> | '''Node''' next <span style="color:#008000"> // указатели на следующий элемент (для внутренних вершин = null)</span> | ||
=== Структура дерева === | === Структура дерева === | ||
− | '''struct''' | + | '''struct''' BPlusTree |
'''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> |
Версия 13:39, 20 марта 2018
BB-дерева, сбалансированное -арное дерево поиска с переменным, но зачастую большим количеством потомков в узле. B -деревья имеют очень высокий коэффициент ветвления (число указателей из родительского узла на дочерние, обычно порядка 100 или более), что снижает количество операций ввода-вывода, требующих поиска элемента в дереве.
-дерево (англ. B -tree) — структура данных на основеСодержание
Где используется
Изначально структура предназначалась для эффективного поиска в блочно-ориентированной среде хранения — в частности, для файловых систем. Структура широко применяется в таких файловых системах, как 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 BPlusTree int t // минимальная степень дерева Node root // указатель на корень дерева