Меню
  Список тем
  Поиск
Полезная информация
  Краткие содержания
  Словари и энциклопедии
  Классическая литература
Заказ книг и дисков по обучению
  Учебники, словари (labirint.ru)
  Учебная литература (Читай-город.ru)
  Учебная литература (book24.ru)
  Учебная литература (Буквоед.ru)
  Технические и естественные науки (labirint.ru)
  Технические и естественные науки (Читай-город.ru)
  Общественные и гуманитарные науки (labirint.ru)
  Общественные и гуманитарные науки (Читай-город.ru)
  Медицина (labirint.ru)
  Медицина (Читай-город.ru)
  Иностранные языки (labirint.ru)
  Иностранные языки (Читай-город.ru)
  Иностранные языки (Буквоед.ru)
  Искусство. Культура (labirint.ru)
  Искусство. Культура (Читай-город.ru)
  Экономика. Бизнес. Право (labirint.ru)
  Экономика. Бизнес. Право (Читай-город.ru)
  Экономика. Бизнес. Право (book24.ru)
  Экономика. Бизнес. Право (Буквоед.ru)
  Эзотерика и религия (labirint.ru)
  Эзотерика и религия (Читай-город.ru)
  Наука, увлечения, домоводство (book24.ru)
  Наука, увлечения, домоводство (Буквоед.ru)
  Для дома, увлечения (labirint.ru)
  Для дома, увлечения (Читай-город.ru)
  Для детей (labirint.ru)
  Для детей (Читай-город.ru)
  Для детей (book24.ru)
  Компакт-диски (labirint.ru)
  Художественная литература (labirint.ru)
  Художественная литература (Читай-город.ru)
  Художественная литература (Book24.ru)
  Художественная литература (Буквоед)
Реклама
Разное
  Отправить сообщение администрации сайта
  Соглашение на обработку персональных данных
Другие наши сайты
Приглашаем посетить
  Маркетплейс (market.find-info.ru)

   

Индексы

Индексы

Евгений Каратаев

Речь пойдет об алгоритмах и структурах данных, их организации и поддержке. Термин индекс далее используется строго в целях обозначения дополнительных поисковых или оптимизирующих структур. Основным языком примеров выбран язык МUMPS. По возможности применяется страндартный синтаксис, в некоторых исключительных случаях для большей читаемости применяются Cache Object Script - расширения. Их применение ограничено и допускает альтернативную замену на эквивалентные выражения в иных диалектах МUMPS.

Индексы - это структуры данных, размещаемые параллельно и поддерживаемые синхронно основным структурам данных и имеющие основным назначением поддержание структур данных, ориентированных на ускорение поиска или оптимизацию хранения основных данных. Здесь под основными данными понимаются данные, хранение и работа с которыми является основным назначением системы базы данных.

При использовании основных данных система базы данных выполняет операции вставки, поиска, удаление и изменения в массиве основных данных. При использовании дополнительных индексных структур система параллельно обновляет индексные структуры при изменении (вставке, изменении и удалении) основных данных и в некоторых случаях получает возможность использовать индексные структуры, ориентированные на поиск данных. Наличие такой возможности определяется характеристиками индекса.

Как следует из вышеприведенного, введение индексов в систему базы данных утяжеляет операции связанные с изменением данных но ускоряет операции связанные с поиском и, как обычно, следствие этого, выборкой данных.

Индексные структуры сами по себе обычно не являются необходимыми для работы системы базы данных. И их применение определяется программистом или администратором системы.

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

Обобщенный механизм поддержки индекса.

Индексная структура по своему состоянию должна соответствовать состоянию индексируемых данных. Поэтому операции обновления индексов обычно делят на две группы - динамическое обновление индексных структур при обновлении одной записи и массовые операции удаления / построения индексов.

Далее будем рассматривать строки данных, устроенные для простоты следующим образом:

идентификатор записи получаем инкрементом ноду ^Data

значение записи хранится в узле ^Data(id)

запись состоит из полей с разделителем ~ (тильда)

индексные записи храним с глобале ^Index

общее строение записи: ^Data(id)=Figure~Color~Count

Операции динамического обновления индексов могут быть встроены в виде вызова из операции обновления записи и либо предшествовать собственно сохранению основной записи, либо последовать ему, либо обрамлять. Например:

; просто сохранение объекта

SaveObject(id,ObjVal)

s ^Data(id)=ObjVal

q

SaveObject(id,ObjVal)

n OldValue

d InsertIndices(id,ObjVal)

s ^Data(id)=ObjVal

q

SaveObject(id,ObjVal)

s OldValue=$g(^Data(id))

q

; обрамление обновления индексов при сохранении

SaveObject(id,ObjVal)

i '+$g(id) s id=$i(^Data)

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)

dDeleteIndex(IndexName)

n id,ObjValue

s id="" f s id=$o(^Data(id),ObjValue) q:id="" d

. d InsertIndex(IndexName,id,ObjVal)

Q