Рубрики

Вставка B-Tree без агрессивного расщепления

Вставка B-Tree без агрессивного расщепления

Этот алгоритм вставки берет запись, находит конечный узел, к которому он принадлежит, и вставляет его туда. Мы рекурсивно вставляем запись, вызывая алгоритм вставки на соответствующем дочернем узле. Результатом этой процедуры является переход к конечному узлу, которому принадлежит запись, размещение записи и возврат обратно к корневому узлу.

Иногда узел заполнен, то есть содержит 2 * t — 1 записей, где t — минимальная степень. В таких случаях узел должен быть разделен. В таком случае один ключ становится родительским, и создается новый узел. Сначала мы вставляем новый ключ, делая общее количество ключей 2 * t. Мы сохраняем первые t записей в исходном узле, переносим последние (t-1) записи в новый узел и устанавливаем (t + 1) -й узел в качестве родителя этих узлов. Если разделяемый узел является не дочерним узлом, то мы также должны разделить дочерние указатели. Узел с 2 * t ключами имеет 2 * t + 1 дочерний указатель. Первые (t + 1) указатели хранятся в исходном узле, а оставшиеся t указателей переходят в новый узел.

This algorithm splits a node only when it is necessary. We first recursively call insert for appropriate child of node (in case of non-leaf node) or insert it into node (for leaf node). If the node is full, we split it, storing new child entry in newEntry and new parent key in val. These values are then inserted into the parent, which recursively splits itself in case it is also full.

Example:

We insert numbers 1 – 5 in tree. The tree becomes:

Then we insert 6, the node is full. Hence it is split into two nodes making 4 as parent.

We insert numbers 7 – 16, the tree becomes:

We insert 22 – 30, the tree becomes:

Note that now the root is full. If we insert 17 now, the root is not split as the leaf node in which 17 was inserted didn’t split. If we were following aggressive splitting, the root would have been split before we went to leaf node.

But if we insert 31, the leaf node splits, which recursively adds new entry to root. But as root is full, it needs to be split. The tree now becomes.

Ниже приведена реализация вышеуказанного подхода:

// C ++ реализация подхода
#include <iostream>
#include <vector>

using namespace std;

  

class BTreeNode {

  

    // Вектор ключей

    vector<int> keys;

  

    // Минимальная степень

    int t;

  

    // Вектор детских указателей

    vector<BTreeNode*> C;

  

    // Истинно, когда узел является листом, иначе ложно

    bool leaf;

  

public:

    // Конструктор

    BTreeNode(int t, bool leaf);

  

    // Обходим узел и печатаем его содержимое

    // с количеством вкладок перед

    void traverse(int tab);

  

    // Вставить ключ в данный узел. Если ребенок разделен, мы

    // нужно вставить * val запись в вектор ключей и

    // указатель newEntry на вектор C этого узла

    void insert(int key, int* val,

                BTreeNode*& newEntry);

  

    // Разбиваем этот узел и сохраняем новое родительское значение в

    // * val и указатель нового узла в newEntry

    void split(int* val, BTreeNode*& newEntry);

  

    // Возвращает true, если узел заполнен

    bool isFull();

  

    // Создает новый корень, устанавливая текущий корень как его дочерний

    BTreeNode* makeNewRoot(int val, BTreeNode* newEntry);

};

  

bool BTreeNode::isFull()

{

    // возвращает true, если узел заполнен

    return (this->keys.size() == 2 * t - 1);

}

  

BTreeNode::BTreeNode(int t, bool leaf)

{

    // Конструктор для установки значения t и leaf

    this->t = t;

    this->leaf = leaf;

}

  
// Функция для печати узлов B-Tree

void BTreeNode::traverse(int tab)

{

    int i;

    string s;

  

    // Напечатать 'tab' количество вкладок

    for (int j = 0; j < tab; j++) {

        s += '\t';

    }

    for (i = 0; i < keys.size(); i++) {

  

        // Если это не лист, то перед печатью ключ [i]

        // пройти поддерево с корнем дочернего C [i]

        if (leaf == false)

            C[i]->traverse(tab + 1);

        cout << s << keys[i] << endl;

    }

  

    // Распечатать поддерево с корнем из последнего потомка

    if (leaf == false) {

        C[i]->traverse(tab + 1);

    }

}

  
// Функция для разделения текущего узла и сохранения нового
// родительское значение * val и новый дочерний указатель в & newEntry
// вызывается только для расщепления неконечного узла

void BTreeNode::split(int* val, BTreeNode*& newEntry)

{

  

    // Создать новый неконечный узел

    newEntry = new BTreeNode(t, false);

  

    // (t + 1) th становится родительским

    *val = this->keys[t];

  

    // Последние (t-1) записи перейдут на новый узел

    for (int i = t + 1; i < 2 * t; i++) {

        newEntry->keys.push_back(this->keys[i]);

    }

  

    // Этот узел хранит первые t записей

    this->keys.resize(t);

  

    // Последние записи t перейдут на новый узел

    for (int i = t + 1; i <= 2 * t; i++) {

        newEntry->C.push_back(this->C[i]);

    }

  

    // Этот узел хранит первые (t + 1) записи

    this->C.resize(t + 1);

}

  
// Функция для вставки нового ключа в данный узел.
// Если дочерний элемент этого узла разделен, мы должны вставить * val
// в вектор ключей и указатель newEntry в вектор C

void BTreeNode::insert(int new_key, int* val,

                       BTreeNode*& newEntry)

{

  

    // неконечный узел

    if (leaf == false) {

        int i = 0;

  

        // Находим первый ключ больше чем new_key

        while (i < keys.size() && new_key > keys[i])

            i++;

  

        // Мы должны вставить new_key в левого потомка

        // Узел с индексом i

        C[i]->insert(new_key, val, newEntry);

  

        // Разделение не было

        if (newEntry == NULL)

            return;

        if (keys.size() < 2 * t - 1) {

  

            // Этот узел может содержать новый ключ

            // и запись дочернего указателя

            // Вставляем * val в ключевой вектор

            keys.insert(keys.begin() + i, *val);

  

            // Вставляем newEntry в вектор C

            C.insert(C.begin() + i + 1, newEntry);

  

            // Поскольку этот узел не был разделен, устанавливаем newEntry

            // в NULL

            newEntry = NULL;

        }

        else {

  

            // Вставляем * val и newentry

            keys.insert(keys.begin() + i, *val);

            C.insert(C.begin() + i + 1, newEntry);

  

            // Текущий узел имеет 2 * t ключей, поэтому разделим его

            split(val, newEntry);

        }

    }

    else {

  

        // Вставляем new_key в этот узел

        vector<int>::iterator it;

  

        // Найти правильную позицию

        it = lower_bound(keys.begin(), keys.end(),

                         new_key);

  

        // Вставить в правильное положение

        keys.insert(it, new_key);

  

        // Если узел заполнен

        if (keys.size() == 2 * t) {

  

            // Создать новый узел

            newEntry = new BTreeNode(t, true);

  

            // Установить (t + 1) -й ключ как родительский

            *val = this->keys[t];

  

            // Вставляем последние (t-1) ключи в новый узел

            for (int i = t + 1; i < 2 * t; i++) {

                newEntry->keys.push_back(this->keys[i]);

            }

  

            // Этот узел хранит первые t ключей

            this->keys.resize(t);

        }

    }

}

  
// Функция для создания нового корня
// установка текущего узла как его потомка

BTreeNode* BTreeNode::makeNewRoot(int val, BTreeNode* newEntry)

{

    // Создать новый корень

    BTreeNode* root = new BTreeNode(t, false);

  

    // Сохраняет значение ключа

    root->keys.push_back(val);

  

    // толкаем дочерние указатели

    root->C.push_back(this);

    root->C.push_back(newEntry);

    return root;

}

  

class BTree {

  

    // Корень B-Tree

    BTreeNode* root;

  

    // Минимальная степень

    int t;

  

public:

    // Конструктор

    BTree(int t);

  

    // Вставить ключ

    void insert(int key);

  

    // Показать дерево

    void display();

};

  
// Функция для создания нового BTree с
// минимальная степень t

BTree::BTree(int t)

{

    root = new BTreeNode(t, true);

}

  
// Функция для вставки узла в B-Tree

void BTree::insert(int key)

{

    BTreeNode* newEntry = NULL;

    int val = 0;

  

    // Вставить в B-Tree

    root->insert(key, &val, newEntry);

  

    // Если newEntry не Null, тогда root должен быть

    // Трещина. Создать новый корень

    if (newEntry != NULL) {

        root = root->makeNewRoot(val, newEntry);

    }

}

  
// Печатает BTree

void BTree::display()

{

    root->traverse(0);

}

  
// Код драйвера

int main()

{

  

    // Создать B-Tree

    BTree* tree = new BTree(3);

    cout << "After inserting 1 and 2" << endl;

    tree->insert(1);

    tree->insert(2);

    tree->display();

  

    cout << "After inserting 5 and 6" << endl;

    tree->insert(5);

    tree->insert(6);

    tree->display();

  

    cout << "After inserting 3 and 4" << endl;

    tree->insert(3);

    tree->insert(4);

    tree->display();

  

    return 0;

}

Выход:

After inserting 1 and 2
1
2
After inserting 5 and 6
1
2
5
6
After inserting 3 and 4
    1
    2
    3
4
    5
    6

Рекомендуемые посты:

Вставка B-Tree без агрессивного расщепления

0.00 (0%) 0 votes