B-дерево в структуре данных: поиск, вставка, удаление

Что такое B-дерево?

Б Дерево B-дерево — это самобалансирующаяся структура данных, основанная на определенном наборе правил для более быстрого и эффективного с точки зрения памяти поиска, вставки и удаления данных. Для достижения этой цели при создании B-дерева используются следующие правила.

B-дерево — это особый тип дерева в структуре данных. В 1972 году этот метод был впервые предложен МакКрейтом и Байером, которые назвали его сбалансированным по высоте m-сторонним деревом поиска. Оно помогает сохранять данные отсортированными и позволяет выполнять различные операции, такие как вставка, поиск и удаление, за меньшее время.

Правила для B-дерева

Вот важные правила для создания B-дерева:

• Все листья будут созданы на одном уровне.
• B-дерево определяется числом степеней, которое также называется «порядком» (задается внешним субъектом, например, программистом), и обозначается как m далее. Значение m зависит от размера блока на диске, на котором в основном расположены данные.
• Левое поддерево узла будет иметь меньшие значения, чем правая часть поддерева. Это означает, что узлы также сортируются по возрастанию слева направо.
• Максимальное количество ключей, которое может содержать корневой узел, а также его дочерние узлы, рассчитывается по следующей формуле: m − 1. Например:

  m = 4
  max keys: 4 − 1 = 3

• Каждый узел, за исключением корневого, должен содержать как минимум одно количество ключей. [m/2] − 1. Например:

  m = 4
  min keys: 4/2 − 1 = 1

• Максимальное количество дочерних узлов, которое может иметь узел, равно его степени, которая равна m.
• Минимальное количество дочерних элементов, которое может иметь узел, составляет половину порядка, то есть m/2 (берется предельное значение).
• Все ключи в узле сортируются по возрастанию.

Зачем использовать B-дерево

Вот причины, по которым стоит использовать B-Tree:

• Уменьшает количество операций чтения с диска.
• B-деревья легко оптимизировать, регулируя их размер (то есть количество дочерних узлов) в зависимости от размера диска.
• Это специально разработанный метод для обработки больших объемов данных.
• Это полезный алгоритм для баз данных и файловых систем.
• Это хороший выбор, когда речь идёт о чтении и записи больших объёмов данных.

История B-Дерева

• Данные хранятся на диске блоками. Эти данные, будучи загруженными в оперативную память (ОЗУ), называются структурой данных.
• В случае больших объемов данных поиск одной записи на диске требует чтения всего диска; это увеличивает время и потребление оперативной памяти из-за высокой частоты обращений к диску и размера данных.
• Для решения этой проблемы создаются индексные таблицы, которые сохраняют ссылки на записи в зависимости от блоков, в которых они находятся. Это значительно сокращает время и потребление памяти.
• Поскольку у нас огромные данные, мы можем создавать многоуровневые индексные таблицы.
• Многоуровневый индекс можно построить, используя B-дерево для управленияping Данные отсортированы таким образом, что происходит самобалансировка.

Поиск Operaпроизводство

Операция поиска является простейшей операцией на B-дереве. Применяется следующий алгоритм:

• Пусть ключ (значение), подлежащее поиску, будет «k».
• Начните поиск с корня и рекурсивно перемещайтесь вниз.
• Если k меньше значения корня, поиск выполняется в левом поддереве; если k больше значения корня, поиск выполняется в правом поддереве.
• Если узел имеет найденный k, просто верните узел.
• Если k не найден в узле, перейдите к дочернему узлу с большим ключом.
• Если k не найден в дереве, мы возвращаем NULL.

Вставить Operaпроизводство

Поскольку B-дерево является самобалансирующимся деревом, невозможно принудительно вставить ключ в любой узел. Применяется следующий алгоритм:

• Запустите операцию поиска и найдите подходящее место вставки.
• Вставьте новый ключ в нужное место, но если узел уже имеет максимальное количество ключей:
• Узел вместе с вновь вставленным ключом отделится от среднего элемента.
• Средний элемент станет родительским для двух других дочерних узлов.
• Узлы должны переставить ключи в порядке возрастания.

В приведенном выше примере:

• Найдите ключ в соответствующем месте узла.
• Вставьте ключ в целевой узел и проверьте наличие правил.
• После вставки имеет ли узел больше или равное минимальному количеству ключей, то есть 1? В этом случае — да. Проверьте следующее правило.
• После вставки, превышает ли узел максимальное количество ключей, равное 3? В этом случае — нет. Это означает, что B-дерево не нарушает никаких правил, и вставка завершена.

В приведенном выше примере:

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

В приведенном выше примере:

• Узел содержит меньше максимального количества ключей.
• Цифра 1 вставлена ​​рядом с цифрой 3, но правило возрастающего порядка нарушается.
• Для решения этой проблемы ключи были рассортированы.

Аналогично, числа 13 и 2 можно легко вставить в узел, поскольку они удовлетворяют правилу «меньше максимального количества ключей» для узлов.

В приведенном выше примере:

• Узел имеет ключи, равные максимальному количеству ключей.
• Ключ вставлен в целевой узел, но при этом нарушается правило максимального количества ключей.
• Целевой узел разделен, и средний ключ с левым смещением теперь является родительским для новых дочерних узлов.
• Новые узлы располагаются в порядке возрастания.

Аналогичным образом, на основе приведенных выше правил и случаев, остальные значения можно легко вставить в B-дерево.

Удалить Operaпроизводство

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

• Выполните операцию поиска и найдите целевой ключ в узлах.
• В зависимости от местоположения целевого ключа применяются три условия, как поясняется в следующих разделах.

Если целевой ключ находится в конечном узле

• Target В листовом узле находится более минимального количества ключей. Удаление этого параметра не нарушит свойства B-дерева.
• Target Находится в листовом узле и содержит узлы с минимальным ключом. Удаление этого узла нарушит свойство B-дерева.
• Целевой узел может заимствовать ключ у непосредственно расположенного слева узла или непосредственно расположенного справа узла (родственного узла).
• Брат или сестра скажет Да если количество ключей превышает минимальное.
• Ключ будет заимствован у родительского узла, максимальное значение будет передано родительскому узлу, максимальное значение родительского узла будет передано целевому узлу, а целевое значение будет удалено.
• Target Если в листовом узле находится элемент, но ни у одного из его соседей нет больше минимального количества ключей: выполняется поиск ключа, объединение с соседними узлами и минимальным количеством ключей родительского узла, общее количество ключей теперь будет больше минимального, и целевой ключ будет заменен минимальным ключом родительского узла.

Если целевой ключ находится во внутреннем узле

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

Если целевой ключ находится в корневом узле

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

Теперь давайте разберемся с операцией удаления на примере.

На приведенной выше диаграмме показаны различные случаи операции удаления в B-дереве. Это B-дерево имеет порядок 5, что означает, что минимальное количество дочерних узлов, которое может иметь любой узел, равно 3, а максимальное количество дочерних узлов, которое может иметь любой узел, равно 5. При этом минимальное и максимальное количество ключей, которые может иметь любой узел, равны 2 и 4 соответственно.

В приведенном выше примере:

• Целевой узел имеет целевой ключ для удаления.
• Целевой узел содержит больше ключей, чем минимальное количество ключей.
• Просто удалите ключ.

В приведенном выше примере:

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

Следующая диаграмма объясняет, как удалить этот ключ:

• Целевой узел заимствует ключ у ближайшего соседа, в данном случае, у предшественника в порядке следования (левого соседа), поскольку у него нет преемника в порядке следования (правого соседа).
• Максимальное значение предшествующего узла в порядке следования будет передано родительскому узлу, а родительский узел передаст максимальное значение целевому узлу (см. диаграмму ниже).

В следующем примере показано, как удалить ключ, которому требуется значение из его преемника по порядку.

• Целевой узел заимствует ключ у ближайшего соседа, в данном случае, у правого соседа, поскольку у его предшественника (левого соседа) ключи равны минимальному числу ключей.
• Минимальное значение преемника по порядку будет передано родительскому узлу, а родительский узел передаст максимальное значение целевому узлу.

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

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

Удалить Operaпсевдо- Code

private int removeBiggestElement()
{
    if (root has no child)
        remove and return the last element
    else {
        answer = subset[childCount-1].removeBiggestElement()
        if (subset[childCount-1].dataCount < MINIMUM)
            fixShort (childCount-1)
        return answer
    }
}

Выход: Самый большой элемент удаляется из B-дерева.

Часто задаваемые вопросы (FAQ)