Індексно-послідовні файли

Типи індексів

Для прискорення доступу до даних застосовується декілька типів індексів.

Головні з них перелічені нижче.

1. Первинний індекс - файл даних послідовно підпорядковується за полем ключа підпорядкування, а на основі поля ключа підпорядкування створюється поле індексації, яке гарантовано має унікальне значення в кожному з записів.

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

3. Вторинний індекс - індекс, який визначений на полі файлу даних, відмінному від поля, за яким виконується підпорядкування.

Файл може мати не більш одного первинного індексу або одного індексу кластеризації, але додатково до них може мати декілька вторинних індексів. Індекс може бути разреженним (sparse) або плотним (dense). Разреженний індекс містить індексні записи лише для деяких значень ключа пошуку в даному файлі, а плотний індекс має індексні записи для всіх значень ключа пошуку в даному файлі. Ключ пошуку для індексу може складатися з декількох полів.

Відсортований файл даних з первинним індексом називається індексованим послідовним файлом, або індексно-послідовним файлом. Ця структура є компромісом поміж файлами з повністю послідовною та повністю довільною організацією. В такому файлі записи можуть опрацьовуватися як послідовно, так й вибірково, з довільним доступом, який здійснюється на основі пошуку за заданим значенням ключа з використанням індексу. Індексований послідовний файл має більш універсальну структуру, яка звичайно включає наступні компоненти:

· первинна область зберігання;

· окремий індекс або декілька індексів;

· область переповнення.

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

Головним недоліком використання первинного індексу є необхідність дотримання послідовності сортування при додаванні та знищенні записів. Ці проблеми ускладнюються тим, що вимагається дотримання порядку сортування як в файлі даних, так й в індексному файлі. В схожому випадку може використовуватися метод, який міститься в застосуванні області переповнення та ланцюжка пов’язаних вказівників, аналогічно методу, який використовується для вирішення конфліктів в хешированих файлах.

Дата добавления: 2014-01-04