Лекції (деякі) - Структури та Алгоритми Обробки Даних - WEBPNZ на
Методи зберігання та доступу до даних.
Одним з основних факторів, що впливають на продуктивність програм, є спосіб зберігання та доступу до даних, розташованих на зовнішніх носіях. У цій темі будуть розглянуті такі методи доступу до даних:
1. Фізичний послідовний.
6. Метод доступу за допомогою хешування.
Ці методи доступу відрізняються один від одногоефективністю доступуіефективністю зберігання. Якщо критичною характеристикою є швидкодія, то вибирають методи з більш ефективним доступом, але, можливо, менш ефективні за обсягом пам'яті.
В іншому випадку, за рахунок зменшення об'єму пам'яті може бути збільшено час доступу.
Знаючи найефективніші методи доступу, програміст може вибрати найбільш прийнятне для нього співвідношення між двома вказаними характеристиками.
Фізичний послідовний метод доступу
Цей метод доступу передбачає зберігання фізичних записів у логічній послідовності. Якщо дані зберігаються на магнітній стрічці, то фізична та логічна послідовність записів збігаються.
Якщо дані зберігаються на пристрої з прямим доступом, записи повинні бути пов'язані так, щоб вони утворили логічну послідовність, навіть якщо вони не надходили для зберігання в цій послідовності.
Ефективність доступувкрай низька. Середня кількість записів, які потрібно вибрати для знаходження потрібної, дорівнює N/2, де N – кількість записів.
Ефективність зберіганнядуже висока. При використанні магнітної стрічки додаткова пам'ять не потрібна. При використанні прямого доступу додаткова пам'ять використовується тільки для організації зв'язків міжзаписами.
Цей метод доступу використовується в тих випадках, коли дані зберігаються на магнітній стрічці, або кількість записів незначно, і використовувати більш ефективні способи доступу недоцільно, або дані завжди обробляються послідовно.
Індексно-послідовний метод доступу
У цьому методі доступу файл даних упорядкований за первинним ключем .Первинний ключ– атрибут фізичного запису, що однозначно ідентифікує цей запис.
Індекс містить посилання не кожну запис файлу даних, але в блок записів. У індексний файл вноситься найбільше чи найменше значення блоку записів.
Оскільки індексний файл також упорядкований, це дозволяє створити індекс для індексного файла.
При початковому створенні файлу даних проводиться завантаження до нього фізичних записів, впорядкованих первинним ключем. Одночасно створюється індексний файл (наприклад, з найбільших значень ключа кожного заповненого блоку записів).
Як здійснюється включення нових записів? Залежно від значень ключів доданих записів може знадобитися зміна індексного файлу. Як чинити, якщо в блоці немає місця для розміщення нового запису? Можливі два варіанти вирішення проблеми.
1. Запис запам'ятовується в окремій області, яка називається областю переповнення, і блок у цій області зв'язується в ланцюжок з блоком, якому логічно належить запис.
2. При неможливості додавання запису до деякого блоку, він ділиться навпіл. До індексного файлу додається новий ключ.
І в тому, і в іншому випадку через деякий час може знадобитися реорганізація даних та індексів.
Ефективність доступузалежить від розміру блоку та кількості індексних файлів (рівня індексування).Ефективність доступу може бути підвищена за рахунок зберігання індексу вищого рівня оперативної пам'яті.
Ефективність зберіганнязалежить від кількості вільних фізичних блоків, що відводяться під область переповнення, та кількості вільної пам'яті в кожному блоці, а також від розміру блоку.