Індексно-послідовна організація файлів

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

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

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

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

Форми організації файлів, при яких використовується індексація, відрізняються способами організації індексу. Якщо індекс породжується внаслідок періодичної реорга­нізації файла і не змінюється в результаті його поточної реорганізації, то говорять про індексно-послідовний файл. При такій організації нові записи поміщаються в область переповнення і пов¢язуються зі своїми сусідами (у відповідності послідовності сортування).

Індексно-послідовні файли складаються із трьох важливих компонентів:

послідовного файлу,

області індексу

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

Виконуючи пошук запису даних по первинному ключу, спочатку знаходять номер блоку в області індексу, після чого блок може бути прочитаний. На мал. 11 демонструються основні компоненти індексно-послідовного файлу (це продовження мал. 10 попереднього роз­ділу).

Малюнок потребує деяких пояснень. Якщо необхідний доступ, наприклад, до запису з ключем МІС-83, спочатку буде встановлено, що він знаходиться у блоці з номером 11, а потім цей блок буде зчитаний з диску і потім витягнутий запис з даними. Правда, цей процес буде трохи утруднятися, якщо був запит на запис, що внесена після останньої реорганізації, а значить, знаходиться в області переповнення.

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

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

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

Поиск по сайту: