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