Створення та обробка баз даних на ПЕОМ (стр. 14 )

Розроблено дуже велика кількість засобів для подолання цієї проблеми. Однак основним засобом забезпечення швидкого доступу до даних є індексування.

4.5. Індексування

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

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

Крім того, висока швидкість досягається завдяки тому, записи в індексному файлі завжди мають постійну довжину.

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

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

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

Значення ключа (чи його згортка)

Номер запису

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

Ефективність того чи іншого методу пошуку прийнято оцінювати максимальним часом доступу до довільного запису. Прийнято час доступу визначати не в абсолютних значеннях часу, а в кількості звертань до пристрою зовнішньої пам'яті, яким звичайно є диск. У випадку бінарного пошуку максимальна кількість звертань до диску (кроків пошуку) дорівнює:

Tпошуку = log2N,

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

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

На Рис. 4.7 показаний приклад організації файлу з щільним індексом.

Для оцінки виграшу, що дає використання щільного індексу, розглянемо такий приклад. Нехай відомі такі характеристики:

-  розмір блоку LB = 1024 байта;

-  довжина запису у файлі LZ = 256 байтів;

-  довжина первинного ключа LK = 4 байти;

-  кількість записів у файлі KZ = 100000.

Розрахуємо розмір індексного запису LI у такий спосіб. Для збереження номера запису нам буде потрібно 3 байти:

28 = 256 - 1 байт;

216 = 65536 - 2 байти;

224 = 16777216 - 3 байти.

Число 100000 можна зберігати у області пам’яти розміром не менше трьох байтів. Звичайно допускається тільки парна адресація. Тому для збереження номера запису відводимо 4 байти. З обліком цього довжина індексного запису буде дорівнювати:

LI = LK + 4 = 4 + 4 = 8 байт.

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

KIZB = 1024/8 = 128.

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

KIB = 100000/128 = 781,25 » 782 блоку.

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

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

Тпошуку = Log2KIB + 1 = Log2728 +1 » 10 + 1 = 11.

2301	7
2302	5
3024	1
4025	6
4080	3
4100	2
4830	4
5420	8
Вільний простір

	Основна область
1	3024	Іванов
2	4100	Петров
3	4080	Симонов
4	4830	Олійник
5	2302	Зикін
6	4025	Кохан
7	2301	Бондар
8	5420	Токар

Блок 1

Індексна

область

Блок 2

Блок 3

 

Рис. 4.7. Приклад організації файлу з щільним індексом

Тут ми так само округляємо результат до найближчого цілого. Одиниця додана для обліку звертання до запису в основній області.

Отже, ми визначили, що для пошуку довільного запису в даному прикладі при застосуванні щільного індексу буде потрібно не більш 11 звертань до диска.

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

Кількість блоків основної області, необхідних для збереження всіх 100000 записів, дорівнює:

KBO = KZ/(LB/LZ) = 100000/ (1024/256) = 100000/4 = 25000 блоків.

Це значить, що максимальна довжина доступу при безпосередньому пошуку довільного запису дорівнює 25000 звертань до диска. Раніше ми визначили, що с застосуванням індексу достатньо лише 11 звертань. Як бачимо, виграш дуже істотний.

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

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

Після знаходження блоку, у який потрібно помістити індексний запис, цей блок копіюється в оперативну пам'ять, там новий індексний запис уставляється на потрібне місце (в оперативній пам'яті це робиться швидко) і після цього змінений блок знов записується на диск на колишнє місце.

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

Тдодав = Log2KIB+1+1 = Log2728+1+1 » 10+1+1 = 12.

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

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

Доступ до даних, заснований на використанні щільного індексу називають індексно-прямим доступом, а файли з щільним індексом називають часто індексно-прямими файлами.