Ѕаза знаний студента. –еферат, курсова€, контрольна€, диплом на заказ

курсовые,контрольные,дипломы,рефераты

»ндексы — »нформатика, программирование

≈вгений  аратаев

–ечь пойдет об алгоритмах и структурах данных, их организации и поддержке. “ермин индекс далее используетс€ строго в цел€х обозначени€ дополнительных поисковых или оптимизирующих структур. ќсновным €зыком примеров выбран €зык ћ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/

≈вгений  аратаев –ечь пойдет об алгоритмах и структурах данных, их организации и поддержке. “ермин индекс далее используетс€ строго в цел€х обозначени€ дополнительных поисковых или оптимизирующих структур. ќсновным €зыком примеров выбран €зык ћ

 

 

 

¬нимание! ѕредставленный ƒоклад находитс€ в открытом доступе в сети »нтернет, и уже неоднократно сдавалс€, возможно, даже в твоем учебном заведении.
—оветуем не рисковать. ”знай, сколько стоит абсолютно уникальный ƒоклад по твоей теме:

Ќовости образовани€ и науки

«аказать уникальную работу

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

»нтерфейсы как решение проблем множественного наследовани€
ѕерспективные архитектуры генетического поиска
ћикроконтент: как писать заголовки, заглави€ страниц и темы в почтовых сообщени€х
ѕоиск подстроки в строке с помощью хеш-функции
¬ласть народу - относительные размеры шрифтов
CSS дизайн: с учетом контекста
ѕоиск того, чего нет
–абота с инифайлами (ini)
јутсорсинг тестировани€ Ч точим чужое оружие
»нструменты необходимые дл€ тестировани€ Linux

—вои сданные студенческие работы

присылайте нам на e-mail

Client@Stud-Baza.ru