апис; запис, що передує поточної і наступну за нею.
Відповідно до методів управління доступом до інформації в файлах розрізняють пристрої зовнішньої пам'яті (накопичувачі інформації) з довільною адресацією, або прямим доступом (магнітні і оптичні диски), і пристрої з послідовною адресацією, або послідовним доступом ( магнітофони, стриммери). На пристроях з довільною адресацією можлива установка головок для читання записи в будь-яку область накопичувача практично миттєво. На пристроях з послідовною адресацією вся пам'ять розглядається як лінійна послідовність інформаційних елементів. Тому в таких накопичувачах для отримання інформації потрібно пройти певний шлях від вихідного стану зчитувального пристрою до потрібного запису.
Файли з постійною довжиною запису, розташовані на пристроях прямого доступу (УПД), є файлами прямого доступу.
У цих файлах фізичну адресу розташування потрібного запису може бути обчислений за номером запису (NZ).
Кожна файлова система - система управління файлами - підтримує деяку ієрархічну файлову структуру, що включає найчастіше обмежене число рівнів ієрархії в поданні зовнішньої пам'яті (рис. 9).
Для кожного файлу в системі зберігається наступна інформація:
· ім'я файлу;
· тип файлу (наприклад, розширення або інші характеристики);
· розмір запису;
· число зайнятих фізичних блоків;- Базовий початковий адреса;
· посилання на сегмент розширення;
· спосіб доступу (код захисту).
Для файлів з постійною довжиною запису адреса розміщення запису з номером К може бути обчислений за формулою
ВА + (К - 1) LZ + 1, де ВА - базова адреса; LZ - довжина запису.
Якщо можна визначити адресу, на яку необхідно позиціонувати механізм зчитування запису, то пристрої прямого доступу роблять це практично миттєво, тому для таких файлів читання довільного запису практично не залежить від її номера.
На пристроях послідовного доступу можуть бути організовані файли тільки послідовного доступу.
Вони можуть бути організовані двома способами:
· кінець запису відзначається спеціальним маркером;
· на початку кожного запису записується її довжина.
Файли з прямим доступом забезпечують досить надійний спосіб доступу до запису. Основним недоліком файлів прямого доступу є те, що пошук запису провадиться за її номером, що при великому числі записів займає істотне час. Суть методів хешування полягає в тому, що вибираються значення ключа (або деякі його характеристики), які використовуються для початку пошуку, тобто обчислюється так звана хеш-функція h (k), де k - значення ключового поля. У цьому випадку число кроків пошуку значно зменшується. Однак при такому підході можливі ситуації, коли кільком різним ключам може відповідати одне значення хеш-функції, тобто одна адреса. Подібні ситуації називаються колізіями. Значення ключів, які мають одне і те ж значення хеш-функції, називаються синонімами.
Тому при використанні хешування як методу доступу необхідно прийняти два незалежних рішення:
· вибрати хеш-функцію;
· вибрати метод вирішення колізій.
Існує безліч різних стратегій вирішення колізій, найбільш поширеними з яких є:
· дозвіл колізії за допомогою області переповнення;
· дозвіл колізії методом вільного заміщення.
1.4 Дозвіл колізії за допомогою області переповнення
При виборі цієї стратегії область зберігання розбивається на дві частини: основну область і область переповнення.
Для кожного нового запису обчислюється значення хеш-функції, яке визначає адресу її розташування, і запис заноситься в основну область у відповідності з отриманим значенням хеш-функції.
Якщо знову заноситься запис має таке ж значення функції хешування, яке використовувала інший запис, вже наявна в БД, то новий запис заноситься в область переповнення на перше вільне місце, а в запису-синониме, яка знаходиться в основної області, робиться посилання на адресу знову розміщеної записи в області переповнення. Якщо ж вже існує посилання в записі-синониме, яка розташована в основний області, то новий запис отримує додаткову інформацію у вигляді посилання і вже в такому вигляді заноситься в область переповнення.
При такому алгоритмі час розміщення будь-якої нової записи становить не більше двох звернень до ди...
