Распределенная обработка данных. Найханова Л.В. - 69 стр.

     Предельным случаем является переполнение корневой страницы B-дерева. В этом
случае она тоже расщепляется на две, и заводится новая корневая страница дерева, т.е. его
глубина увеличивается на единицу.
     При удалении записи выполняются следующие действия:
     • Поиск записи по ключу. Если запись не найдена, то значит удалять ничего не
     нужно.
     • Реальное удаление записи в буфере, в который прочитана соответствующая
     листовая страница.
     • Если после выполнения этой подоперации размер занятой в буфере области
     оказывается таковым, что его сумма с размером занятой области в листовых
     страницах, являющихся левым или правым братом данной страницы, больше, чем
     размер страницы, операция завершается.
     • Иначе производится слияние с правым или левым братом, т.е. в буфере
     производится новый образ страницы, содержащей общую информацию из данной
     страницы и ее левого или правого брата. Ставшая ненужной листовая страница
     заносится в список свободных страниц. Соответствующим образом корректируется
     список листовых страниц.
     Чтобы устранить возможность доступа от корня к освобожденной странице, нужно
удалить соответствующее значение ключа и ссылку на освобожденную страницу из
внутренней страницы - ее предка. При этом может возникнуть потребность в слиянии этой
страницы с ее левым или правыми братьями и т.д.
     Предельным случаем является полное опустошение корневой страницы дерева,
которое возможно после слияния последних двух потомков корня. В этом случае корневая
страница освобождается, а глубина дерева уменьшается на единицу.
     Как видно, при выполнении операций вставки и удаления свойство
сбалансированности B-дерева сохраняется, а внешняя память расходуется достаточно
экономно.
     Проблемой является то, что при выполнении операций модификации слишком часто
могут возникать расщепления и слияния. Чтобы добиться эффективного использования
внешней памяти с минимизацией числа расщеплений и слияний, применяются более
сложные приемы, в том числе:
      - упреждающие расщепления, т.е. расщепления страницы не при ее
          переполнении, а несколько раньше, когда степень заполненности страницы
          достигает некоторого уровня;
      - переливания, т.е. поддержание равновесного заполнения соседних страниц;
      - слияния 3-в-2, т.е. порождение двух листовых страниц на основе содержимого
          трех соседних.
     Следует заметить, что при организации мультидоступа к B-деревьям, характерного
при их использовании в СУБД, приходится решать ряд нетривиальных проблем. Конечно,
грубые решения очевидны, например монопольный захват B-дерева на все выполнение
операции модификации. Но существуют и более тонкие решения, рассмотрение которых
выходит за пределы нашего курса.
     И последнее замечание относительно B-деревьев. В литературе вид рассмотренных
нами деревьев принято называть B* или B+-деревьями.

     Хэширование

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



                                                                                       69