5.3. Індексні файли

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

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

5.3.1 Файли з щільним індексом

Розглянемо файли з щільним індексом . В цих файлах головна область (файл БД) вміщує послідовність записів однакової довжини, розташованих удовільному порядку, а структура індексного запису в них має наступний вигляд:

Значення ключа	Номер запису
2	1
4	2
5	3
6	4
7	5
10	6

Рис. 5.2. Структура індексного файлу за первинним ключем

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

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

Найбільш ефективним являється алгоритм бінарного пошуку ( метод рекурсивної дихотомії). Весь простір пошуку розбивається навпіл на дві рівні частини. Оскільки множина упорядкована за значенням ключа, то перевіряється значення останього ключа першої половини: чи більше воно за значення ключа, що шукаємо, якщо більше, то першу половину ділимо навпіл і повторюємо алгоритм, якщо ні, то ділимо навпіл другу частину індексного файлу і т.д. Максимальна кількість кроків пошуку вираховується за формулою:

Тn = log₂ N

Де N - число записів індексного файлу.

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

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

Тn = log₂ N_{обл.інд.} + 1,

Де N_{обл.інд} - кількість блоків для збереження індексного файла, одиниця враховує звернення до файлу БД для пошуку знайденого запису.

Приклад:

Нехай довжина запису (LZ) - 128 байт. Довжина первинного ключа (LK) - 12 байт. Кількість записів у файлі (KZ) - 100000. Розмір блока (LB) - 1024 байта. Розрахуємо розмір індексного запису. 4 байта використаємо для зберігання номеру запису, тоді довжина індексного запису буде:

LІ = LK + 4 = 12 + 4 = 16 байт.

Визначемо кількість індексних записів, що можуть зберігатись у одному блоці:

KIZB = LB/LI =1024/16= 64 інд. записа в блоці.

Визначимо необхідну кількість індексних блоків:

KIB = KZ/KZIB = 100000/64 = 1563 блока.

Накінець знайдемо максимальну кількість звернень до диску при пошуку довільного запису:

T = log₂KIB +1 = log₂1563 +1 = 12 звернень.

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

Якби індексація не проводилась, то при довільному зберіганні інформації в БД, треба було б переглянути всі блоки в яких зберігається файл (часом перегляду блоків нехтуємо, оскільки він відбувається в оперативній пам‘яті), тоді кількість звернень до диску:

KBO = KZ/(LB/LZ) = 100000 /(1024/128) = 12500

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

Кількість звернень при доповненні запису:

Тn = log₂ N_{обл.інд.} + 1 +1+1,

Складається з кількості звернень для пошуку запису плюс звернення для модифікації індексного файлу, плюс звернення для внесення даних до БД.