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

       

B-деревья, оптимизированные для записи


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

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

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

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



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