Деревья

• Часть 1
• | 2
• | 3

Действия при удалении записи.

1. Поиск ключа удаляемой записи в дереве.
2. Если ключ найден, выполняется удаление записи в соответствующей листовой странице, иначе алгоритм закончил работу.
3. . Если после удаления сумма размера текущей страницы с размером страницы слева или справа больше n, то алгоритм закончил работу. Иначе производится перемещение данных текущей страницы соответственно в правую или левую. Освободившаяся страница заносится в список свободных страниц. Корректируется связный список листовых страниц.
4. Вносятся изменения в родительские страницы (для страниц, участвующих в удалении и/или слиянии). При этом может возникнуть потребность в слиянии родительских страниц по аналогичному принципу.
5. Если в корневой странице остался один элемент, корневая страница освобождается (стала ненужной), а новой корневой становится единственная вершина бывшего первого уровня.

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

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

1. Упреждающие расщепления, т.е. расщепления страницы не при ее переполнении, а несколько раньше, когда степень заполненности страницы достигает некоторого уровня;

2. Переливания, т.е. поддержание равновесного заполнения соседних страниц;

3. Слияния 3-в-2, т.е. порождение двух листовых страниц на основе содержимого трех соседних.