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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 61: Строка 61:
 
  '''bool''' insert(T: '''BPlusTree''', key: '''int''', value: '''Info'''):
 
  '''bool''' insert(T: '''BPlusTree''', key: '''int''', value: '''Info'''):
 
     leaf = find_key(T, key)
 
     leaf = find_key(T, key)
     '''if''' key <tex>\in</tex> leaf
+
     '''for''' i = 0 '''to''' leaf.key_num
        '''return false'''  
+
        '''if''' key == leaf.key[i]
      
+
            '''return false'''  
 +
     pos = 0
 
     '''while''' pos < leaf.key_num '''and''' leaf.key[pos] < key
 
     '''while''' pos < leaf.key_num '''and''' leaf.key[pos] < key
 
         ++pos
 
         ++pos
     Вставляем key и value на позицию pos в листе
+
     '''for''' i = leaf.key_num '''downto''' pos + 1
 +
        leaf.key[i] = leaf.key[i - 1]
 +
        leaf.pointers[i] = leaf.pointer[i - 1]
 +
    leaf.key[pos] = key
 +
    leaf.pointers[pos] = value
 
     ++leaf.key_num
 
     ++leaf.key_num
   
 
 
     '''if''' leaf.key_num == 2 * t <span style="color:#008000">            // t {{---}} степень дерева</span>
 
     '''if''' leaf.key_num == 2 * t <span style="color:#008000">            // t {{---}} степень дерева</span>
 
         split(T, leaf)            <span style="color:#008000">      // Разбиваем узел</span>
 
         split(T, leaf)            <span style="color:#008000">      // Разбиваем узел</span>
Строка 84: Строка 88:
  
 
  '''void''' split(T: '''BPlusTree''', node: '''Node'''):
 
  '''void''' split(T: '''BPlusTree''', node: '''Node'''):
     Создаем новый узел new_node
+
     new_node = new_Node() <span style="color:#008000">                //Создаем новый узел</span>
     Перенаправляем right и left указатели, вставляя его между node и node.right
+
    new_node.right = node.right
 +
     node.right.left = new_node
 +
    node.right = new_node
 +
    new_node.left = node
 
     mid_key = node.key[t]
 
     mid_key = node.key[t]
 +
    new_node.key_num = t - 1
 
      
 
      
     new_node.key_num = t - 1    
+
     '''for''' i = 0 '''to''' new_node.key_num - 1
 +
        new_node.key[i] = node.key[i + t + 1]
 +
        new_node.pointers[i] = node.pointers[i + t + 1] 
 +
        new_node.child[i] = node.child[i + t + 1]   
 +
    new_node.child[new_node.key_num] = node.child[2 * t] 
 
     node.key_num = t
 
     node.key_num = t
     Перемещаем new_node.key_num значений и соответствующих им указателей в new_node
+
      
     
 
 
     '''if''' node.leaf
 
     '''if''' node.leaf
 +
        ++new_node.key_num
 
         new_node.leaf = '''true'''
 
         new_node.leaf = '''true'''
         Перемещаем в new_node оставшийся при разбиении элемент mid_key
+
         '''for''' i = new_node.key_num - 1 '''downto''' 1
 +
            new_node.key[i] = node.key[i - 1]
 +
            new_node.pointers[i] = node.pointers[i - 1]
 +
        new_node.key[0] = node.key[t]
 +
        new_node.pointers[0] = node.pointers[0]
 
      
 
      
 
     '''if''' node == T.root
 
     '''if''' node == T.root
         Создаем новый корень T.root
+
         T.root = new_Node()
 
         T.root.key[0] = mid_key
 
         T.root.key[0] = mid_key
 
         T.root.child[0] = node
 
         T.root.child[0] = node
Строка 107: Строка 123:
 
         new_node.parent = node.parent
 
         new_node.parent = node.parent
 
         parent = node.parent
 
         parent = node.parent
       
 
 
         pos = 0
 
         pos = 0
 
         '''while''' pos < parent.key_num '''and''' parent.key[pos] < mid_key
 
         '''while''' pos < parent.key_num '''and''' parent.key[pos] < mid_key
 
             ++pos
 
             ++pos
         Вставляем в parent на позицию pos ключ mid_key и направляем ссылку из него на new_node
+
         '''for''' i = parent.key_num '''downto''' pos + 1
 +
            parent.key[i] = parent.key[i - 1]
 +
        '''for''' i = parent.key_num + 1 '''downto''' pos + 2
 +
            parent.child[i] = parent.child[i - 1]
 +
        parent.key[pos] = mid_key
 +
        parent.child[pos + 1] = new_node
 
         ++parent.key_num
 
         ++parent.key_num
 
          
 
          
         '''if''' parent.key_num == 2 * t <span style="color:#008000">      // Если требуется, продолжаем разбиение узла</span>
+
         '''if''' parent.key_num == 2 * t  
 
             split(T, parent)
 
             split(T, parent)
  
Строка 125: Строка 145:
 
     leaf = find_key(T, key)
 
     leaf = find_key(T, key)
 
     pos = 0
 
     pos = 0
     '''if''' key <tex>\notin</tex> leaf
+
    '''while''' pos < leaf.key_num '''and''' leaf.key[pos] < key
         '''return false'''  
+
        ++pos
 +
     '''if''' pos == leaf.key_num '''or''' leaf.key[pos] <tex>\neq</tex> key
 +
         '''return false'''
 
     '''else'''  
 
     '''else'''  
         delete_in_node(leaf, key)                  <span style="color:#008000">               // Удалить ключ из вершины</span>
+
         delete_in_node(leaf, key)                  <span style="color:#008000"> // Удалить ключ из вершины</span>
 
         '''return true'''
 
         '''return true'''
  
Строка 135: Строка 157:
 
     '''while''' pos < tec.key_num '''and''' tec.key[pos] < key
 
     '''while''' pos < tec.key_num '''and''' tec.key[pos] < key
 
         ++pos
 
         ++pos
     '''if''' key <tex>\notin</tex> tec
+
     '''if''' pos == tec.key_num '''or''' tec.key[pos] <tex>\neq</tex> key
         '''return'''  
+
         '''return'''
     Удаляем key из tec
+
     '''for''' i = pos '''to''' tec.key_num - 1
 +
        tec.key[i] = tec.key[i + 1]
 +
        tec.pointers[i] = tec.pointer[i + 1]
 +
    '''for''' i = pos + 1 '''to''' tec.key_num
 +
        tec.child[i] = tec.child[i + 1]
 
     --tec.key_num
 
     --tec.key_num
 
      
 
      
Строка 146: Строка 172:
 
             --left_sibling.key_num
 
             --left_sibling.key_num
 
             ++tec.key_num
 
             ++tec.key_num
             Перемещаем максимальный из left_sibling ключ на первую позицию в tec
+
             '''for''' i = 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.pointers[left_sibling.key_num]
 +
            tec.child[0] = left_sibling.child [left_sibling.key_num + 1]
 +
             update(tec)                    <span style="color:#008000">                                  // Обновить ключи на пути к корню</span>
 
          
 
          
 
         '''else if''' right_sibling <tex>\neq</tex> null '''and''' right_sibling.key_num > t - 1
 
         '''else if''' right_sibling <tex>\neq</tex> null '''and''' right_sibling.key_num > t - 1
 
             --right_sibling.key_num
 
             --right_sibling.key_num
 
             ++tec.key_num
 
             ++tec.key_num
             Перемещаем минимальный из right_sibling ключ на последнюю позицию в tec
+
             tec.key[tec.key_num - 1] = right_sibling.key[0]
             Обновляем ключи на пути к корню
+
            tec.pointers[tec.key_num - 1] = right_sibling.child[0]
 +
            tec.child[tec.key_num - 1] = right_sibling.pointers[0]
 +
             update(tec) 
 
            
 
            
 
         '''else'''
 
         '''else'''
 
             '''if''' left_sibling <tex>\neq</tex> null  
 
             '''if''' left_sibling <tex>\neq</tex> null  
                 Сливаем tec и left_sibling
+
                 left_sibling.right = tec.right
                 Перенаправляем right и left указатели
+
                 tec.right.left = left_sibling
                 Обновляем ключи на пути к корню
+
                 '''for''' i = 0 to tec.key_num - 1
                 delete_in_node(left_sibling.parent, min_key(tec))  <span style="color:#008000"> // Удаляем разделительный ключ в отце</span>
+
                    left_sibling.key[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
 +
                left_sibling.child[left_sibling.key_num + 1] = tec.child[tec.key_num]
 +
                update(left_sibling)
 +
                 delete_in_node(left_sibling.parent, min_key(tec))  <span style="color:#008000">   // Удаляем разделительный ключ в отце</span>
 
                
 
                
 
             '''else'''
 
             '''else'''
                 Сливаем tec и right_sibling  
+
                 right_sibling.right.left = tec
                 Перенаправляем right и left указатели
+
                tec.right = right_sibling.right
                 Обновляем ключи на пути к корню
+
                '''for''' 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]
 +
                 update(tec)
 
                 delete_in_node(tec.parent, min_key(right_sibling))  
 
                 delete_in_node(tec.parent, min_key(right_sibling))  
           
+
         '''if''' T.root.key_num == 1
         '''if''' T.root.key_num == 1 <span style="color:#008000">                                      // Если у корня 1 ребенок понижаем высоту дерева</span>
 
 
             T.root = T.root.child[0]
 
             T.root = T.root.child[0]
  

Версия 21:39, 17 апреля 2018

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

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

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

Структура

Свойства [math]B^{+}[/math] дерева аналогичны свойствам [math]B[/math]-дерева (с учетом отличий описанных выше).

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

struct Node
   bool leaf       // является ли узел листом
   int  key_num    // количество ключей узла
   int  key[]      // ключи узла
   Node parent     // указатель на отца
   Node child[]    // указатели на детей узла
   Info pointers[] // если лист — указатели на данные
   Node left       // указатель на левого брата
   Node right      // указатель на правого брата

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

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

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

Теорема:
Если [math]n \geqslant 1[/math], то для [math]B^{+}[/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], то корень [math]B^{+}[/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]

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

Операции

[math]B^{+}[/math]-деревья являются сбалансированными, поэтому время выполнения стандартных операций в них пропорционально высоте, то есть [math]O(\log n)[/math]. Однако стоит заметить, что так как степень дерева зачастую выбирается большой, константа при выполнении операций тоже большая. Это связано с большим количеством ключей в узлах, которые необходимо сравнить. Но из-за небольшой высоты дерева это не сильно сказывается на скорости работы.

Поиск листа

Напишем вспомогательную функцию, которая будет возвращать лист, в котором должен находится переданный ей ключ. Определяем интервал и переходим к соответствующему сыну. Повторяем пока не дошли до листа.

Node find_leaf(T: BPlusTree, key: int):
    cur = T.root
    while cur.leaf [math]\neq[/math] true
        for i = 0 to cur.key_num
            if i == cur.key_num or key < cur.key[i]
                cur = cur.child[i]
                break
    return cur

Поиск

Находим нужный лист через [math]find[/math]_[math]leaf[/math] и ищем нужный ключ в нем

Добавление ключа

Ищем лист, в который можно добавить ключ и добавляем его в список ключей. Если узел не заполнен, то добавление завершено. Иначе разбиваем узел на два узла. Будем считать, что в дереве не может находиться [math]2[/math] одинаковых ключа, поэтому [math]insert[/math] будет возвращать был ли добавлен ключ.

bool insert(T: BPlusTree, key: int, value: Info):
    leaf = find_key(T, key)
    for i = 0 to leaf.key_num
        if key == leaf.key[i]
            return false 
    pos = 0
    while pos < leaf.key_num and leaf.key[pos] < key
        ++pos
    for i = leaf.key_num downto pos + 1 
        leaf.key[i] = leaf.key[i - 1]
        leaf.pointers[i] = leaf.pointer[i - 1]
    leaf.key[pos] = key
    leaf.pointers[pos] = value
    ++leaf.key_num
    if leaf.key_num == 2 * t              // t — степень дерева
        split(T, leaf)                   // Разбиваем узел
    return true

Разбиение узла

Разбиение на два узла происходит следующим образом: в первый добавляем первые [math]t[/math] ключей, во второй последние [math]t - 1[/math]. Если узел — лист, то оставшийся ключ также добавляется в правое поддерево, а его копия отправляется в родительский узел, где становится разделительной точкой для двух новых поддеревьев.

Если и родительский узел заполнен — поступаем аналогично, но не копируем, а просто перемещаем оставшийся перемещаем ключ в родительский узел, так как это просто копия. Повторяем пока не встретим незаполненный узел или не дойдем до корня. В последнем случае корень разбивается на два узла и высота дерева увеличивается.

Поскольку в родителя всегда отправляется минимальный ключ из второй половины, то каждый ключ, который хранится во внутренней вершине — это минимум правого поддерева для этого ключа.

B Plus tree insetring.png


void split(T: BPlusTree, node: Node):
    new_node = new_Node()                  //Создаем новый узел
    new_node.right = node.right
    node.right.left = new_node
    node.right = new_node
    new_node.left = node
    mid_key = node.key[t]
    new_node.key_num = t - 1
    
    for i = 0 to new_node.key_num - 1
        new_node.key[i] = node.key[i + t + 1]
        new_node.pointers[i] = node.pointers[i + t + 1]  
        new_node.child[i] = node.child[i + t + 1]    
    new_node.child[new_node.key_num] = node.child[2 * t]  
    node.key_num = t
    
    if node.leaf
        ++new_node.key_num
        new_node.leaf = true
        for i = new_node.key_num - 1 downto 1
            new_node.key[i] = node.key[i - 1]
            new_node.pointers[i] = node.pointers[i - 1]
        new_node.key[0] = node.key[t]
        new_node.pointers[0] = node.pointers[0]
    
    if node == T.root
        T.root = new_Node()
        T.root.key[0] = mid_key
        T.root.child[0] = node
        T.root.child[1] = new_node
        T.root.key_num = 1;
        node.parent = T.root
        new_node.parent = T.root
    else
        new_node.parent = node.parent
        parent = node.parent
        pos = 0
        while pos < parent.key_num and parent.key[pos] < mid_key
            ++pos
        for i = parent.key_num downto pos + 1 
            parent.key[i] = parent.key[i - 1]
        for i = parent.key_num + 1 downto pos + 2 
            parent.child[i] = parent.child[i - 1]
        parent.key[pos] = mid_key
        parent.child[pos + 1] = new_node
        ++parent.key_num
        
        if parent.key_num == 2 * t 
            split(T, parent)

Удаление

Поскольку все ключи находятся в листах, для удаления в первую очередь необходимо найти листовой узел, в котором он находится. Если узел содержит не менее [math]t - 1[/math] ключей, где [math]t[/math] — это степень дерева, то удаление завершено. Иначе необходимо выполнить попытку перераспределения элементов, то есть добавить в узел элемент из левого или правого брата (не забыв обновить информацию в родителе). Если это невозможно, необходимо выполнить слияние с братом и удалить ключ, который указывает на удалённый узел. Объединение может распространяться на корень, тогда происходит уменьшение высоты дерева. Так как мы считаем, что в дереве не может находиться [math]2[/math] одинаковых ключей, то [math]delete[/math] будет возвращать был ли удален ключ.

B-Tree-Deletions.gif

bool delete(T: BPlusTree, key: int):
    leaf = find_key(T, key)
    pos = 0
    while pos < leaf.key_num and leaf.key[pos] < key
        ++pos
    if pos == leaf.key_num or leaf.key[pos] [math]\neq[/math] key
        return false
    else 
        delete_in_node(leaf, key)                    // Удалить ключ из вершины
        return true
void delete_in_node(tec: Node, key: int):
    pos = 0
    while pos < tec.key_num and tec.key[pos] < key
        ++pos
    if pos == tec.key_num or tec.key[pos] [math]\neq[/math] key
        return
    for i = pos to tec.key_num - 1 
        tec.key[i] = tec.key[i + 1]
        tec.pointers[i] = tec.pointer[i + 1]
    for i = pos + 1 to tec.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 [math]\neq[/math] null and left_sibling.key_num > t - 1
            --left_sibling.key_num
            ++tec.key_num
            for i = 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.pointers[left_sibling.key_num]
            tec.child[0] = left_sibling.child [left_sibling.key_num + 1]
            update(tec)                                                        // Обновить ключи на пути к корню
        
        else if right_sibling [math]\neq[/math] null and right_sibling.key_num > t - 1
            --right_sibling.key_num
            ++tec.key_num
            tec.key[tec.key_num - 1] = right_sibling.key[0]
            tec.pointers[tec.key_num - 1] = right_sibling.child[0]
            tec.child[tec.key_num - 1] = right_sibling.pointers[0]
            update(tec)  
         
        else
            if left_sibling [math]\neq[/math] null 
                left_sibling.right = tec.right
                tec.right.left = left_sibling 
                for i = 0 to tec.key_num - 1
                    left_sibling.key[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
                left_sibling.child[left_sibling.key_num + 1] = tec.child[tec.key_num]
                update(left_sibling) 
                delete_in_node(left_sibling.parent, min_key(tec))      // Удаляем разделительный ключ в отце
             
            else
                right_sibling.right.left = tec 
                tec.right = right_sibling.right
                for 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]
                update(tec)
                delete_in_node(tec.parent, min_key(right_sibling)) 
        if T.root.key_num == 1
            T.root = T.root.child[0]

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

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

См. также

Примeчания

Источники информации