Алгоритмы в B-деревьях
Поиск
Поиск похож на поиск в двоичном дереве поиска. Начиная с корня, дерево рекурсивно перемещается сверху вниз. На каждом уровне поиск сокращает свое поле зрения до дочернего указателя (поддерева), диапазон которого включает значение поиска. Диапазон поддерева определяется значениями или ключами, содержащимися в его родительском узле. Эти предельные значения также известны как значения разделения.
Бинарный поиск обычно (но не обязательно) используется в узлах, чтобы найти значения разделения и интересующее дочернее дерево.
Вставка
Все вставки начинаются с конечного узла. Чтобы вставить новый элемент, выполните поиск в дереве, чтобы найти листовой узел, в который должен быть добавлен новый элемент. Вставьте новый элемент в этот узел, выполнив следующие действия:
- Если узел содержит меньше максимально допустимого количества элементов, тогда есть место для нового элемента. Вставьте новый элемент в узел, сохраняя элементы узла в порядке.
- В противном случае узел заполнен, равномерно разделите его на два узла так:
- Одна медиана выбирается из элементов листа и нового элемента.
- Значения, меньшие, чем медиана, помещаются в новый левый узел, а значения, превышающие медиану, помещаются в новый правый узел, причем медиана выступает в качестве значения разделения.
- Значение разделения вставляется в родительский узел, что может привести к его разделению и так далее. Если у узла нет родителя (то есть узел был корнем), создайте новый корень над этим узлом (увеличив высоту дерева).
Если расщепление проходит до самого корня, оно создает новый корень с одним значением разделителя и двумя дочерними элементами, поэтому нижняя граница размера внутренних узлов не применяется к корню. Максимальное количество элементов на узел - 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-дерева.
- Найдите и удалите элемент, затем реструктурируйте дерево, чтобы сохранить его инварианты, ИЛИ
- Сделайте один проход вниз по дереву, но перед входом (посещением) узла реструктурируйте дерево так, чтобы после обнаружения удаляемого ключа его можно было удалить, не вызывая необходимости какой-либо дальнейшей реструктуризации
Алгоритм ниже использует предыдущую стратегию.
При удалении элемента необходимо учитывать два особых случая:
- Элемент во внутреннем узле является разделителем для его дочерних узлов
- Удаление элемента может поставить его узел под минимальное количество элементов и дочерних элементов
Процедуры для этих случаев в порядке ниже.
Удаление из листового узла
- Найдите значение для удаления.
- Если значение находится в листовом узле, просто удалите его из узла.
- Если происходит недостаточное заполнение, выполните повторную балансировку дерева, как описано в разделе "Перебалансировка после удаления" ниже.
Удаление с внутреннего узла
Каждый элемент во внутреннем узле действует как значение разделения для двух поддеревьев, поэтому нам нужно найти замену для разделения. Обратите внимание, что самый большой элемент в левом поддереве все еще меньше разделителя. Аналогично, самый маленький элемент в правом поддереве все еще больше, чем разделитель. Оба эти элемента находятся в конечных узлах, и любой из них может быть новым разделителем для двух поддеревьев. Алгоритмически описано ниже:
- Выберите новый разделитель (либо самый большой элемент в левом поддереве, либо самый маленький элемент в правом поддереве), удалите его из конечного узла, в котором он находится, и замените удаляемый элемент новым разделителем.
- Предыдущий шаг удалил элемент (новый разделитель) из конечного узла. Если этот конечный узел в настоящее время имеет недостаток (имеет меньше необходимого количества узлов), то выполните балансировку дерева, начиная с конечного узла.
Перебалансировка после удаления
Восстановление баланса начинается с листа и продолжается до корня, пока дерево не уравновесится. Если удаление элемента из узла привело к его минимальному размеру, то некоторые элементы должны быть перераспределены, чтобы привести все узлы к минимуму. Обычно перераспределение включает в себя перемещение элемента с одноуровневого узла, у которого больше минимального количества узлов. Эта операция перераспределения называется ротацией. Если ни один из братьев не может сэкономить элемент, то дефектный узел должен быть объединен с родным братом. В результате слияния родительский элемент теряет элемент-разделитель, поэтому родительский элемент может стать неполноценным и потребовать перебалансировки. Слияние и ребалансировка могут продолжаться вплоть до самого корня. Поскольку минимальное количество элементов не относится к корню, сделать корень единственным дефектным узлом не проблема. Алгоритм перебалансировки дерева выглядит следующим образом:
-
Если правый брат дефектного узла существует и имеет больше, чем минимальное количество элементов, поверните влево
- Скопируйте разделитель из родительского в конец дефектного узла (разделитель перемещается вниз; дефектный узел теперь имеет минимальное количество элементов)
- Замените разделитель в родительском элементе первым элементом правого родного брата (правый родной брат теряет один узел, но все еще имеет хотя бы минимальное количество элементов)
- Дерево теперь сбалансировано
-
В противном случае, если левый брат дефектного узла существует и имеет больше, чем минимальное количество элементов, поверните вправо
- Скопируйте разделитель из родительского в начало дефектного узла (разделитель перемещается вниз; дефектный узел теперь имеет минимальное количество элементов)
- Замените разделитель в родительском элементе с последним элементом левого родного брата (левый родной брат теряет один узел, но все еще имеет по крайней мере минимальное количество элементов)
- Дерево теперь сбалансировано
-
В противном случае, если у обоих непосредственных братьев есть только минимальное количество элементов, то объединяются с родным братом, отделяющим их разделитель от родителя.
- Скопируйте разделитель в конец левого узла (левый узел может быть дефектным узлом или это может быть брат с минимальным количеством элементов)
- Переместите все элементы от правого узла к левому узлу (теперь левый узел имеет максимальное количество элементов, а правый узел - пустой)
- Удалить разделитель из родительского элемента вместе с пустым правым дочерним элементом (родительский элемент теряет элемент)
- Если родитель является корнем и теперь не имеет элементов, то освободите его и сделайте объединенный узел новым корнем (дерево становится более мелким)
- В противном случае, если родительский элемент содержит меньше необходимого количества элементов, перебалансируйте родительский элемент.
Примечание: операции перебалансировки различаются для B+ деревьев (например, ротация отличается, потому что у родителя есть копия ключа) и B* деревьев (например, три родных брата объединяются в два родных брата).
Последовательный доступ
Хотя недавно загруженные базы данных имеют тенденцию к хорошему последовательному поведению, это поведение становится все труднее поддерживать по мере роста базы данных, что приводит к более случайным операциям ввода-вывода и проблемам с производительностью.
Начальная конструкция
Распространенным частным случаем является добавление большого количества предварительно отсортированных данных в изначально пустое B-дерево. Хотя вполне возможно просто выполнить серию последовательных вставок, вставка отсортированных данных приводит к тому, что дерево почти полностью состоит из наполовину заполненных узлов. Вместо этого можно использовать специальный алгоритм "массовой загрузки" для создания более эффективного дерева с более высоким коэффициентом ветвления.
Когда входные данные отсортированы, все вставки находятся на крайнем правом краю дерева, и, в частности, каждый раз, когда узел разделяется, мы гарантируем, что в левой половине больше не будет вставок. При массовой загрузке мы пользуемся этим, и вместо того, чтобы равномерно разделять переполненные узлы, разделяем их как можно неравномернее: оставляем левый узел полностью заполненным и создаем правый узел с нулевыми ключами и одним дочерним (в нарушение обычного B-правила дерева).
В конце массовой загрузки дерево почти полностью состоит из полностью заполненных узлов; только самый правый узел на каждом уровне может быть меньше, чем полный. Поскольку эти узлы также могут быть заполнены менее чем наполовину, для восстановления нормальных правил B-дерева объедините такие узлы с их (гарантированно заполненными) левыми братьями и сестрами и разделите ключи, чтобы получить два узла, по крайней мере наполовину заполненные. Единственный узел, у которого нет полного левого родного брата - это корень, который может быть заполнен менее чем наполовину.
Читайте также:
Комментарии
Отправить комментарий