Классика баз данных - статьи

       

Буферизация в разделах B-дерева


В одной из работ, мотивируемой желанием избежать кодирования частных случаев, используется основное B-дерево как собственная буферная структура данных за счет введения разделов внутри каждого B-дерева []. За счет введения искусственного лидирующего столбца ключа сохраняется традиционная структура B-дерева. "Основное" B-дерево определяется общим значением искусственного лидирующего столбца ключа, скажем, 0 или null, а один или более буферов определяются другими значениями этого столбца, скажем, 1, 2 и т.д.

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

При выполнении запросов требуется производить поиск в каждом разделе с использованием традиционных методов, ограничивающих значения некоторых столбцов индекса, за исключением лидирующего [], которые, возможно, дополняются оптимизацией на основе того факта, что в качестве идентификаторов разделов используются последовательные целые значения. В качестве альтернативы, при выполнении запросов могут возникать некоторые слияния, выполняемые до реальной выборки данных и реализуемые с использованием системных транзакций. Таким образом, работа по поддержке B-дерева, традиционно выполняемая как часть операций обновления, перемещается в состав операций запросов или реорганизации, которая может случаться в любое время между вставкой и запросом. В крайнем случае, запрос может привести к полному слиянию и оптимизации всех разделов за исключением, может быть, одного раздела, предназначенного для текущих вставок.

Некоторые интересные аспекты таких B-деревьев состоят в том, что

  1. операция реорганизации, которая объединяет несколько разделов в один раздел, очень похожа на шаг слияния в традиционной внешней сортировке со слиянием;
  2. такие операции слияния могут выполняться как системные транзакции и фиксировать каждый раз очень небольшой диапазон ключей;
  3. такие операции слияния и реорганизации могут приостанавливаться и возобновляться в любое время, если возникают периоды пиковой нагрузки;
  4. тот же метод может способствовать выполнению массовых удалений, т.е. удаляемые элементы B-дерева перемещаются небольшими системными транзакциями в выделенный раздел, а затем удаляются в одной из быстрых пользовательских транзакций, которая вырезает из B-дерева несколько полных страниц.



Содержание раздела