Главная | Обратная связь

Пошук запису із заданим значенням ключа

При послідовній структурі зберігання пошук може здійснюватися лише перебором. Читається перший фізичний запис, в ОП він розбивається на k логічних записи (розблоковується), задане значення ключа порівнюється із значенням ключа кожного логічного запису. При неспівпаданні читається наступний фізичний запис і процес повторюється. У кращому разі потрібний запис буде знайдений за одне звернення, в гіршому – необхідно прочитати всі фізичні записи. Середня кількість звернень до зовнішньої пам'яті для пошуку потрібного запису ТР визначається наступною формулою

ТР = (1+[N/k])/2

де N – кількість логічних записів, k – коефіцієнт блокування, [N/k] ‑ кількість фізичних записів.

Читання запису із заданим значенням ключа

Спочатку необхідно знайти потрібний запис (дивися операцію "пошук"). Після закінчення операції "пошук" потрібний запис вже зчитаний в ОП. Кількість звернень до ВП дорівнює ТР.

Коректування запису

Спочатку необхідно знайти потрібний запис (дивися операцію "пошук"). Після закінчення операції "пошук" в ОП знайдений логічний запис коректується, формується фізичний запис (блок) і заноситься у зовнішню пам'ять за тією адресою, звідки вона була зчитана. Кількість звернень до ВП дорівнює ТР+1.

Видалення запису

Аналогічна операції коректування. Службове поле відповідного логічного запису позначається як "видалений запис". Кількість звернень до ВП рівною ТР+1.

Додавання запису

Розглянемо два випадки. У першому випадку користувач вводить новий логічний запис у кінець таблиці. Тоді логічний запис, що вводиться, додається в кінець файлу. Він заноситься або в останній фізичний запис (якщо в ній менше k логічних записів – блок неповний), для цього цей запис має бути зчитаний в ОП. Якщо останній блок повний, то формується новий фізичний запис, який заноситься в кінець файлу. Кількість звернень до ВП рівна відповідно або 2, або 1.

У другому випадку користувач вводить новий логічний запис у вказаний їм i-ий рядок таблиці (i=1, 2, ..., n). У цьому випадку читається фізичний запис з номером [(i-1)/k], що містить i-ий, логічний запис. Якщо відповідний фізичний запис містить порожні логічні записи, то запис, що додається, вставляється у цей блок, блок записується на своє місце у ВП. Кількість звернень до ВП дорівнює 2. Якщо вказаний фізичний запис містить k екземплярів логічних записів вихідної таблиці, читається фізичний запис з номером [i/k]. Якщо цей фізичний запис містить порожні логічні записи, запис, що додається, вставляється в цей блок, блок записується на своє місце у ВП. Сумарна кількість звернень в цьому випадку буде на одиницю більшою і рівна 3.

Якщо фізичні записи з номерами [(i-1)/k] та [i/k] містять по k екземплярів вихідних логічних записів, необхідно формувати додатковий фізичний запис. Відповідний блок міститиме логічний запис, що додається, та k-1 порожніх логічних записів. Блоки з номерами [i/k], [(i+1)/k], ... [N/k] переписуються на одну позицію нижче (зсуваються). Сформований фізичний запис заноситься на місце, що звільнилося (місце запису з номером [i/k]).

У кращому разі (i = N) жоден блок не зрушується. У гіршому разі (i = 1) зсуваються всі блоки. Середня кількість звернень до ВП для перезапису блоків (читання + запис) складе 2[N/k]/2. Тоді сумарна кількість звернень до ВП при додаванні запису в цьому випадку буде рівною 3+[N/k].

Відмітимо, що якщо записи впорядковані за значеннями ключа може проводитися дихотомічним методом і кількість звернень до зовнішньої пам'яті буде не пропорційною (1+[N/k]) /2, а log₂[N/k], тобто істотно меншою. Проте додавання запису потребує для збереження впорядкованості, як правило, зсув великої кількості записів. Тому розміщення фізичних записів з впорядкуванням їх за значеннями ключа в СУБД не використовується.

 

36. Структура зберігання даних у зовнішній пам’яті комп’ютера. Розміщення фізичних записів у вигляді спискової структури

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

Окрім цього списку у ВП формується список вільних елементів ("порожніх" фізичних записів), елементи якого використовуються при введенні нового запису з даними (мал. 9.5).

Нагадаємо, що кожен фізичний запис складається, як і раніше, із k логічних записів.

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