Індекси

Євген Каратаєв

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