Учебники

4) B ДЕРЕВО в структуре данных

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

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

B-дерево – это особый вид дерева в структуре данных. В 1972 году этот метод был впервые представлен McCreight, и Bayer назвал его m-way Search Tree с сбалансированной высотой. Это помогает сохранить отсортированные данные и позволяет выполнять различные операции, такие как вставка, поиск и удаление, за меньшее время.

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

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

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

  • Все листья будут созданы на одном уровне.
  • B-Tree определяется числом степеней, которые также называют «порядком» (указанным внешним субъектом, например, программистом), называемым
    m

    и далее. Значение

    m

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

  • Левое поддерево узла будет иметь меньшие значения, чем правая сторона поддерева. Это означает, что узлы также сортируются в порядке возрастания слева направо.
  • Максимальное количество дочерних узлов, которые может содержать корневой узел, а также его дочерние узлы, рассчитывается по следующей формуле:
    m – 1

    Например:

    m = 4
    max keys: 4 – 1 = 3
    

  • Каждый узел, кроме root, должен содержать минимальные ключи
    [m/2]-1

    Например:

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

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

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

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

История B Tree

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

Операция поиска

Операция поиска является самой простой операцией на B Tree.

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

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

Операция вставки

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

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

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

ПОДСКАЗКА

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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-дерева.

Резюме:

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