5.3.2 Файли з нещільним індексом (індексно-послідовні файли)

Файли з нещільним індексом використовуються тоді, коли дані в основному файлі БД фізично упорядковані. Упорядкування відбувається за первинним ключем, який і утворює індекс. Індекс утакому файлі називається кластерізованим. Кластерізований індекс може бути тільки один. Структура файла з нещільним індексом наведена на рис.

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

Значення ключа першого запису блока	Номер блока		Ключ
100	0		100
			…
			Вільне місце
200	1		200
			…
			Вільне місце
400	2		400
			…
			Вільне місце

Рис. 5.3. Індексна структура бази даних з нещільним індексом

Розрахуємо кількість звернень до зовнішнього пристрою для файлів з нещільним індексом порівняно з довільним розташуванням інформації з використанням метода дихотомії. Кількість звернень до зовнішнього пристрою з використанням метода дихотомії вираховується за формулою:

T = log₂ 12500 = 14 звернень

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

Довжина запису у індексному файлі складається з довжини ключа та номера блока і в нашому прикладі дорівнює 14.

Li = Lk + 2 = 14,

Тоді кількість індекних записів у одному блоці складає :

KIZB = Lb/Li= 1024/14 = 73 записа

Визначимо кількість блоків необхідних для збереження індексного файла:

KIB = KBO / KZIB = 12500 / 73 = 172 блока

Таким чином, кількість звернень до диску для пошуку довільного запису складає:: Tпош. = log₂ KIB +1 = log₂ 172 + 1 = 9 звернень,

Де log₂ KIB - кількість звернень до індекного файла, та одне звернення до файла БД.

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

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

T = log₂ KIB +1 +1 = 10 звернень

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