Алгоритмы в B-деревьях

Поиск

Поиск похож на поиск в двоичном дереве поиска. Начиная с корня, дерево рекурсивно перемещается сверху вниз. На каждом уровне поиск сокращает свое поле зрения до дочернего указателя (поддерева), диапазон которого включает значение поиска. Диапазон поддерева определяется значениями или ключами, содержащимися в его родительском узле. Эти предельные значения также известны как значения разделения.

Бинарный поиск обычно (но не обязательно) используется в узлах, чтобы найти значения разделения и интересующее дочернее дерево.

Вставка

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

Если узел содержит меньше максимально допустимого количества элементов, тогда есть место для нового элемента. Вставьте новый элемент в узел, сохраняя элементы узла в порядке.
В противном случае узел заполнен, равномерно разделите его на два узла так:
1. Одна медиана выбирается из элементов листа и нового элемента.
2. Значения, меньшие, чем медиана, помещаются в новый левый узел, а значения, превышающие медиану, помещаются в новый правый узел, причем медиана выступает в качестве значения разделения.
3. Значение разделения вставляется в родительский узел, что может привести к его разделению и так далее. Если у узла нет родителя (то есть узел был корнем), создайте новый корень над этим узлом (увеличив высоту дерева).

Если расщепление проходит до самого корня, оно создает новый корень с одним значением разделителя и двумя дочерними элементами, поэтому нижняя граница размера внутренних узлов не применяется к корню. Максимальное количество элементов на узел - U-1. Когда узел разделяется, один элемент перемещается к родителю, но добавляется один элемент. Таким образом, должно быть возможно разделить максимальное количество U-1 элементов на два допустимых узла. Если это число нечетное, то U = 2L, и один из новых узлов содержит (U − 2)/2 = L − 1 элементов, и, следовательно, является допустимым узлом, а другой содержит еще один элемент, и, следовательно, он является допустимым тоже. Если U − 1 является четным, то U = 2L − 1, поэтому в узле есть 2L − 2 элемента. Половина этого числа составляет L-1, что является минимальным количеством элементов, разрешенным для каждого узла.

Альтернативный алгоритм поддерживает один проход по дереву от корня к узлу, где будет происходить вставка, с преимущественным разбиением любых полных узлов, встречающихся на пути. Это предотвращает необходимость вызова родительских узлов в память, что может быть дорогостоящим, если узлы находятся во вторичном хранилище. Однако, чтобы использовать этот алгоритм, мы должны иметь возможность отправить один элемент родительскому элементу и разделить оставшиеся элементы U-2 на два допустимых узла, не добавляя новый элемент. Это требует U = 2L, а не U = 2L − 1, что объясняет, почему некоторые учебники навязывают это требование при определении B-деревьев.

Удаление

Существует две популярные стратегии удаления из B-дерева.

Найдите и удалите элемент, затем реструктурируйте дерево, чтобы сохранить его инварианты, ИЛИ
Сделайте один проход вниз по дереву, но перед входом (посещением) узла реструктурируйте дерево так, чтобы после обнаружения удаляемого ключа его можно было удалить, не вызывая необходимости какой-либо дальнейшей реструктуризации

Алгоритм ниже использует предыдущую стратегию.

При удалении элемента необходимо учитывать два особых случая:

Элемент во внутреннем узле является разделителем для его дочерних узлов
Удаление элемента может поставить его узел под минимальное количество элементов и дочерних элементов

Процедуры для этих случаев в порядке ниже.

Удаление из листового узла

Найдите значение для удаления.
Если значение находится в листовом узле, просто удалите его из узла.
Если происходит недостаточное заполнение, выполните повторную балансировку дерева, как описано в разделе "Перебалансировка после удаления" ниже.

Удаление с внутреннего узла

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

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

Перебалансировка после удаления

Восстановление баланса начинается с листа и продолжается до корня, пока дерево не уравновесится. Если удаление элемента из узла привело к его минимальному размеру, то некоторые элементы должны быть перераспределены, чтобы привести все узлы к минимуму. Обычно перераспределение включает в себя перемещение элемента с одноуровневого узла, у которого больше минимального количества узлов. Эта операция перераспределения называется ротацией. Если ни один из братьев не может сэкономить элемент, то дефектный узел должен быть объединен с родным братом. В результате слияния родительский элемент теряет элемент-разделитель, поэтому родительский элемент может стать неполноценным и потребовать перебалансировки. Слияние и ребалансировка могут продолжаться вплоть до самого корня. Поскольку минимальное количество элементов не относится к корню, сделать корень единственным дефектным узлом не проблема. Алгоритм перебалансировки дерева выглядит следующим образом:

Если правый брат дефектного узла существует и имеет больше, чем минимальное количество элементов, поверните влево
1. Скопируйте разделитель из родительского в конец дефектного узла (разделитель перемещается вниз; дефектный узел теперь имеет минимальное количество элементов)
2. Замените разделитель в родительском элементе первым элементом правого родного брата (правый родной брат теряет один узел, но все еще имеет хотя бы минимальное количество элементов)
3. Дерево теперь сбалансировано
В противном случае, если левый брат дефектного узла существует и имеет больше, чем минимальное количество элементов, поверните вправо
1. Скопируйте разделитель из родительского в начало дефектного узла (разделитель перемещается вниз; дефектный узел теперь имеет минимальное количество элементов)
2. Замените разделитель в родительском элементе с последним элементом левого родного брата (левый родной брат теряет один узел, но все еще имеет по крайней мере минимальное количество элементов)
3. Дерево теперь сбалансировано
В противном случае, если у обоих непосредственных братьев есть только минимальное количество элементов, то объединяются с родным братом, отделяющим их разделитель от родителя.
1. Скопируйте разделитель в конец левого узла (левый узел может быть дефектным узлом или это может быть брат с минимальным количеством элементов)
2. Переместите все элементы от правого узла к левому узлу (теперь левый узел имеет максимальное количество элементов, а правый узел - пустой)
3. Удалить разделитель из родительского элемента вместе с пустым правым дочерним элементом (родительский элемент теряет элемент)
  - Если родитель является корнем и теперь не имеет элементов, то освободите его и сделайте объединенный узел новым корнем (дерево становится более мелким)
  - В противном случае, если родительский элемент содержит меньше необходимого количества элементов, перебалансируйте родительский элемент.

Примечание: операции перебалансировки различаются для B+ деревьев (например, ротация отличается, потому что у родителя есть копия ключа) и B* деревьев (например, три родных брата объединяются в два родных брата).

Последовательный доступ

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

Начальная конструкция

Распространенным частным случаем является добавление большого количества предварительно отсортированных данных в изначально пустое B-дерево. Хотя вполне возможно просто выполнить серию последовательных вставок, вставка отсортированных данных приводит к тому, что дерево почти полностью состоит из наполовину заполненных узлов. Вместо этого можно использовать специальный алгоритм "массовой загрузки" для создания более эффективного дерева с более высоким коэффициентом ветвления.

Когда входные данные отсортированы, все вставки находятся на крайнем правом краю дерева, и, в частности, каждый раз, когда узел разделяется, мы гарантируем, что в левой половине больше не будет вставок. При массовой загрузке мы пользуемся этим, и вместо того, чтобы равномерно разделять переполненные узлы, разделяем их как можно неравномернее: оставляем левый узел полностью заполненным и создаем правый узел с нулевыми ключами и одним дочерним (в нарушение обычного B-правила дерева).

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

Поиск по этому блогу

Alex tools