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