Рубрики

Введение B-Tree

B-Tree — это самобалансирующееся дерево поиска. В большинстве других самобалансируемых поисковых деревьев (таких как AVL и красно-черные деревья) предполагается, что все находится в основной памяти. Чтобы понять использование B-Trees, мы должны подумать об огромном количестве данных, которые не помещаются в основную память. Когда количество ключей велико, данные считываются с диска в виде блоков. Время доступа к диску очень велико по сравнению с временем доступа к основной памяти. Основная идея использования B-Trees — уменьшить количество обращений к диску. Большинство операций с деревом (поиск, вставка, удаление, max, min, ..etc) требуют O (h) обращений к диску, где h — высота дерева. B-дерево — это толстое дерево. Высота B-деревьев поддерживается на низком уровне путем помещения максимально возможных ключей в узел B-Tree. Обычно размер узла B-Tree сохраняется равным размеру блока диска. Поскольку h для B-Tree низкое, общий доступ к диску для большинства операций значительно уменьшается по сравнению со сбалансированными деревьями двоичного поиска, такими как AVL Tree, Red-Black Tree, ..etc.

Свойства B-Tree
1) Все листья на одном уровне.
2) B-дерево определяется термином минимальная степень «t». Значение t зависит от размера дискового блока.
3) Каждый узел, кроме root, должен содержать не менее t-1 ключей. Корень может содержать минимум 1 ключ.
4) Все узлы (включая root) могут содержать максимум 2t — 1 ключей.
5) Количество дочерних узлов узла равно количеству ключей в нем плюс 1.
6) Все ключи узла отсортированы в порядке возрастания. Дочерний элемент между двумя ключами k1 и k2 содержит все ключи в диапазоне от k1 и k2.
7) B-Tree растет и сжимается от корня, что не похоже на Binary Search Tree. Деревья бинарного поиска растут вниз, а также сжимаются вниз.
8) Как и другие сбалансированные деревья бинарного поиска, сложность времени для поиска, вставки и удаления равна O (Logn).

Ниже приведен пример B-дерева минимальной степени 3. Обратите внимание, что в практических B-деревьях значение минимальной степени намного больше 3.

Поиск
Поиск аналогичен поиску в бинарном дереве поиска. Пусть ключ для поиска будет k. Начнем с корня и рекурсивно пройдем вниз. Для каждого посещенного неконечного узла, если у узла есть ключ, мы просто возвращаем узел. В противном случае мы возвращаемся к соответствующему дочернему элементу (дочернему элементу перед первым большим ключом) узла. Если мы достигаем конечного узла и не находим k в конечном узле, мы возвращаем NULL.

Траверса
Обход также похож на обход Inorder Binary Tree. Мы начинаем с самого левого дочернего элемента, рекурсивно печатаем самый левый дочерний элемент, затем повторяем тот же процесс для остальных дочерних элементов и ключей. В конце рекурсивно распечатайте самого правого ребенка.

// C ++ реализация методов search () и traverse ()
#include<iostream>

using namespace std;

  
// Узел BTree

class BTreeNode

{

    int *keys;  // Массив ключей

    int t;      // Минимальная степень (определяет диапазон для количества ключей)

    BTreeNode **C; // Массив дочерних указателей

    int n;     // Текущее количество ключей

    bool leaf; // Истинно, когда узел является листом. В противном случае ложь

public:

    BTreeNode(int _t, bool _leaf);   // Конструктор

  

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

    void traverse();

  

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

    BTreeNode *search(int k);   // возвращает NULL, если k отсутствует.

  
// Сделайте это BTree другом, чтобы мы могли получить доступ к приватным членам этого
// класс в функциях BTree

friend class BTree;

};

  
// Bree

class BTree

{

    BTreeNode *root; // Указатель на корневой узел

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

public:

    // Конструктор (Инициализирует дерево как пустое)

    BTree(int _t)

    {  root = NULL;  t = _t; }

  

    // функция для обхода дерева

    void traverse()

    if (root != NULL) root->traverse(); }

  

    // функция для поиска ключа в этом дереве

    BTreeNode* search(int k)

    return (root == NULL)? NULL : root->search(k); }

};

  
// Конструктор для класса BTreeNode

BTreeNode::BTreeNode(int _t, bool _leaf)

{

    // Копируем заданную минимальную степень и свойство листа

    t = _t;

    leaf = _leaf;

  

    // Распределяем память на максимальное количество возможных ключей

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

    keys = new int[2*t-1];

    C = new BTreeNode *[2*t];

  

    // Инициализируем количество ключей как 0

    n = 0;

}

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

void BTreeNode::traverse()

{

    // есть n ключей и n + 1 потомков, обходы через n ключей

    // и первые n детей

    int i;

    for (i = 0; i < n; i++)

    {

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

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

        if (leaf == false)

            C[i]->traverse();

        cout << " " << keys[i];

    }

  

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

    if (leaf == false)

        C[i]->traverse();

}

  
// Функция для поиска ключа k в поддереве с этим узлом

BTreeNode *BTreeNode::search(int k)

{

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

    int i = 0;

    while (i < n && k > keys[i])

        i++;

  

    // Если найденный ключ равен k, вернуть этот узел

    if (keys[i] == k)

        return this;

  

    // Если ключ не найден здесь и это листовой узел

    if (leaf == true)

        return NULL;

  

    // Перейти к соответствующему ребенку

    return C[i]->search(k);

}

Приведенный выше код не содержит драйвер программы. Мы расскажем о полной программе в нашем следующем посте о B-Tree Insertion.

Существует два соглашения для определения B-дерева: одно — определить по минимальной степени (см. В книге Кормена ), второе — по порядку. Мы следовали соглашению о минимальной степени и будем следовать тому же в следующих публикациях на B-Tree. Имена переменных, используемые в вышеуказанной программе, также сохраняются в том же виде, что и книга Кормена, для лучшей читаемости.

Вставка и удаление
Вставка B-дерева
Удаление B-Tree

Ссылки:
Введение в алгоритмы 3-е издание Клиффорд Стейн, Томас Х. Кормен, Чарльз Э. Лейзерсон, Рональд Л. Ривест

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

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

Введение B-Tree

0.00 (0%) 0 votes