ску, з урахуванням того, що номер першої вільної записи в області переповнення зберігається у вигляді системної змінної.
. 5 Дозвіл колізії методом вільного заміщення
При цій стратегії файловий простір не поділяється на області, але для кожного запису додаються два покажчики: покажчик на попередній запис у ланцюжку синонімів і покажчик на наступний запис в ланцюжку синонімів. Відсутність відповідного посилання позначається спеціальним символом, наприклад нулем. Для кожного нового запису обчислюється значення хеш-функції і, якщо даний адреса вільна, запис потрапляє на задане місце і стає першою в ланцюжку синонімів.
Якщо запис, який займає необхідне місце, не є першим записом у ланцюжку синонімів, значить, вона займає дане місце «незаконно» і при появі «законного власника» повинна бути «виселена», тобто переміщена на нове місце.
Після переміщення «незаконної» записи знову вноситься запис займає своє законне місце і стає першим записом у новій ланцюжку синонімів.
. 6 Індексні файли
Незважаючи на високу ефективність хеш-адресації в файлових структурах не завжди вдається знайти відповідну функцію, тому при організації доступу по первинному ключу широко використовуються індексні файли.
Індексні файли можна представити як файли, що складаються з двох частин. Спочатку йде індексна область, яка займає деякий ціле число блоків, а потім йде основна область, у якій послідовно розташовані всі записи файлу.
У деяких системах індексними файлами називаються також і файли, організовані у вигляді інвертованих списків, які використовуються для доступу по вторинному ключу. Залежно від організації індексного і основний областей розрізняють два типи файлів: з щільним індексом (індексного-прямі файли) і з нещільним індексом (індексного-послідовні файли).
. 6.1 Файли з щільним індексом, або індексного-прямі файли.
У цих файлах основна область містить послідовність записів однакової довжини, розташованих у довільному порядку, а структура індексного запису в них має наступний вигляд:
Таблиця
Значення ключаНомер записи
Тут значення ключа - це значення первинного ключа, а номер запису - це порядковий номер запису в основній області, яка має дане значення первинного ключа.
Найбільш ефективним алгоритмом пошуку на упорядкованому масиві є логарифмічний, або бінарний, пошук. У теорії ймовірності його називають методом половинного ділення. Максимальне число кроків пошуку визначається двійковим логарифмом від загального числа елементів (цілей) в шуканому просторі пошуку:
де N - число елементів.
При пошуку записів істотним є тільки число звернень до диска за заданим значенням первинного ключа. Спочатку проводиться пошук в індексному області, де застосовується двійковий алгоритм пошуку індексного запису, а потім шляхом прямої адресації в основний області проводиться пошук по номеру запису. Для того щоб оцінити максимальний час доступу до запису, необхідно визначити число звернень до диска в процecce пошуку.
Відповідно до формули число звернень до диска при пошуку записи визначиться наступним чином:
де - число індексних блоків, в яких розміщуються всі записи.
Враховуючи що після пошуку запису в індексному блоці потрібно ще раз звернутися до основної області, у формулі, додалася одиниця (+1).
Отже, способи організації файлів баз даних та відповідні їм фізичні моделі повинні бути спрямовані на скорочення часу звернення до дискового простору при її пошуку і скороченню часу на додавання і коригування змісту баз даних. На це і спрямований метод організації файлів з нещільним індексом.
. 6.2 Файли з нещільним індексом, або індексного-послідовні файли
Структура записів даних в таких файлах має вигляд, представлений на рис. 4.
При такій організації файлової структури процеси додавання нових записів відрізняються від аналогічних дій у файлах з щільним індексом. Кожна нова запис заноситься в відповідний блок на місце, визначене значенням ключового поля. У цьому випадку виконується наступна послідовність дій:
- визначається номер блоку основної області, в який необхідно помістити новий запис;
- знайдений блок зчитується в оперативну пам'ять;
- в оперативній пам'яті здійснюється коректування блоку;
- відкоригований блок записується на диск на колишнє місце...
