Доклад : Индексы (работа 1) 


Полнотекстовый поиск по базе:

Главная >> Доклад >> Информатика, программирование


Индексы (работа 1)




Индексы

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

Речь пойдет об алгоритмах и структурах данных, их организации и поддержке. Термин индекс далее используется строго в целях обозначения дополнительных поисковых или оптимизирующих структур. Основным языком примеров выбран язык М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/

Похожие работы:

  • Индексы Ковача и нормальные температуры кипения алкилбифенилов

    Реферат >> Химия
    ... шкале н-алканов) 217 единицам индекса Ковача в случае неполярной силиконовой ... - по сравнению с аддитивным - значение индекса Ковача, а значит и энергии межмолекулярного ... выигрыш, эквивалентный 13 единицам индекса Ковача. Аналогичное поведение свойственно ...
  • Индекс человеческого развития

    Реферат >> География
    ... среднее из этих трех индексов. 1.Индекс ожидаемой продолжительности жизни - ... из этих трех индексов. Альтернативным индексом является Индекс бедности - служит ... человеческого потенциала в Российской Федерации". Индекс человеческого развития меньше 0,5 принято ...
  • Индекс цитирования ученого: важнейший ли это критерий качества его научной деятельности?

    Реферат >> Наука и техника
    ... оценке качества научной деятельности, где индекс цитирования ученого -неважно, с ... на искусственное раздувание личного индекса цитирования, сказанным отнюдь не ... и последователи идеи об использовании индексов цитирования работ конкретного ученого ...
  • Индексы

    Контрольная работа >> Математика
    ... Классификация экономических индексов 3. Индексы переменного и постоянного состава 4. Ценные и базисные индексы 5. Использование индексов в ... рассмотрим некоторые виды индексов. Индексы индивидуальные и общие. Агрегатный индекс Индивидуальные - характеризуют ...
  • Индексы

    Контрольная работа >> Экономико-математическое моделирование
    ... работа по статистике «Индексы» Содержание Индексы и их использование в статистике Индексы, их общая ... индексы качественных показателей. Индексы количественных показателей К индексам количественных (объемных) показателей относятся такие индексы, как индексы ...
  • Индексы и организация фондовых бирж

    Контрольная работа >> Банковское дело
    ... точности и надежности фондовых индексов. Тема фондовых индексов на сегодняшний день актуальна ... всех компаний, входящих в индекс. Индекс S&P - второй по известности ... также транспортный индекс Доу-Джонса, коммунальный индекс, композитный индекс Доу-Джонса ...
  • Индексы гигиены

    Реферат >> Медицина, здоровье
    ... расчетов используется индекс PMA, йодистый индекс, индекс десневого кармана, индекс ретракции десны. Индекс деструкции костной ... 5 уровней интенсивности кариеса зубов: Пародонтальные индексы. Индекс CPITN. Для оценки распространенности и интенсивности ...
  • Индекс развития человеческого потенциала

    Реферат >> Социология
    ... не включённые в индекс Отчёт 2007 1. Понятие и сущность индекса человеческого потенциала Индекс развития человеческого ... показателей: Индекс продолжительности жизни = Индекс образования = Индекс грамотности взрослого населения (ALI) = Индекс совокупной доли ...
  • Индекс БигМака

    Реферат >> Международные отношения
    ... Суть и история индекса БигМака Индекс БигМака в 2008г. Индекс БигМака за 2009г. Индекс БигМака за ... индекса БигМака Конкурент индекса БигМака – индекс iPod Список используемых источников Суть и история индекса БигМака Индекс ...
  • Индекс развития человеческого потенциала

    Реферат >> Социология
    ... , включающая: коэффициент дифференциации индекса развития человеческого потенциала, характеризующий ... или регионах. Альтернативным индексом является Индекс бедности (разработан ООН ... место в списке с индексом ИРЧП = 0,806. Индекс стал падать с началом ...