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

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

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

• Все листья будут созданы на одном уровне.
• 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-дерева для самобалансирующейся сортировки данных.

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

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

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

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

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

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

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

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

СОВЕТ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Удалить OperaПсевдокод

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-дереве является самой простой, она всегда начинается с корня и проверяет, больше или меньше целевой ключ значения узла.
• Операция вставки B-дерева довольно подробная: сначала находит подходящую позицию вставки для целевого ключа, вставляет ее, оценивает достоверность B-дерева для различных случаев, а затем соответствующим образом реструктурирует узлы B-дерева.
• Операция удаления B-дерева сначала ищет целевой ключ, который нужно удалить, удаляет его, оценивает достоверность на основе нескольких случаев, таких как минимальный и максимальный ключи целевого узла, одноуровневых узлов и родителя.