Гоц Грейф (Goetz Graefe)

Индексы на основе B-деревьев для поддержки высокого темпа обновлений

Источник: Море(!)аналитической информации ! ::
CITFORUM.RU, 2006
http://citforum.ru/database/articles/b-tree_indexes/
Перевод: Сергей Кузнецов
Оригинал: B-tree indexes for high update rates
( http://www.sigmod.org/sigmod/record/issues/0603/p39-article-graefe.pdf),
SIGMOD Record, Vol. 35, No. 1, Mar. 2006

Предисловие переводчика

Статья Грейфа привлекла меня тем, что уже давно не попадались обзоры, посвященные алгоритмам работы с B-деревьями. Должен сразу сказать, что во многом статья не оправдала мои ожидания: многие, по-видимому, интересные методы и структуры данных описаны слишком кратко и сумбурно, очень не хватает иллюстраций. Во время перевода мне постоянно хотелось исправить недостатки статьи, благо, что большая часть источников, упоминаемых в списке литературы, свободно доступна в Internet. Однако я сдержал себя и представляю вам чистый перевод статьи. В целом он дает представление о существующих подходах, а с подробностями вы можете при желании ознакомиться сами, воспользовавшись списком литературы и поставленными мной ссылками на публикации в Web.

Аннотация

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

Для этих приложений хорошим вариантом являются индексы на основе B-деревьев, если принять некоторые компромиссные решения, направленные на оптимизацию скорее операций обновления, чем запросов. В этой статье приводится обзор некоторых методов, которые за счет снижения эффективности обработки запросов позволяют B-деревьям выдерживать очень высокий темп обновлений, на несколько порядков более высокий, чем могут допустить традиционные B-деревья. Не удивительно, что некоторые из этих методов напоминают методы, используемые при создании, перестройке индексов и т.д., а другие выводятся из известных технологий, таких как дифференциальные файлы и файловые системы с журнальной структурой (log-structured file system).

Введение

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

Другой областью применения методов, обсуждаемых в этом обзоре, является индексирование непрерывных потоков данных. Достаточно хорошо понятна фильтрация потоков "на лету", но для потоков, содержащих идентификаторы объектов реального мира, часто требуется сопоставление со статическими данными, а также с другими потоками. Поэтому крайне необходима возможность сбора потоковых данных, обычно в порядке их поступления, а также их индексирования по атрибутам, отличным от времени поступления. Иногда требуется несколько индексов, поддерживающих разные порядки. Например, для обеспечения эффективного и близкого к мгновенному обнаружения случаев мошенничества в потоке данных о транзакциях с кредитными карточками может потребоваться индексирование по номеру карты, идентификационным данным клиента (клиент может потерять несколько кредитных карт в одно и то же время) и данным о продавце (нечестный служащий может мошенническим образом расплачиваться кредитными картами многих клиентов).

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

===***===***===***===

Полностью текст этой статьи находится по адресу:
http://citforum.ru/database/articles/b-tree_indexes/