Індекси - інформатика, програмування

Йтиметься про алгоритми і структури даних, їх організації та підтримки. Термін індекс далі використовується строго в цілях позначення додаткових пошукових або оптимізують структур. Основною мовою прикладів вибрана мова МUMPS. По можливості застосовується Страндартное синтаксис, в деяких виняткових випадках для більшої Новомосковскемості застосовуються Cache Object Script - розширення. Їх застосування обмежене і допускає альтернативну заміну на еквівалентні вирази в інших діалектах МUMPS.

Індекси - це структури даних, що розміщуються паралельно і підтримувані синхронно основним структурам даних і мають основним призначенням підтримку структур даних, орієнтованих на прискорення пошуку або оптимізацію зберігання основних даних. Тут під основними даними розуміються дані, зберігання і робота з якими є основним призначенням системи бази даних.

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

Як випливає з вищенаведеного, введення індексів в систему бази даних ускладнює операції пов'язані зі зміною даних але прискорює операції пов'язані з пошуком і, як зазвичай, наслідок цього, вибіркою даних.

Індексні структури самі по собі зазвичай не є необхідними для роботи системи бази даних. І їх застосування визначається програмістом або адміністратором системи.

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

Узагальнений механізм підтримки індексу.

Індексна структура за своїм станом має відповідати стану індексованих даних. Тому операції оновлення індексів зазвичай ділять на дві групи - динамічне оновлення індексних структур при оновленні запису і масові операції видалення / побудови індексів.

Далі будемо розглядати рядки даних, влаштовані для простоти наступним чином:

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

значення запису зберігається у вузлі ^ Data (id)

запис складається з полів з роздільником

індексні записи зберігаємо з глобальний ^ Index

в запису припускаємо поля - фігура, колір, кількість

загальна будова записи: ^ Data (id) = Figure

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

; просто збереження об'єкта

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

; оновлення індексів перед збереженням

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

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

Тут DeletIndices видаляє індексні записи по цьому об'єкту, а InsertIndices їх створює. В даному випадку мається на увазі простий формат зберігання записи - одним рядком, яка трактується або як рядок з роздільниками або як список. Незважаючи на те, що три методу в результаті дають однаковий результат, між ними є різниця в тому, наскільки правильно буде працювати конкурентний (одночасний для кількох процесів) доступ до даних і індексам. У разі зберігання тільки даних це питання практично не варто, оскільки операція set атомарна. У разі застосування паралельних структур індексів існує момент між станами, коли записи немає, але індекс є, або індекс є але записи немає. Це питання вирішується зазвичай за допомогою застосування блокувань. Операція set нового значення запису обрамляється командами

І всередині функцій видалення / вставки індексних записів також вставляються обрамляють блокування. Наявність блокувань особливо критично в разі виконання коду в контексті транзакції і можливості виконання операції trollback.

Різниця в режимі перестроювання індексу, а саме що раніше з'явиться в базі - індексна запис або запис з даними, дозволяє побудувати в деякому сенсі самовідновлюється систему, яка буде мати можливість восстановітсья в разі збою під час запису рядка даних. Якщо індекс побудований раніше, то при вибірці за індексом функція вибірки даних може визначити що індексна запис існує але їй не відповідає рядок даних. У разі застосування блокувань в операції поновлення запису ми в функції вибірки можемо також спробувати заблокувати цю ж запис і якщо блокування виявилася успішною але записи немає, або її стан не відповідає індексним значенням, то значить що операція запису самої рядки даних була неуспішною і слід просто видалити індексний запис. Механізм досить громіздкий, але в ситуації коли з міркувань ефективності не хочеться застосовувати транзакції, може виявитися корисним. Питання вибору стратегії оновлення індексу при оновленні запису залишимо програмісту.

Операція перестроювання індексу зводиться до видалення всіх індексних записів і перебору всіх наявних записів з даними і побудови індексних записів по кожній наявної записи даних. Вважаємо, що є функції DeleteIndex для видалення всіх індексних записів по одному індексу. Тоді перестроювання індексу може виглядати як

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