Реализация B * -Trees в C ++

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

B * -дерево порядка m - это дерево поиска, которое либо пусто, либо удовлетворяет трем свойствам:

  • У корневого узла минимум два и максимум два этажа ((2m-2) / 3) +1 детей
  • Остальные внутренние узлы имеют минимальный этаж ((2m-1) / 3) и максимальный m дочерних элементов.
  • Все внешние узлы находятся на одном уровне.

Преимущество использования B *-деревьев перед B-деревьями - это уникальная особенность, называемая разделением «два на три». Таким образом, минимальное количество ключей в каждом узле составляет не половину максимального числа, а две трети от него, что делает данные намного более компактными. Однако недостатком этого является сложная операция удаления.

Трудности практической реализации алгоритма B-star способствуют тому, что он не так регулярно используется, как его аналоги B и B +.
Ниже представлена базовая реализация функции вставки B-звезды - просто чтобы продемонстрировать ее отличие от B (полная реализация была бы гораздо более длительной и сложной).

Уникальные части алгоритма вставки B * Tree заключаются в следующем:

Два-три сплита

1. При вставке в полный листовой узел (который не является корневым) и который имеет полного правого брата (и чей родительский узел имеет хотя бы один свободный ключ):

  • Возьмите массив ('marray'), состоящий из ключей 'm-1' полного листового узла, родительского ключа этого узла, нового ключа, который нужно вставить, и ключей 'm-1' его правого брата ( Всего m-1 + 1 + 1 + m-1 = 2m ключей)
  • Отсортируйте эти ключи
  • Создайте три новых узла:
    • p - чьи ключи являются первыми (2m - 2) / 3 элементами 'marray'
      Элемент с индексом (2m - 2) / 3 сохраняется как 'parent1'
    • q - чьи ключи являются следующими (2m - 1) / 3 элементами 'marray' после parent1
      Элемент с индексом (4m) / 3 сохраняется как parent2.
    • r - чьи ключи являются последними (2m) / 3 элементами 'marray' после parent2
  • Ключ в родительском элементе листа, который указывает на этот лист, должно иметь значение, замененное на 'parent1'.
  • Если у родительского ключа в iv) есть какие-либо смежные ключи, их следует сдвинуть вправо. В оставшееся пространство поместите parent2.
  • p, q и r должны быть дочерними ключами parent1 и parent2 (если parent1 и parent2 - первые два ключа в родительском узле), иначе p, q, r должны быть дочерними ключами ключа перед родитель 1, родитель 1 и родитель 2 соответственно.

Перед вставкой:

После прошивки:

2. При вставке в полный листовой узел (который не является корневым) с пустым / неполным правым братом.

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

    3. Остальные случаи такие же, как для B-деревьев.



    Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

    Примеры:

    Input: Add 4 to 1 2 3 L 5 R 7 8 9
    Output: 1 2 L 3 7 R 4 5 R 8 9
    3 and 7 become the parent keys by the two-three split

    Input : Add 5 to 2 3 4 L 6 R 8 9 11
    Output : 2 3 L 4 8 R 5 6 R 9 11
    3 and 6 become the parent keys by the two-three split

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

    // CPP program to implement B* tree
    #include <bits/stdc++.h>
    using namespace std;
    // This can be changed to any value -
    // it is the order of the B* Tree
    #define N 4
    struct node {
    // key of N-1 nodes
    int key[N - 1];
    // Child array of 'N' length
    struct node* child[N];
    // To state whether a leaf or not; if node
    // is a leaf, isleaf=1 else isleaf=0
    int isleaf;
    // Counts the number of filled keys in a node
    int n;
    // Keeps track of the parent node
    struct node* parent;
    };
    // This function searches for the leaf
    // into which to insert element 'k'
    struct node* searchforleaf( struct node* root, int k,
    struct node* parent, int chindex)
    {
    if (root) {
    // If the passed root is a leaf node, then
    // k can be inserted in this node itself
    if (root->isleaf == 1)
    return root;
    // If the passed root is not a leaf node,
    // implying there are one or more children
    else {
    int i;
    /*If passed root's initial key is itself g
    reater than the element to be inserted,
    we need to insert to a new leaf left of the root*/
    if (k < root->key[0])
    root = searchforleaf(root->child[0], k, root, 0);
    else
    {
    // Find the first key whose value is greater
    // than the insertion value
    // and insert into child of that key
    for (i = 0; i < root->n; i++)
    if (root->key[i] > k)
    root = searchforleaf(root->child[i], k, root, i);
    // If all the keys are less than the insertion
    // key value, insert to the right of last key
    if (root->key[i - 1] < k)
    root = searchforleaf(root->child[i], k, root, i);
    }
    }
    }
    else {
    // If the passed root is NULL (there is no such
    // child node to search), then create a new leaf
    // node in that location
    struct node* newleaf = new node; struct
    newleaf->isleaf = 1;
    newleaf->n = 0;
    parent->child[chindex] = newleaf;
    newleaf->parent = parent;
    return newleaf;
    }
    }
    struct node* insert( struct node* root, int k)
    {
    if (root) {
    struct node* p = searchforleaf(root, k, NULL, 0);
    struct node* q = NULL;
    int e = k;
    // If the leaf node is empty, simply
    // add the element and return
    for ( int e = k; p; p = p->parent) {
    if (p->n == 0) {
    p->key[0] = e;
    p->n = 1;
    return root;
    }
    // If number of filled keys is less than maximum
    if (p->n < N - 1) {
    int i;
    for (i = 0; i < p->n; i++) {
    if (p->key[i] > e) {
    for ( int j = p->n - 1; j >= i; j--)
    p->key[j + 1] = p->key[j];
    break ;
    }
    }
    p->key[i] = e;
    p->n = p->n + 1;
    return root;
    }
    // If number of filled keys is equal to maximum
    // and it's not root and there is space in the parent
    if (p->n == N - 1 && p->parent && p->parent->n < N) {
    int m;
    for ( int i = 0; i < p->parent->n; i++)
    if (p->parent->child[i] == p) {
    m = i;
    break ;
    }
    // If right sibling is possible
    if (m + 1 <= N - 1)
    {
    // q is the right sibling
    q = p->parent->child[m + 1];
    if (q) {
    // If right sibling is full
    if (q->n == N - 1) {
    struct node* r = new node; struct
    int * z = new int [((2 * N) / 3)];
    int parent1, parent2;
    int * marray = new int [2 * N];
    int i;
    for (i = 0; i < p->n; i++)
    marray[i] = p->key[i];
    int fege = i;
    marray[i] = e;
    marray[i + 1] = p->parent->key[m];
    for ( int j = i + 2; j < ((i + 2) + (q->n)); j++)
    marray[j] = q->key[j - (i + 2)];
    // marray=bubblesort(marray, 2*N)
    // a more rigorous implementation will
    // sort these elements
    // Put first (2*N-2)/3 elements into keys of p
    for ( int i = 0; i < (2 * N - 2) / 3; i++)
    p->key[i] = marray[i];
    parent1 = marray[(2 * N - 2) / 3];
    // Put next (2*N-1)/3 elements into keys of q
    for ( int j = ((2 * N - 2) / 3) + 1; j < (4 * N) / 3; j++)
    q->key[j - ((2 * N - 2) / 3 + 1)] = marray[j];
    parent2 = marray[(4 * N) / 3];
    // Put last (2*N)/3 elements into keys of r
    for ( int f = ((4 * N) / 3 + 1); f < 2 * N; f++)
    r->key[f - ((4 * N) / 3 + 1)] = marray[f];
    // Because m=0 and m=1 are children of the same key,
    // a special case is made for them
    if (m == 0 || m == 1) {
    p->parent->key[0] = parent1;
    p->parent->key[1] = parent2;
    p->parent->child[0] = p;
    p->parent->child[1] = q;
    p->parent->child[2] = r;
    return root;
    }
    else {
    p->parent->key[m - 1] = parent1;
    p->parent->key[m] = parent2;
    p->parent->child[m - 1] = p;
    p->parent->child[m] = q;
    p->parent->child[m + 1] = r;
    return root;
    }
    }
    }
    else // If right sibling is not full
    {
    int put;
    if (m == 0 || m == 1)
    put = p->parent->key[0];
    else
    put = p->parent->key[m - 1];
    for ( int j = (q->n) - 1; j >= 1; j--)
    q->key[j + 1] = q->key[j];
    q->key[0] = put;
    p->parent->key[m == 0 ? m : m - 1] = p->key[p->n - 1];
    }
    }
    }
    }
    /*Cases of root splitting, etc. are omitted
    as this implementation is just to demonstrate
    the two-three split operation*/
    }
    else
    {
    // Create new node if root is NULL
    struct node* root = new node; struct
    root->key[0] = k;
    root->isleaf = 1;
    root->n = 1;
    root->parent = NULL;
    }
    }
    // Driver code
    int main()
    {
    /* Consider the following tree that has been obtained
    from some root split:
    6
    /
    1 2 4 7 8 9
    We wish to add 5. This makes the B*-tree:
    4 7
    /
    1 2 5 6 8 9
    Contrast this with the equivalent B-tree, in which
    some nodes are less than half full
    4 6
    /
    1 2 5 7 8 9
    */
    // Start with an empty root
    struct node* root = NULL;
    // Insert 6
    root = insert(root, 6);
    // Insert 1, 2, 4 to the left of 6
    root->child[0] = insert(root->child[0], 1);
    root->child[0] = insert(root->child[0], 2);
    root->child[0] = insert(root->child[0], 4);
    root->child[0]->parent = root;
    // Insert 7, 8, 9 to the right of 6
    root->child[1] = insert(root->child[1], 7);
    root->child[1] = insert(root->child[1], 8);
    root->child[1] = insert(root->child[1], 9);
    root->child[1]->parent = root;
    cout << "Original tree: " << endl;
    for ( int i = 0; i < root->n; i++)
    cout << root->key[i] << " " ;
    cout << endl;
    for ( int i = 0; i < 2; i++) {
    cout << root->child[i]->key[0] << " " ;
    cout << root->child[i]->key[1] << " " ;
    cout << root->child[i]->key[2] << " " ;
    }
    cout << endl;
    cout << "After adding 5: " << endl;
    // Inserting element '5':
    root->child[0] = insert(root->child[0], 5);
    // Printing nodes
    for ( int i = 0; i <= root->n; i++)
    cout << root->key[i] << " " ;
    cout << endl;
    for ( int i = 0; i < N - 1; i++) {
    cout << root->child[i]->key[0] << " " ;
    cout << root->child[i]->key[1] << " " ;
    }
    return 0;
    }

    Выход:

    Исходное дерево:
6
1 2 4 7 8 9
После добавления 5:
4 7
1 2 5 6 8 9

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

    Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.

    • DBMS

    РЕКОМЕНДУЕМЫЕ СТАТЬИ

    Что такое язык программирования четвертого поколения?
    22 Февраля, 2023
    Разница между ER-моделированием и трехмерным моделированием
    24 Января, 2023
    Infosys SDE Sheet: Вопросы и ответы для интервью
    12 Декабря, 2022
    Применение структур данных в реальном времени
    6 Октября, 2022
    Производственные базы данных в SQL-запросах
    28 Августа, 2022
    Уровень бизнес-логики
    28 Августа, 2022
    Разница между представлением и таблицей
    28 Августа, 2022
    План оценки запроса в SQL
    28 Августа, 2022