B-ДЕРЕВО в структуре данных: пример операции поиска, вставки, удаления

Содержание:

Anonim

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

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

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

В этом руководстве по B-дереву вы узнаете:

  • Что такое B-дерево?
  • Зачем использовать B-Tree
  • История B Tree
  • Поисковая операция
  • Вставить операцию
  • Удалить операцию

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

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

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

  • Каждый узел, кроме корневого, должен содержать минимум ключей 
    [m/2]-1
    Например: 
    m = 4min keys: 4/2-1 = 1
  • Максимальное количество дочерних узлов, которое может иметь узел, равно его степени, которая равна 
    m
  • Минимальное количество дочерних узлов, которое может иметь узел, составляет половину порядка, то есть m / 2 (берется максимальное значение).
  • Все ключи в узле отсортированы в порядке возрастания.

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

Вот причины использования B-Tree

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

История B Tree

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

Поисковая операция

Операция поиска - самая простая операция в B-дереве.

Применяется следующий алгоритм:

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

Вставить операцию

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

Применяется следующий алгоритм:

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

КОНЧИК

Следующее неверно об алгоритме вставки:

Поскольку узел заполнен, он будет разделен, а затем будет вставлено новое значение

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

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

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

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

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

  • У узла меньше максимального количества ключей
  • 1 вставлен рядом с 3, но правило возрастания нарушено
  • Чтобы это исправить, ключи отсортированы

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

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

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

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

Удалить операцию

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

Применяется следующий алгоритм:

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

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

  • Цель находится в листовом узле, больше чем min ключей.
    • Удаление этого не нарушает свойства B Tree
  • Цель находится в листовом узле, у нее есть минимальные ключевые узлы
    • Удаление этого нарушит свойство B Tree
    • Целевой узел может заимствовать ключ от непосредственного левого узла или непосредственного правого узла (родственного брата)
    • Брат или сестра скажет " да", если у него больше минимального количества ключей.
    • Ключ будет заимствован из родительского узла, максимальное значение будет передано родительскому узлу, максимальное значение родительского узла будет передано целевому узлу, а целевое значение будет удалено.
  • Цель находится в листовом узле, но у братьев и сестер больше минимального количества ключей
    • Искать ключ
    • Слияние с братьями и сестрами и минимумом родительских узлов
    • Всего ключей теперь будет больше мин.
    • Целевой ключ будет заменен минимумом родительского узла

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Смотрите процедуру удаления такого ключа:

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

Удалить псевдокод операции

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

Выход :

Самый большой элемент удаляется из B-Tree.

Резюме:

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