Термин индекс здесь и далее используется строго в целях обозначения дополнительных
поисковых или оптимизирующих структур. Основным языком примеров выбрано
стандартное подмножество языка МUMPS. Но, хотя по возможности применяется
страндартный синтаксис, в некоторых
исключительных случаях для большей читаемости применяются Cache Object Script и
MiniM Database Server - расширения. Их применение ограничено и допускает
альтернативную замену на эквивалентные выражения в иных диалектах МUMPS.
Применение битмап индексов ограничено теми MUMPS системами, которые поддерживают
расширенные $BIT функции.
Общие принципы
Индексы - это структуры данных, размещаемые параллельно и поддерживаемые синхронно основным структурам данных и имеющие основным назначением поддержание структур данных, ориентированных на ускорение поиска или оптимизацию хранения основных данных. Здесь под основными данными понимаются данные, хранение и работа с которыми является основным назначением системы базы данных.
При использовании основных данных система базы данных выполняет операции вставки, поиска, удаления и изменения в общем массиве их хранения. При использовании дополнительных индексных структур система параллельно обновляет индексные структуры при изменении (вставке, изменении и удалении) основных данных и в некоторых случаях получает возможность использовать индексные структуры, ориентированные на поиск данных. Наличие такой возможности определяется характеристиками и структурой индекса.
Как следует из вышеприведенного, введение индексов в систему базы данных утяжеляет операции, связанные с изменением данных, но ускоряет операции связанные с поиском и, как обычно, в следствии этого, с выборкой данных.
Индексные структуры сами по себе обычно не являются необходимыми для основной работы системы базы данных. И их применение определяется программистом или администратором системы.
В большинстве общераспространенных систем баз данных поддержка индексных структур и их использование выполняется автоматическими средствами. В этой главе мы будем составлять структуры и алгоритмы, которые можно использовать вне автоматики и пользоваться всеми возможностями безотносительно ограничений системы базы данных. Примерно как если бы по частям реализовали внутренние механизмы большой системы, но в несколько упрощенном варианте.
Механизм поддержки индекса
Индексная структура по своему состоянию должна соответствовать состоянию индексируемых данных. Поэтому операции обновления индексов обычно делят на две группы - динамическое обновление индексных структур при обновлении одной записи и массовые операции удаления / построения индексов.
Далее будем рассматривать строки данных, устроенные для простоты следующим образом:
Например:
Несмотря на то, что три метода в итоге дают одинаковый результат, между ними есть разница в том, насколько правильно будет работать конкурентный (одновременный для нескольких процессов) доступ к данным и индексам. В случае хранения только данных этот вопрос практически не стоит, поскольку операция set атомарная в том смысле, что в операции выполняется только одно изменение в глобалах. В случае же применения параллельных структур индексов существует момент между состояниями, когда записи нет, но индекс есть, или наоборот, индекс есть но записи нет. Этот вопрос решается обычно с помощью применения блокировок. Операция set нового значения записи обрамляется командами
Различие в режиме перестроения индекса, а именно что раньше появится в базе - индексная запись или запись с данными, позволяет построить в некотором смысле самовосстанавливающуюся систему, которая будет иметь возможность восстановиться в случае сбоя при записи строки данных. Если индекс построен раньше, то при выборке по индексу функция выборки данных может определить, что индексная запись существует, но ей не соответствует строка данных.
В случае применения блокировок в операции обновления записи мы в функции выборки можем также попытаться заблокировать эту же запись и, если блокировка оказалась успешной, но записи нет, или ее состояние не соответствует индексным значениям, то значит что операция записи самой строки данных была неуспешной и следует просто удалить индексную запись. Механизм довольно громоздкий, но в ситуации, когда из соображений эффективности не хочется применять транзакции, может оказаться полезным. Вопрос выбора стратегии обновления индекса при обновлении записи оставим программисту.
Операция перестроения индекса сводится к удалению всех индексных записей и перебору всех имеющихся записей с данными и построения индексных записей по каждой имеющейся записи данных. Полагаем, что есть функции DeleteIndex для удаления всех индексных записей по одному индексу. Тогда перестроение индекса может выглядеть как
Общие принципы
Индексы - это структуры данных, размещаемые параллельно и поддерживаемые синхронно основным структурам данных и имеющие основным назначением поддержание структур данных, ориентированных на ускорение поиска или оптимизацию хранения основных данных. Здесь под основными данными понимаются данные, хранение и работа с которыми является основным назначением системы базы данных.
При использовании основных данных система базы данных выполняет операции вставки, поиска, удаления и изменения в общем массиве их хранения. При использовании дополнительных индексных структур система параллельно обновляет индексные структуры при изменении (вставке, изменении и удалении) основных данных и в некоторых случаях получает возможность использовать индексные структуры, ориентированные на поиск данных. Наличие такой возможности определяется характеристиками и структурой индекса.
Как следует из вышеприведенного, введение индексов в систему базы данных утяжеляет операции, связанные с изменением данных, но ускоряет операции связанные с поиском и, как обычно, в следствии этого, с выборкой данных.
Индексные структуры сами по себе обычно не являются необходимыми для основной работы системы базы данных. И их применение определяется программистом или администратором системы.
В большинстве общераспространенных систем баз данных поддержка индексных структур и их использование выполняется автоматическими средствами. В этой главе мы будем составлять структуры и алгоритмы, которые можно использовать вне автоматики и пользоваться всеми возможностями безотносительно ограничений системы базы данных. Примерно как если бы по частям реализовали внутренние механизмы большой системы, но в несколько упрощенном варианте.
Механизм поддержки индекса
Индексная структура по своему состоянию должна соответствовать состоянию индексируемых данных. Поэтому операции обновления индексов обычно делят на две группы - динамическое обновление индексных структур при обновлении одной записи и массовые операции удаления / построения индексов.
Далее будем рассматривать строки данных, устроенные для простоты следующим образом:
- Идентификатор записи получаем инкрементом узла ^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Подробнее о книге "MUMPS СУБД"
Комментариев нет:
Отправить комментарий