Базы данных. Вводный курс


B+-деревья - часть 3


В результате потребуется вставить значение ключа и ссылку на новую страницу во внутреннюю страницу-предка выше по иерархии и т.д.

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

    При удалении записи выполняются следующие действия.

    • Поиск записи по ключу. Если запись не найдена, то удалять ничего не нужно.

    • Реальное удаление записи в буфере, в который прочитана соответствующая листовая страница.

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

    • Иначе производится слияние с правым или левым братом, т.е. в буфере производится новый образ страницы, содержащей общую информацию из данной страницы и ее левого или правого брата. Ставшая ненужной листовая страница заносится в список свободных страниц. Соответствующим образом корректируется список листовых страниц.

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

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

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

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

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

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

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

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




    - Начало -  - Назад -  - Вперед -