Вставка в дерево B +

Опубликовано: 9 Января, 2022

Предпосылка: Введение деревьев B +

В этой статье мы обсудим, как вставить узел в B + Tree. При вставке необходимо соблюдать следующие свойства B + Tree:

  • Каждый узел, кроме корневого, может иметь не более M дочерних узлов и не менее ceil (M / 2) дочерних узлов.
  • Каждый узел может содержать максимум M - 1 ключей и минимум ceil (M / 2) - 1 ключей.
  • У корня есть как минимум два потомка и как минимум один ключ поиска.
  • При вставке переполнение узла происходит, когда он содержит более M - 1 значений ключа поиска.

Здесь M - порядок дерева B +.

Шаги для вставки в B + Tree

  1. Каждый элемент вставляется в листовой узел. Итак, переходим к соответствующему листу узла.
  2. Вставьте ключ в листовой узел в порядке возрастания, только если нет переполнения. В случае переполнения выполните следующие шаги, упомянутые ниже, чтобы справиться с переполнением при сохранении свойств B + Tree.

Свойства для вставки B + Tree

Случай 1: переполнение в листовом узле

  1. Разделите листовой узел на два узла.
  2. Первый узел содержит значения ceil ((m-1) / 2) .
  3. Второй узел содержит остальные значения.
  4. Скопируйте наименьшее значение ключа поиска со второго узла в родительский узел (со смещением вправо)

Ниже приведена иллюстрация вставки 8 в B + Tree порядка 5:

Случай 2: переполнение в нелистовом узле

  1. Разделите нелистовой узел на два узла.
  2. Первый узел содержит значения ceil (m / 2) -1.
  3. Переместите наименьшее из оставшихся к родителю.
  4. Второй узел содержит оставшиеся ключи.

Ниже приведена иллюстрация вставки 15 в дерево B + порядка 5:

Пример для иллюстрации вставки в дерево B +

Проблема: вставьте следующие ключевые значения 6, 16, 26, 36, 46 в дерево B + с порядком = 3.
Решение:
Шаг 1. Порядок равен 3, то есть максимум в узле, поэтому может быть только 2 значения ключа поиска. Поскольку вставка происходит на листовом узле только в дереве B +, вставляйте значения ключа поиска 6 и 16 в узел в порядке возрастания. Ниже приведена иллюстрация того же:

Шаг 2: Мы не можем вставить 26 в тот же узел, так как это вызывает переполнение в листовом узле. Мы должны разделить листовой узел в соответствии с правилами. Первая часть содержит значения ceil ((3-1) / 2), т.е. только 6 . Второй узел содержит оставшиеся значения, то есть 16 и 26 . Затем также скопируйте наименьшее значение ключа поиска из второго узла в родительский узел, т. Е. 16, в родительский узел. Ниже приведена иллюстрация того же:

Шаг 3: Теперь следующее значение - 36 , которое должно быть вставлено после 26, но в этом узле это снова вызывает переполнение в этом листовом узле. Снова выполните описанные выше шаги, чтобы разделить узел. Первая часть содержит значения ceil ((3-1) / 2), т.е. только 16 . Второй узел содержит оставшиеся значения, то есть 26 и 36 . Затем также скопируйте наименьшее значение ключа поиска из второго узла в родительский узел, т. Е. 26, в родительский узел. Ниже приведена иллюстрация того же:
Иллюстрация представлена на схеме ниже.

Шаг 4: Теперь нам нужно вставить 46, который должен быть вставлен после 36, но это вызывает переполнение в листовом узле. Итак, мы разбиваем узел по правилам. Первая часть содержит 26, а вторая часть содержит 36 и 46, но теперь мы также должны скопировать 36 в родительский узел, но это вызывает переполнение, поскольку в узле могут быть размещены только два значения ключа поиска. Теперь выполните шаги, чтобы справиться с переполнением в нелистовом узле.
Первый узел содержит значения ceil (3/2) -1, то есть «16».
Переместите наименьший из оставшихся к родительскому узлу, т.е. «26» будет новым родительским узлом.
Второй узел содержит оставшиеся ключи, т.е. «36», а остальные листовые узлы остаются прежними. Ниже приведена иллюстрация того же:

Below is the implementation of insertion in the B+ tree:

C++

// C++ program for implementing B+ Tree
#include <climits>
#include <fstream>
#include <iostream>
#include <sstream>
using namespace std;
int MAX = 3;
  
// BP node
class Node {
    bool IS_LEAF;
    int *key, size;
    Node** ptr;
    friend class BPTree;
  
public:
    Node();
};
  
// BP tree
class BPTree {
    Node* root;
    void insertInternal(int,
                        Node*,
                        Node*);
    Node* findParent(Node*, Node*);
  
public:
    BPTree();
    void search(int);
    void insert(int);
    void display(Node*);
    Node* getRoot();
};
  
// Constructor of Node
Node::Node()
{
    key = new int[MAX];
    ptr = new Node*[MAX + 1];
}
  
// Initialise the BPTree Node
BPTree::BPTree()
{
    root = NULL;
}
  
// Function to find any element
// in B+ Tree
void BPTree::search(int x)
{
  
    // If tree is empty
    if (root == NULL) {
        cout << "Tree is empty ";
    }
  
    // Traverse to find the value
    else {
  
        Node* cursor = root;
  
        // Till we reach leaf node
        while (cursor->IS_LEAF == false) {
  
            for (int i = 0;
                 i < cursor->size; i++) {
  
                // If the element to be
                // found is not present
                if (x < cursor->key[i]) {
                    cursor = cursor->ptr[i];
                    break;
                }
  
                // If reaches end of the
                // cursor node
                if (i == cursor->size - 1) {
                    cursor = cursor->ptr[i + 1];
                    break;
                }
            }
        }
  
        // Traverse the cursor and find
        // the node with value x
        for (int i = 0;
             i < cursor->size; i++) {
  
            // If found then return
            if (cursor->key[i] == x) {
                cout << "Found ";
                return;
            }
        }
  
        // Else element is not present
        cout << "Not found ";
    }
}
  
// Function to implement the Insert
// Operation in B+ Tree
void BPTree::insert(int x)
{
  
    // If root is null then return
    // newly created node
    if (root == NULL) {
        root = new Node;
        root->key[0] = x;
        root->IS_LEAF = true;
        root->size = 1;
    }
  
    // Traverse the B+ Tree
    else {
        Node* cursor = root;
        Node* parent;
  
        // Till cursor reaches the
        // leaf node
        while (cursor->IS_LEAF
               == false) {
  
            parent = cursor;
  
            for (int i = 0;
                 i < cursor->size;
                 i++) {
  
                // If found the position
                // where we have to insert
                // node
                if (x < cursor->key[i]) {
                    cursor
                        = cursor->ptr[i];
                    break;
                }
  
                // If reaches the end
                if (i == cursor->size - 1) {
                    cursor
                        = cursor->ptr[i + 1];
                    break;
                }
            }
        }
  
        if (cursor->size < MAX) {
            int i = 0;
            while (x > cursor->key[i]
                   && i < cursor->size) {
                i++;
            }
  
            for (int j = cursor->size;
                 j > i; j--) {
                cursor->key[j]
                    = cursor->key[j - 1];
            }
  
            cursor->key[i] = x;
            cursor->size++;
  
            cursor->ptr[cursor->size]
                = cursor->ptr[cursor->size - 1];
            cursor->ptr[cursor->size - 1] = NULL;
        }
  
        else {
  
            // Create a newLeaf node
            Node* newLeaf = new Node;
  
            int virtualNode[MAX + 1];
  
            // Update cursor to virtual
            // node created
            for (int i = 0; i < MAX; i++) {
                virtualNode[i]
                    = cursor->key[i];
            }
            int i = 0, j;
  
            // Traverse to find where the new
            // node is to be inserted
            while (x > virtualNode[i]
                   && i < MAX) {
                i++;
            }
  
            // Update the current virtual
            // Node to its previous
            for (int j = MAX + 1;
                 j > i; j--) {
                virtualNode[j]
                    = virtualNode[j - 1];
            }
  
            virtualNode[i] = x;
            newLeaf->IS_LEAF = true;
  
            cursor->size = (MAX + 1) / 2;
            newLeaf->size
                = MAX + 1 - (MAX + 1) / 2;
  
            cursor->ptr[cursor->size]
                = newLeaf;
  
            newLeaf->ptr[newLeaf->size]
                = cursor->ptr[MAX];
  
            cursor->ptr[MAX] = NULL;
  
            // Update the current virtual
            // Node"s key to its previous
            for (i = 0;
                 i < cursor->size; i++) {
                cursor->key[i]
                    = virtualNode[i];
            }
  
            // Update the newLeaf key to
            // virtual Node
            for (i = 0, j = cursor->size;
                 i < newLeaf->size;
                 i++, j++) {
                newLeaf->key[i]
                    = virtualNode[j];
            }
  
            // If cursor is the root node
            if (cursor == root) {
  
                // Create a new Node
                Node* newRoot = new Node;
  
                // Update rest field of
                // B+ Tree Node
                newRoot->key[0] = newLeaf->key[0];
                newRoot->ptr[0] = cursor;
                newRoot->ptr[1] = newLeaf;
                newRoot->IS_LEAF = false;
                newRoot->size = 1;
                root = newRoot;
            }
            else {
  
                // Recursive Call for
                // insert in internal
                insertInternal(newLeaf->key[0],
                               parent,
                               newLeaf);
            }
        }
    }
}
  
// Function to implement the Insert
// Internal Operation in B+ Tree
void BPTree::insertInternal(int x,
                            Node* cursor,
                            Node* child)
{
  
    // If we doesn"t have overflow
    if (cursor->size < MAX) {
        int i = 0;
  
        // Traverse the child node
        // for current cursor node
        while (x > cursor->key[i]
               && i < cursor->size) {
            i++;
        }
  
        // Traverse the cursor node
        // and update the current key
        // to its previous node key
        for (int j = cursor->size;
             j > i; j--) {
  
            cursor->key[j]
                = cursor->key[j - 1];
        }
  
        // Traverse the cursor node
        // and update the current ptr
        // to its previous node ptr
        for (int j = cursor->size + 1;
             j > i + 1; j--) {
            cursor->ptr[j]
                = cursor->ptr[j - 1];
        }
  
        cursor->key[i] = x;
        cursor->size++;
        cursor->ptr[i + 1] = child;
    }
  
    // For overflow, break the node
    else {
  
        // For new Interval
        Node* newInternal = new Node;
        int virtualKey[MAX + 1];
        Node* virtualPtr[MAX + 2];
  
        // Insert the current list key
        // of cursor node to virtualKey
        for (int i = 0; i < MAX; i++) {
            virtualKey[i] = cursor->key[i];
        }
  
        // Insert the current list ptr
        // of cursor node to virtualPtr
        for (int i = 0; i < MAX + 1; i++) {
            virtualPtr[i] = cursor->ptr[i];