B+-дерево — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Структура дерева)
(Структура дерева)
Строка 18: Строка 18:
 
     '''Node''' next <span style="color:#008000">  // указатели на следующий элемент (для внутренних вершин = null)</span>
 
     '''Node''' next <span style="color:#008000">  // указатели на следующий элемент (для внутренних вершин = null)</span>
 
=== Структура дерева ===
 
=== Структура дерева ===
  '''struct''' BTree
+
  '''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

B[math]^{+}[/math]-дерево (англ. B[math]^{+}[/math]-tree) — структура данных на основе B-дерева, сбалансированное [math]n[/math]-арное дерево поиска с переменным, но зачастую большим количеством потомков в узле. B[math]^{+}[/math]-деревья имеют очень высокий коэффициент ветвления (число указателей из родительского узла на дочерние, обычно порядка 100 или более), что снижает количество операций ввода-вывода, требующих поиска элемента в дереве.

Где используется

Изначально структура предназначалась для эффективного поиска в блочно-ориентированной среде хранения — в частности, для файловых систем. Структура широко применяется в таких файловых системах, как NTFS[1], ReiserFS[2], NSS[3], JFS[4], ReFS[5]. Различные реляционные системы управления базами данных, такие как Microsoft SQL Server[6], Oracle Database[7], SQLite[8] используют B[math]^{+}[/math]-деревья для табличных индексов.

Отличия от B-дерева

В B-дереве во всех вершинах хранятся ключи вместе с сопутствующей информацией. В B[math]^{+}[/math]-деревьях вся информация хранится в листьях, а во внутренних узлах хранятся только копии ключей. Таким образом удается получить максимально возможную степень ветвления во внутренних узлах. Кроме того, листовой узел может включать в себя указатель на следующий листовой узел для ускорения последовательного доступа, что решает одну из главных проблем B-деревьев.

Структура

Свойства B[math]^{+}[/math] дерева аналогичны свойствам B-дерева

Структура узла

struct Node
   bool leaf    // является ли узел листом
   int  n       // количество ключей узла
   int  key[]   // ключи узла
   Node c[]     // указатели на детей узла
   Node next    // указатели на следующий элемент (для внутренних вершин = null)

Структура дерева

struct BPlusTree
   int  t       // минимальная степень дерева
   Node root    // указатель на корень дерева

Примeчания