Индексы
Индексы
Евгений Каратаев
Речь
пойдет об алгоритмах и структурах данных, их организации и поддержке. Термин
индекс далее используется строго в целях обозначения дополнительных поисковых
или оптимизирующих структур. Основным языком примеров выбран язык МUMPS. По
возможности применяется страндартный синтаксис, в некоторых исключительных
случаях для большей читаемости применяются Cache Object Script - расширения. Их
применение ограничено и допускает альтернативную замену на эквивалентные
выражения в иных диалектах МUMPS.
Индексы
- это структуры данных, размещаемые параллельно и поддерживаемые синхронно
основным структурам данных и имеющие основным назначением поддержание структур
данных, ориентированных на ускорение поиска или оптимизацию хранения основных
данных. Здесь под основными данными понимаются данные, хранение и работа с
которыми является основным назначением системы базы данных.
При
использовании основных данных система базы данных выполняет операции вставки,
поиска, удаление и изменения в массиве основных данных. При использовании
дополнительных индексных структур система параллельно обновляет индексные
структуры при изменении (вставке, изменении и удалении) основных данных и в
некоторых случаях получает возможность использовать индексные структуры,
ориентированные на поиск данных. Наличие такой возможности определяется
характеристиками индекса.
Как
следует из вышеприведенного, введение индексов в систему базы данных утяжеляет
операции связанные с изменением данных но ускоряет операции связанные с поиском
и, как обычно, следствие этого, выборкой данных.
Индексные
структуры сами по себе обычно не являются необходимыми для работы системы базы
данных. И их применение определяется программистом или администратором системы.
В
большинстве общераспространенных систем баз данных поддержка индексных структур
и их использование выполняется автоматическими средствами. В этой работе мы
будем составлять структуры и алгоритмы, которые можно использовать вне
автоматики и пользоваться всеми возможностями безотносительно ограничений
системы базы данных. Примерно как если бы по частям реализовали внутренние
механизмы большой системы, но в несколько упрощенном варианте.
Обобщенный механизм поддержки индекса.
Индексная
структура по своему состоянию должна соответствовать состоянию индексируемых
данных. Поэтому операции обновления индексов обычно делят на две группы -
динамическое обновление индексных структур при обновлении одной записи и
массовые операции удаления / построения индексов.
Далее
будем рассматривать строки данных, устроенные для простоты следующим образом:
идентификатор
записи получаем инкрементом ноду ^Data
значение
записи хранится в узле ^Data(id)
запись
состоит из полей с разделителем ~ (тильда)
индексные
записи храним с глобале ^Index
в
записи предполагаем поля - фигура, цвет, количество
общее
строение записи: ^Data(id)=Figure~Color~Count
Операции
динамического обновления индексов могут быть встроены в виде вызова из операции
обновления записи и либо предшествовать собственно сохранению основной записи,
либо последовать ему, либо обрамлять. Например:
;
просто сохранение объекта
SaveObject(id,ObjVal)
i
'+$g(id) s id=$i(^Data)
s
^Data(id)=ObjVal
q
;
обновление индексов перед сохранением
SaveObject(id,ObjVal)
n OldValue
i '+$g(id) s id=$i(^Data)
s OldValue=$g(^Data(id))
d DeleteIndices(id,OldValue)
d InsertIndices(id,ObjVal)
s
^Data(id)=ObjVal
q
;
обновление индексов после сохранения
SaveObject(id,ObjVal)
n OldValue
i '+$g(id) s id=$i(^Data)
s OldValue=$g(^Data(id))
s ^Data(id)=ObjVal
d DeleteIndices(id,OldValue)
d
InsertIndices(id,ObjVal)
q
;
обрамление обновления индексов при сохранении
SaveObject(id,ObjVal)
i '+$g(id) s id=$i(^Data)
d DeleteIndices(id,$g(^Data(id)))
s ^Data(id)=ObjVal
d InsertIndices(id,ObjVal)
q
Здесь
DeletIndices удаляет индексные записи по этому объекту, а InsertIndices их
создает. В данном случае подразумевается простой формат хранения записи - одной
строкой, которая трактуется либо как строка с разделителями либо как список.
Несмотря на то, что три метода в итоге дают одинаковый результат, между ними
есть разница в том, насколько правильно будет работать конкурентный
(одновременный для нескольких процессов) доступ к данным и индексам. В случае
хранения только данных этот вопрос практически не стоит, поскольку операция set
атомарная. В случае применения параллельных структур индексов существует момент
между состояниями, когда записи нет, но индекс есть, или индекс есть но записи
нет. Этот вопрос решается обычно с помощью применения блокировок. Операция set
нового значения записи обрамляется командами
l +^Data(id)
s ^Data(id)=ObjVal
l -^Data(id)
И
внутри функций удаления / вставки индексных записей также вставляются
обрамляющие блокировки. Наличие блокировок особенно критично в случае
исполнения кода в контексте транзакции и возможности выполнения операции
trollback.
Различие
в режиме перестроения индекса, а именно что раньше появится в базе - индексная
запись или запись с данными, позволяет построить в некотором смысле
самовосстанавливающуюся систему, которая будет иметь возможность восстановитсья
в случае сбоя при записи строки данных. Если индекс построен раньше, то при
выборке по индексу функция выборки данных может определить что индексная запись
существует но ей не соответствует строка данных. В случае применения блокировок
в операции обновления записи мы в функции выборки можем также попытаться
заблокировать эту же запись и если блокировка оказалась успешной но записи нет,
или ее состояние не соответствует индексным значениям, то значит что операция
записи самой строки данных была неуспешной и следует просто удалить индексную
запись. Механизм довольно громоздкий, но в ситуации когда из соображений
эффективности не хочется применять транзакции, может оказаться полезным. Вопрос
выбора стратегии обновления индекса при обновлении записи оставим программисту.
Операция
перестроения индекса сводится к удалению всех индексных записей и перебору всех
имеющихся записей с данными и построения индексных записей по каждой имеющейся
записи данных. Полагаем, что есть функции DeleteIndex для удаления всех
индексных записей по одному индексу. Тогда перестроение индекса может выглядеть
как
UpdateIndex(IndexName)
d DeleteIndex(IndexName)
n id,ObjValue
s id="" f s
id=$o(^Data(id),ObjValue) q:id="" d
. d InsertIndex(IndexName,id,ObjVal)
Q
Список литературы
Для
подготовки данной работы были использованы материалы с сайта http://karataev.nm.ru/