Евгений Каратаев
Речь пойдет об алгоритмах и структурах данных, их организации и поддержке. Термин индекс далее используется строго в целях обозначения дополнительных поисковых или оптимизирующих структур. Основным языком примеров выбран язык М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)
dDeleteIndex(IndexName)
n id,ObjValue
s id="" f s id=$o(^Data(id),ObjValue) q:id="" d
. d InsertIndex(IndexName,id,ObjVal)
Q
Другие работы по теме:
Индексы
Индексы и их использование в статистике. Общая характеристика и сфера их применения. Индексы количественных показателей: физического объема производства продукции, затрат на выпуск продукции и ее стоимость. Факторный анализ и методы его применения.
Статистический расчет показателей фондовооруженности
Определение показателей фондоемкости и фондоотдачи, базисных и среднегодовых темпов роста, характеризующих использование основных фондов. Расчет изменения объема продукции за счет прироста производственных фондов, показателей фондовооруженности труда.
Экономические индексы и индексный метод
Индекс — это обобщающий относительный показатель, характеризующий изменение уровня общественного явления во времени, по сравнению с программой развития, планом, прогнозом или его соотношение в пространстве.
Методика построения уравнения регрессии и корреляции
Контрольная работа №2 Задача №1 Для изучения связи между активами-нетто и объемом капитала по 30 коммерческим банкам (согласно Вашему варианту): а) изобразите связь между изучаемыми признаками графически построением поля корреляции;
Вычисление индексов динамики
ЗАДАЧА Коммерческая фирма занимается рекламной деятельностью наименование январь февраль абсолют отклон цена стоим цена стоим цена стоим каталоги
Вычисление индексов динамики
Решение задач на вычисление индивидуальных индексов и общих индексов цен, объема продукции, товарооборота в фактических ценах. Динамика объема производства и исчисление индексов физического объема промышленной продукции. Динамика натуральных показателей.
Методика построения уравнения регрессии и корреляции
Методика построения графика зависимости между величиной капитала и чистыми активами банков, определение уравнения регрессии зависимости чистых активов и капитала коммерческих банков. Вычисление показателей тесноты связи между изучаемыми признаками.
Фондовые индексы
Фондовые индексы давно стали привычными индикаторами состояния экономики. Они постоянно упоминаются на страницах газет и в выпусках телевизионных новостей. Узнайте самую суть об основных мировых фондовых индексах, а также о методах их расчетов.
Виды и формы индексов
Определение роли индексного факторного анализа в экономических исследованиях. Изучение понятий, видов и форм агрегатных индексов выручки от продажи, цен на товары согласно методикам Ласперреса и Пааше, которые оказывают влияние на сложное явление.
Определение основных показателей деятельности предприятия
Методика и этапы группировки предприятий по объему продукции, определение среднесписочной численности сотрудников, среднегодовой стоимости ОФ, выработки продукции на одного работника. Вычисление фактического уровня производительности труда и прироста.
Расчет цепных и базисных абсолютных данных
Определение вида рядов динамики. Методы расчета цепных и базисных абсолютных приростов, темпов роста и прироста, среднего уровня ряда. Определение индивидуальных индексов себестоимости по видам продукции, агрегатных индексов товарооборота и реализации.
Расчет объема производства
Вычисление объема производства в целом и в среднем за год в натуральных единицах, величины средней себестоимости продукции за период. Абсолютный прирост, темпы роста и прироста объема производства - базисные и цепные. Индивидуальные базисные индексы.
Определение стоимости основных фондов
Определение средней стоимости основных фондов по данным вариационного ряда. Построение кумуляты распределения предприятий по величине стоимости основных фондов. Расчет индексов цен по каждому виду товаров. Определение значений изменения товарооборота.
Расчет объема производства
Расчетно-графическая работа по дисциплине "Статистика" Вычислить объем производства в целом за 4 года и в среднем за год в натуральных единицах.
Расчет цепных и базисных абсолютных данных
Задание № 1 Условно принять, что первые пять показателей из столбца представляют собой уровни ряда динамики. Дать наименование этим уровням. Определить вид ряда динамики. Для полученного ряда рассчитать цепные и базисные абсолютные приросты, темпы роста, темпы прироста, средний уровень ряда, средний темп роста, средний тем прироста.
Социально-экономическая статистика
Статистические задачи на определение механического прироста и коэффициента механического прироста населения за год, а так же коэффициента жизнеспособности, если коэффициенты смертности и механического прироста равны. Определение валового оборота фирмы.
Кристаллографические символы
Система обозначения граней и направлений. Индексы граней и ребер кристаллов. Символы ребер. Основные кристаллографические соотношения. Углы между двумя направлениями, между направлением и плоскостью. Межплоскостное расстояние и индексы плоскости.
Распределение грузоперевозок
1. Формулировка задачи и исходные данные Имеется 5 поставщиков (отправителей) груза и 10получателей (потребителей) груза, с известным количеством груза у каждого из поставщиков и потребности в нём каждого получателя (Таблица 1.1 и 1.2). Определены также расстояния между ними (Таблица 1.3).
Обозначения и определения тензорной алгебры
Особенности системы индексных обозначений. Специфика суммирования в тензорной алгебре. Главные операции в алгебре, которые называются сложением, умножением и свертыванием. Применение операции внутреннего умножения. Симметричные и антисимметричные объекты.
Индексы
Понятие об индексах и их роль в экономических исследованиях. Метод экономических индексов и их классификация по группировочным признакам. Индексы переменного и постоянного состава, ценные и базисные. Использование в макроэкономических исследованиях.
Общие индексы количественных и качественных показателей
Статистика 29 Общие индексы количественных и качественных показателей Индекс – это результат сравнения двух одноименных показателей, при исчислении которого следует различать числитель индексного отношения (сравниваемый или отчетный уровень) и знаменатель индексного отношения (базисный уровень, с которым производится сравнение).
Задачи по Статистике 7
Задачи и их решения по предмету Статистика Задача № 1 Имеются следующие данные о товарообороте по 20 магазинам продовольственных товаров (тыс. руб.): 2200, 3000, 1000, 2000, 4000, 3300, 2500, 2320, 1500, 2100, 2700, 1900, 2300, 3200, 3800, 2900, 2400, 3500, 2380, 2600. Постройте интервальный ряд распределения торговых предприятий по товарообороту, образовав, 5 групп с равными интервалами.
Цепные и базисные индексы
МОСКОВСКИЙ СОЦИАЛЬНО – ЭКОНОМИЧЕСКИЙ ИНСТИТУТ ПЕНЗЕНСКОЕ ПРЕДСТАВИТЕЛЬСТВО Специальность 080109.65 «Бухгалтерский учет, анализ и аудит» Реферат
Индексы NASDAQ
Введение 1 NASDAQ Composite 2 NASDAQ-100 3 NASDAQ Biotechnology Index Список литературы Введение NASDAQ (National Association of Securities Dealers Automated Quotation, читается как «Насдак») — фондовая биржа, специализирующаяся на акциях высокотехнологичных компаний (производство электроники, программного обеспечения и т. п.) является одной из трех основных фондовых бирж США вместе с NYSE и AMEX.
Лидирующие индикаторы
Департамент Торговли правительства США использует 10 индикаторов деловой активности отслеживающих различные сегменты экономики в попытке предсказать направление развития экономики США в ближайшем будущем. В принципе, экономических индикаторов огромное количество, однако, считается, что подавляющее их большинство не обладает предсказательной способностью.
Чикагская товарная биржа
Введение 1 История биржи Список литературы Введение Чикагская товарная биржа (англ. Chicago Mercantile Exchange) — одна из крупнейших и наиболее диверсифицированная товарно-сырьевая биржа мира. Располагается в Чикаго, США.
Факторный индексный анализ. Методика и проблемы
Понятие экономических индексов. Классификация индексов. Индексный метод в анализе хозяйственной деятельности. Индексный метод определения влияния факторов на обобщающий показатель. Важнейшие экономические индексы и их взаимосвязи.
Биржевые индексы 2
Биржевые индексы. Понятие «биржевой индекс». Российские фондовые индексы. Индексы – это укрупненные показатели (индикаторы), отражающие состояние и основные тенденции развития рынка акций и облигаций, а также производных ЦБ.