3.2. Індексування
Як зазначалося вище, визначення ключа для таблиці означає автоматичне сортування записів, контроль відсутності повторень значень ключових полях записів та підвищення швидкості виконання операцій пошуку в таблиці. Для реалізації цих функцій у СУБД застосовуютьіндексування.
Термін "індекс" тісно пов'язаний з поняттям "ключ", хоча між ними є і деяка відмінність.
Підіндексомрозуміють засібприскоренняоперації пошуку записів у таблиці, а отже, та інших операцій, які використовують пошук: витяг, модифікація, сортування і т. д. Таблицю, для якої використовується індекс, називаютьіндексованою.
Варіанти вирішення проблеми організації фізичного доступу до інформації в основному залежать від наступних факторів:
виду вмісту у полі ключа записів індексного файлу;
типу використовуваних посилань (покажчиків) для запису основний таблиці;
способу пошуку корисних записів.
У поліключа індексного файламожна зберігати значення ключових полів таблиці, що індексується, або згортку ключа (так званий хеш-код). Перевага зберігання хеш-коду замість значення полягає в тому, що довжина згортки незалежно від довжини вихідного значення ключового поля завжди має деяку постійну і досить малу величину (наприклад, 4 байти), що суттєво знижує час пошукових операцій. Недоліком хешування є необхідність виконання операції згортки (вимагає певного часу), а також боротьба з виникненням колізій (згортання різних значень може дати однаковий хеш-код).
На практиці найчастіше використовуютьсядва методи пошуку:послідовний і бінарний (заснований на розподілі інтервалу пошуку навпіл).
Проілюструємо організацію індексування таблиць двома схемами:однорівневий та дворівневий. При цьому приймемо ряд припущень, які зазвичай виконуються в сучасних обчислювальних системах. Нехай ОС підтримує пряму організацію даних на магнітних дисках, основні таблиці та індексні файли зберігаються у окремих файлах. Інформація файлів зберігається як сукупності блоків фіксованого розміру, наприклад цілого числа кластерів.
Мал. 3.3. Однорівнева схема індексації
У кожному блоці запису розташовуються у порядку зростання значення ключа чи згортки. Старшим ключем кожного блоку є ключ його останнього запису.
Якщо в індексному файлі зберігаються хеш-коди ключових полів індексованої таблиці, то алгоритм пошуку потрібного запису (із зазначеним ключем) у таблиці включає наступні три етапи.
Утворення згортки значення ключового поля шуканого запису.
Пошук в індексному файлі запису про блок, значення першого поля якого більше отриманої згортки (це гарантує знаходження згортки в цьому блоці).
Двохурівнева схемау ряді випадків виявляється більш раціональною, в ній ключі (згортки) записів відокремлені від вмісту записів (рис. 3.4).
Мал. 3.4. Дворівнева схема індексації
У цій схемі індекс основної таблиці розподілено за сукупністю файлів: один файл головного індексу і безліч файлів з блоками ключів.
Насправді створення індексу для деякої таблиці БД користувач вказує поле таблиці, яке вимагає індексації. Ключові поля таблиці у багатьох СУБД зазвичай індексуються автоматично. Індексні файли, створювані за ключовими полями таблиці, часто називаютьсяфайлами первинних індексів.
Зв'язок вторинного індексу з елементами бази даних може бути встановлена різними способами. Один зних - використання вторинного індексу як входу для отримання первинного ключа, яким потім з використанням первинного індексу проводиться пошук необхідних записів (рис. 3.5).
Мал. 3.5. Спосіб використання вторинних індексів
Деякими СУБД, наприклад Access, розподіл індексів на первинні та вторинні не проводиться. У цьому випадку використовуються автоматично створювані індекси та індекси, що визначаються користувачем по будь-якому з не ключових полів.
Головна причина підвищення швидкості виконання різних операцій в індексованих таблицях полягає в тому, що основна частина роботи проводиться з невеликими індексними файлами, а не самими таблицями. Найбільший ефект підвищення продуктивність роботи з індексованими таблицями досягається для значних за обсягом таблиць. Індексування вимагає невеликого додаткового місця на диску та незначних витрат процесора на зміну індексів у процесі роботи. Індекси можуть змінюватися перед виконанням запитів до БД, після виконання запитів до БД, за спеціальними командами користувача або програмними викликами додатків.