Індексування
Індекс є засобом прискорення пошуку записів в таблиці, а також інших операцій, що використовують пошук: витягання, модифікацію, сортування і т.д. Таблицю, для якої використовують індекс, називають індексованою. Індекс містить відсортовану по колонці або декільком колонкам інформацію і указує на рядки, в яких зберігається конкретне значення колонки. Індекс виконує роль змісту таблиць, проглядання якого передує зверненню до записів таблиці. У деяких системах індекси зберігаються в індексних файлах окремо від табличних.
Вирішення проблеми організації фізичного доступу до інформації залежить в основному від наступних чинників:
виду вмісту в полі ключа записів індексного файлу;
типу використовуваних посилань (покажчиків) на запис основної таблиці;
методу пошуку потрібних записів.
Індексний файл — це файл, що зберігається, особливого типу, в якому кожен запис складається з двох значень: дане і RID-покажчик. На практиці найчастіше використовуються два методи пошуку: послідовний і бінарний (заснований на діленні інтервалу пошуку навпіл).
Пошук необхідних записів при індексації може відбуватися по однорівневій або дворівневій схемі індексації. При однорівневій схемі в індексному файлі зберігаються короткі записи, два поля, що мають: поле вмісту старшого ключа (хеш-кода ключа) блоку, що адресується, і поле адреси початку цього блоку (мал. 2.2.).
Рис.
2.2. Одноуровневая схема индексации
У кожному блоці записи розташовуються у порядку зростання значення ключа (або згортки). Старшим ключем кожного блоку є ключ його останнього запису. Якщо в індексному файлі зберігаються хеш-коды ключових полів індексованої таблиці, то алгоритм пошуку потрібного запису включає три етапи.
Утворення згортки значення ключового поля шуканого запису.
Пошук в індексному файлі запису про блок, значення першого поля якого більше одержаною згортки (це гарантує знаходження шуканою згортки в даному блоці).
Послідовний перегляд записів блоку до збігу згорток шуканого запису і запису блоку файлу. У разі колізій (декільком різним ключам може відповідати одне значення хеш-функции, тобто одна адреса) згорток шукається запис, значення ключа якої співпадає із значенням ключа шуканого запису.
Недолік однорівневої схеми — ключі (згортки) записів зберігаються разом із записами, що приводить до збільшення часу пошуку записів через велику довжину перегляду (значення даних в записах доводиться пропускати). У дворівневій схемі ключі (згортки) записів відокремлені від вмісту записів (мал. 2.3).
В даному випадку індекс основної таблиці розподілений по сукупності файлів: одному файлу головного індексу і множинаі файлів з блоками ключів.
На практиці при створенні індексу для деякої таблиці бази даних указують поле таблиці, яке вимагає індексації. Ключові поля таблиці в багатьох СУБД індексуються автоматично. Індексні файли, створювані n<J ключовим полям таблиці, називаються файлами первинних індексів.
Індекси, що створюються не для ключових полів, називаються вторинними (призначеними для користувача) індексами. Введення цих індексів не змінює фізичного розташування записів таблиці, але впливає на послідовність проглядання записів. Індексні файли, що створюються для підтримки вторинних індексів таблиці, називаються файлами вторинних індексів.
Рис. 2.3. Двухуровневая схема индексации
Деякі СУБД підтримують кластеризованные і кластеризованные хешированные індекси.
Кластеризація — приміщення в один блок записів таблиць, які з великою вірогідністю часто піддаватимуться з'єднанню.
Кластерізованний індекс — спеціальна техніка індексування, при якій дані в таблиці фізично розташовуються в індексованому порядку. Використання кластеризованного індексу значно прискорює виконання запитів по індексованій колонці. Для кожної таблиці може існувати тільки один кластеризованный індекс. При створенні кластеризованного індексу не по первинному ключу автоматично знімається кластеризація по первинному ключу.
Хешування — альтернативний спосіб зберігання даних в наперед заданому порядку з ланцюгом прискорення пошуку (прямий доступ). Хешування позбавляє від необхідності підтримувати і проглядати індекси. Кластерізованний хеширо-ванний індекс значно прискорює операції пошуку і сортування, але додавання і видалення рядків сповільнюється із-за необхідності реорганізації даних для відповідності індексу. Хешування застосовується у тому випадку, коли необхідний прямий доступ (без індексів), наприклад при бронюванні авіаквитків, місць в готелях, прокаті машин, а також електронних грошових переказах. Проте недоліком хешування є необхідність знаходження відповідної хеш-функции, необхідність виконання операції згортки (вимагає певного часу), можливі колізії (згортка різних значень може дати однаковий j хеш-код) і проміжки між записами невизначеної протяжності. При хешуванні RID-покажчик обчислюється за допомогою деякої хеш-функции і називається хеш-кодом. У полі ключа індексного файлу можна зберігати значення ' ключових полів індексованої таблиці або згортку ключа (хеш-код). Довжина хеш-кода завжди постійна і має достатньо малу величину (наприклад, 4 байти), а це істотно знижує час пошукових операцій.
Загальним недоліком індексних схем є необхідність зберігання індексів, до яких потрібно звертатися для виявлення записів.