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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 13: Строка 13:
 
  '''struct''' Node
 
  '''struct''' Node
 
     '''bool''' leaf <span style="color:#008000">  // является ли узел листом</span>
 
     '''bool''' leaf <span style="color:#008000">  // является ли узел листом</span>
     '''int'''  n <span style="color:#008000">      // количество ключей узла</span>
+
     '''int'''  key_num <span style="color:#008000">      // количество ключей узла</span>
 
     '''int'''  key[] <span style="color:#008000">  // ключи узла</span>
 
     '''int'''  key[] <span style="color:#008000">  // ключи узла</span>
 +
    '''Node''' p <span style="color:#008000">      // указатель на отца</span>
 
     '''Node''' c[] <span style="color:#008000">    // указатели на детей узла</span>
 
     '''Node''' c[] <span style="color:#008000">    // указатели на детей узла</span>
 
     '''Node''' next <span style="color:#008000">  // указатели на следующий элемент (для внутренних вершин = null)</span>
 
     '''Node''' next <span style="color:#008000">  // указатели на следующий элемент (для внутренних вершин = null)</span>
Строка 36: Строка 37:
 
}}  
 
}}  
  
Как можно заметить, высота B<tex>^{+}</tex>-дерева не более чем на 1 отличается от [[B-дерево#Высота|высоты B-дерева]], то есть хранение значений только в листах почти не ухудшает эффективность дерева  
+
Как можно заметить, высота B<tex>^{+}</tex>-дерева не более чем на 1 отличается от [[B-дерево#Высота|высоты B-дерева]], то есть хранение информации только в листах почти не ухудшает эффективность дерева  
 +
 
 +
== Операции ==
 +
B<tex>^{+}</tex>-деревья являются сбалансированными, поэтому время выполнения стандартных операций в них пропорционально высоте.
 +
 
 +
=== Поиск ===
 +
Определяем интервал и переходим к соответствующему сыну. Повторяем пока не дошли до листа.
 +
 
 +
'''Node''' find(T: '''BPlusTree''', k: '''int'''):
 +
    Node now = T.root
 +
    '''while''' !now.leaf
 +
        '''for''' i = 0 '''to''' key.num
 +
            '''if''' i == now.key_num '''or''' key < now.key[i]
 +
                now = now.ch[i]
 +
                '''break'''
 +
    '''return''' now
  
 
== Примeчания ==
 
== Примeчания ==
 
<references/>
 
<references/>

Версия 04:32, 26 марта 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  key_num       // количество ключей узла
   int  key[]   // ключи узла
   Node p       // указатель на отца
   Node c[]     // указатели на детей узла
   Node next    // указатели на следующий элемент (для внутренних вершин = null)

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

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

Оценка высоты дерева

Теорема:
Если [math]n \geqslant 1[/math], то для B[math]^{+}[/math]-дерева c [math]n[/math] узлами и минимальной степенью [math]t \geqslant 2[/math]
[math]h \leqslant \log_t\dfrac{n}{2} + 1[/math]
Доказательство:
[math]\triangleright[/math]

Так как [math]n \geqslant 1[/math], то корень B[math]^{+}[/math]-дерева [math]T[/math] содержит хотя бы один ключ, а все остальные узлы — хотя бы [math]t - 1[/math] ключей. [math]T[/math] имеет хотя бы [math]2[/math] узла на высоте [math]1[/math], не менее [math]2t[/math] узлов на глубине [math]2[/math], и так далее. То есть на глубине [math]h[/math], оно имеет хотя бы [math]2t^{h-1}[/math] узлов. Так как сами ключи хранятся только в листах, а во внутренних вершинах лишь их копии, то для [math]n[/math] ключей [math]n \geqslant 2t^{h-1}[/math]

[math]t^{h-1} \leqslant \dfrac{n}{2}[/math]
[math]h-1 \leqslant \log_t\dfrac{n}{2}[/math]
[math]h \leqslant \log_t\dfrac{n}{2} + 1[/math]
[math]\triangleleft[/math]

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

Операции

B[math]^{+}[/math]-деревья являются сбалансированными, поэтому время выполнения стандартных операций в них пропорционально высоте.

Поиск

Определяем интервал и переходим к соответствующему сыну. Повторяем пока не дошли до листа.

Node find(T: BPlusTree, k: int):
    Node now = T.root
    while !now.leaf
        for i = 0 to key.num
            if i == now.key_num or key < now.key[i]
                now = now.ch[i]
                break
    return now

Примeчания