Фізична організація даних в базі даних

Размещено на http://www.allbest.ru/

Реферат

На тему:

“Фізична організація даних в базі даних”

Львів 2011



План

1.Фізична модель бази даних

2. Дискова фізична модель бази даних

3. Управління дисковим простором

4. Управління буферами даних (в RAM)

5. Формати запису і сторінки

6. Файли записів

7. Висновки

8. Глосарій



Огляд

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

Ми охопимо наступні теми: керування дисковим простором, керування кешем буферів (в RAM) даних і організація збереження записів на диску. Іншими словами, ми опишемо, як модулі DBMS працюють над найнижчому рівні і які структури даних потрібні.

Проблеми щодо створення індексів і виконання операторів SQL будуть представлені в наступних лекціях.



1. Фізична модель бази даних

До тепер ми працювали переважно над проблемами, що стосуються логічної моделі бази даних. Тепер настав час розказати більше деталей про реалізацію логічної моделі в комп'ютері - і яка є фізичною моделлю бази даних. Ця модель безпосередньо залежить від поточної архітектури обчислювальних систем. Коли ця архітектура змінюється, ця модель також змінюється і звичайно це також матиме місце в майбутньому. Ми припускаємо, що читач знає архітектуру сучасних обчислювальних систем - включаючи засоби для зберігання даних, як наприклад магнітні диски. Технічні деталі того, як диски побудовані не - є темою цієї лекції.

Фізична модель бази даних базується на поняттях файлу (file) і запису (record). Файл скомпонований із записів, що мають однаковий формат. Формат запису - це список імен поля із специфікацією їх типів даних. Запис скомпонований із значень специфічних полів. Деякі з цих полів відрізняються як пошуковий ключ записів .Може бути більш ніж один ключ для пошуку записів. На фізичному рівні не вимагається мати унікальне ім'я (ключ) для запису у файлі.

Основні дії з файлами, які використовують програми:

Insertion - вставити запис у файлі.

Deletion - вилучити запис з файлу.

Modification - змінити вміст запису у файлі.

Search - пошук записів у файлі з даним пошуковим ключовим значенням або пошук за визначеним критеріями.

Ми повинні підкреслити тут, що файл фізичної моделі бази даних може зображатися файлом, доступним у файловій системі комп'ютера, - але це не так. От чому поняття файлу з записами не ідентичне дисковому файлу.

В спеціальному випадку дисковий файл може включити окремі файли бази даних (наприклад у разі кластера окремих таблиць).

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

Диски і файли

Сучасні системи управління базою даних зберігають дані на жорстких дисках. Щоб оперувати зданими, вони повинні спочатку занестися в оперативну пам'ять, потім виконуються над ними деякі дії, а результат повинен зберегтися назад на жорсткий диск. От чому ми завжди використовуємо дискові операції вводу/виводу (IO):

WRITE:передача даних з оперативної пам'яті на диск.

READ: передача даних від диска у оперативну пам'ять.

Складність операцій баз даних представляється як кількість операцій вводу/виводу.

Природнім є запитання - а чому дані не зберігаються в оперативній пам'яті?

Перший аргумент це факт, що пам'ять є оперативною. Після виключення комп'ютера з електромережі ми втрачаємо всі дані. Хоча ми могли б аргументувати тут, що можна використовувати UPS, щоб при аварійному виключенні всі дані збереглися на диск.

Другий важливий аргумент є, що оперативна пам'ять є дорожчою ніж жорсткий диск.

Третій аргумент рішення є, що дотепер 32 біти, що адресуються, обмежують кількість даних, які можуть зберігатися в оперативній пам'яті. Проте, це планується змінитися до 64 розрядних адресацій в майбутньому.

Згадане вище обговорення показує, що в найближчому майбутньому ми можемо зустріти нову, альтернативну фізичну модель бази даних. Проте факт на сьогодні є такий, що первинний засіб для збереження даних - це магнітний диск.

Окрім дисків ми також використовуємо більші, проте повільніші в доступі, носії даних, як наприклад оптичні диски. Вони використовують для зберігання: дублювання поточних баз даних, реєстрації операції off-line і архівні копії даних.

Особливості використання даних, збережених на диску

Довільний доступ (random access): спосіб організації доступу до пристрою памґяті, де для читання/запису не потрібен послідовний перегляд блоків починаючи з найпершого.

Дані зберігаються і вибираються частинами під назвою блоки диска (disk blocks) або сторінки (pages).

Час доступу до даних на диску залежить від їх розташування на диску. От чому розташування сторінок на диску може мати істотний вплив на швидкість DBMS! Отримуються кращі результати, коли опрацьовуємо сторінки розміщені одна за одною.

Дані котрі часто використовуються прикладними програмами, зберігаються в буферах RAM (cashing). Доступ до цих даних відбувається дуже швидко.

Читання і запис блоку може відбуватися паралельно. Також розподіл даних на різних дисках в межах однієї транзакції має істотний вплив на швидкість.

На магнітних дисках доступ є послідовний - дані читаються один за одним виконується від початку до кінця, як одна довга дія IO. Перевага стрічки - це великий розмір і низька вартість. Вони використовуються для архівування даних і створення резервних копій (back-ups).

2. Дискова фізична модель бази даних

У разі вибору диска як первинного носія даних в базі, загальна фізична модель розширюється сторінками диска. Тут є короткий огляд:

Таблицю (відношення) (table (relation) зображають файлом (на диску). Файл скомпонований із сторінок. Сторінка скомпонована із записів. Запис скомпонований з полів.

Окрім:

Коли розмір запису більший, ніж розмір сторінки, тоді запис ділять на дві частини, які зберігаються на різних сторінках.

Об'єкти LOB зберігаються в окремій області призначеній для зберігання в базі - звичайно це є послідовність сторінок збережених одна за одною. Тільки їх локатори зберігаються в записах.

Коли схема доступу до даних базується обґєднаних даних від двох або більше таблиць (наприклад департаменти і їх працівники), дані від окремих таблиць групуються в одному файлі, на одному відкритому ключі (наприклад номер департаменту або код клієнта) - в такому випадку ми звертаємося до кластера таблиці (cluster).

Ієрархія засобів, для збереження даних в базі

RAM використовується для даних тепер.

Диск для основної бази даних.

Магнітна стрічка для архівування даних і резервної копії.

Ми зараз продовжуватимемо обговорювати основні модулі DBMS, що виконують дії на сторінках (не звернення до записів), які використовуються іншими модулями DBMS. Ними є: менеджер дискового простору (disk space manager) і менеджер буферів RAM (RAM buffer manager).

3. Управління дисковим простором

Є два види сторінок у файлі бази даних:

сторінки з вільним просторм для запису нових записів, і

сторінки майже або цілком заповнені.

Ми також припускаємо, що система може розширити файл записів і виділити нові, порожні сторінки а також що система може здібна до повернути (звільнити) сторінки, які не використовуються.

Менеджер дискового простору виконує наступні функції:

Читання сторінки у пам'ять.

Запис сторінки на диск.

Локалізація сторінки або послідовності сторінок (розташованих в суміжній області диска).

Повернення (звільнення) сторінки.

Розмір сторінки - це звичайно розмір блоку диска і сторінок збережені як блоки диска так, що операції запису/читання сторінки звичайно виконуються як єдина дія I/O.

Менеджер дискового простору приховує деталі про технічні засоби і операційну систему і дозволяє іншим модулям обійтися з даними на диску як з множиною сторінок.

4. Управління буферами даних (в RAM)

Менеджер буфера даних відповідає за відновлення сторінок з диска у динамічні буфери даних в RAM. Дані повинні розміщуватися в буферах даних для того, щоб процеси DBMS обробляли їх! Сторінка записується у фрейм (frame).

Окрім динамічної області фреймів, також зберігаються в RAM :

таблиця <frameid, pageid>

для кожного фрейма: pin count - скільки різних процесів використовують фрейм в той же час. На початку після розміщення сторінки у фреймі: pin count = 1

для кожного фрейма: modification bit = true - якщо після відновлення сторінки до фрейма, вміст фрейма був змінений ("dirty" state). Це означає, що сторінка на диску, який є джерелом цього вмісту фрейма, може бути вже іншою, ніж вміст фрейма в RAM. На початку після розміщення сторінки у фреймі: modification bit = false

Крім того, всі фрейми, що мають pin count = 0 формують список вільних фреймів ( the list of free frames).

Модуль менеджера буфера даних використовується процесами DBMS - переважно процесами розподіленими для користувацьких запитів. Нижче того, є план того, як це працює:

Якщо процесору потрібна сторінка, виконується наступний алгоритм:

Якщо запитана сторінка не доступна в динамічній області фрейма:

Виберіть фрейм зі списку вільних фреймів (pin count = 0).

Якщо сторінка у вибраному фреймі була змінена, але не оновлена на диску (modification bit = true ), запишіть це до диска.

Читати потрібну сторінку до вибраного фрейма.

Встановити pin count = 1.

Якщо запитана сторінка знаходиться в динамічній області фрейма, збільшити на 1 pin count.

Якщо фрейм є у списку вільних фреймів, вилучити із списку.

Дайте процес вказівником на фрейм.

Якщо вміст фрейма змінений:

Встановіть modification bit = true .

Сторінка в буфері даних може бути потрібна багатьом процесам:

Нова вимога на сторінку у фреймі збільшує на 1 pin count.

Коли процес звільняє сторінку у фреймі зменшення на 1 pin count. Процес повинен зберегти номер фрейма, який це використовує.

Фрейм стає кандидатом для заміни, коли pin count = 0. Він тоді потрапляє у список вільних фреймів незалежно від значення modification bit.

Один фрейм в RAM може використовуватися багатьма процесами. Яким чином і якими процедурами це відбувається буде обговорюватися в лекції про транзакції.

Стратегія заміни сторінок у фреймах (зі списку вільних фреймів)

Сторінка додається до списку вільних фреймів, pin count = 0 . Нова сторінка, взята з диска, замінює одну із сторінок, розміщених у списку вільних фреймів.

LRU - це замінює сторінку, яка найменше недавно використовувалася;

MRU - це замінює сторінку, яка найбільше недавно використовувалася;

Clock - сторінки замінюються у фіксованому, циклічному порядку.

Послідовне заповнення динамічної області фрейма:

Коли ми використовуємо стратегію LRU, ми повторюємо послідовні сканування файлу. Коли #buffer frames < #pages у файлі, тоді кожний запит викликає дію IO.

Стратегія для попереднього зчитування фреймів в буфер RAM з подальшим використанням стратегії MRU повинна бути в цьому випадку кращою. Частина сторінок яка рівна #buffer frames-1 повинна залишатися весь час в динамічній області буфера. Решта сторінок повинна бути записана послідовно в один з фреймів.

На практиці, процес опрацьовування користувацького запиту може містити інформацію про те, що деякі сторінки часто використовуються, і таким чином повинні постійно зберігатися в буферах RAM. Більшість комерційнх баз даних підтримують таку можливість.

Обробка вказівників

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

файл програма диск фрейм

5. Формати запису і сторінки

Коли користувачу потрібен специфічний запис від бази даних, відбувається процес, що узгоджується із запитом користувача:

спершу обчислюється адресу сторінки, де даний запис розміщений;

потім відновлюється сторінка з диску і записується в буфер RAM (працює менеджер дискового простору і менеджер буфера RAM.

потім відновлюється шуканий запис і подається користувачу

В пункті 3 потрібні знання про структури даних на сторінці, відносно полів в записі і записах на сторінці. Ми опишемо їх зараз.

Ми припускаємо, що кількість і типи полів є однакові для всіх записів у файлі; вони зберігаються в словнику баз даних (каталог системи). Є окремі альтернативні формати для збереження полів в записі.

Формат запису: фіксована довжина поля

Запис зображають, як послідовність послідовних полів P1...,Pn фіксованого розміру D1...,Dn. Маючи базову адресу (початок запису) B можна легко вирахувати початок i-того поля як B+D1+...+Di-1.

6. Файли записів

Файл - це набір сторінок, який може містити нуль, однин або більше записів. Виконуються наступні дії на файлі:

вставка/ вилучення/модифікація запису (insert/delete/modify);

прочитати частковий запис з отриманим rid (read);

пошук всіх записів, які підлягають певній умов (search).

Є окремі шляхи, як організувати файли записів. Основна різниця між ними є, чи впорядковані записи відносно значень деякого ключа чи ні. Давайте розглянемо організацію невпорядкованого файлу (heap file).

Невпорядковані файли

Записи зберігаються на сторінках файлу невпорядковано.

Новий запис вставляється на першу вільну сторінку, яка доступна.

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

Невпорядкована організація є добра, коли ми виконуємо запити, які торкаються всіх записів або більшість з них, наприклад:

SELECT* FROM Emp;

або

SELECT * FROM Emp e WHERE e.Sal > 1000;

Відсортований файл

Записи зберігаються на сторінках згідно значення пошукового ключа запису. Це представлення добре, коли всі записи або як мінімум значна їх кількість обробляються у визначеному порядку, наприклад:

SELECT * FROM Emp e ORDER BY e.Sal;

або

SELECT * FROM Emp e WHERE e.Sal BETWEEN 1000 and 2000 ORDER BY e.Sal;

У відсортованому файлі, пошук записів, грунтується на пошуковому ключі, є ненабагато швидше з порівнюваним невпорядкованим хеш-файлом. Але з тих пір, як записи розміщуються на диску, використання одного з швидких методів пошуку, подібно двійковому пошуку, не повністю можливе.

Є дві можливі реалізації:

1. Full extent - сторінок, що розміщені поряд один за одним на диску, - записи впорядковані згідно значень пошукового ключа. Є проблема зі вставкою нового запису або вилученням запису з файлу. Ми можемо використовувати двійковий пошук для пошуку відносно пошукового ключового значення.

2. Page list (або extent list) - записи, впорядковані згідно пошукового ключового значення. Немає проблеми зі вставкою нового запису і вилученням запису з файлу. Безпосередньо немає можливості використовування методу двійкового пошуку - потрібна додаткова структура, використовуючи відсортовані дані

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

Хеш - файл

Хеш-файл - це набір ділянок записів (buckets of records). Ділянка - це головна сторінка плюс нуль або більше сторінок переповнення(overflow pages) , локалізованих до ділянки, якщо потрібно. Розміщення запису до ділянки зроблена здійснюється по значенню хеш-функції (hashing function), яка по пошуковому ключі запису, яким є одне або більше полів запису:

Хеш-функція h:

h(record's r search key) = адреса ділянки де запис r попадає.

З цим методом, записи з тим же значенням пошукового ключа розміщують на тій же сторінці або тільки на окремих сторінках диска. Це вельми важливо при виконанні пошуку, тому що пошук всіх записів з даним ключовим значенням вимагає відновлення тільки окремих сторінок, а не окремої сторінки для кожного запису.

Організація хеш - файлу мішанини корисна при виборі запису з файлу, який базується на значенні або значеннях деяких полів запису, наприклад при виконанні запиту:

SELECT * FROM Emp e WHERE e.Ename=:Surname;

Організація записів у хеш - файлі мішанини не підтримує порядок значень пошукового ключа.

Використання тільки однієї організація записів у файлі звичайно не достатньо для додатків бази даних, де пошукові дії проводяться на значеннях різних пошукових ключів. Щоб вирішити цю проблему ми повинні використовувати окремі індексні структури. Їх вивчення почнеться в наступній лекції.



7. Висновки

Протягом цієї лекції ми ознайомились з фізичною моделлю бази даних, яка ґрунтується на поняттях файлу, сторінки, запису і буфера даних. В наступних лекціях ми охопимо поняття правил функціонування DBMS на основі представленої моделі.



8. Глосарій

database physical model - представлення таблиці в термінах структур зберігання даних в комп'ютері. Основна фізична модель диска: таблицю зображають файлом; файл складається із сторінок, сторінка складається із записів, запис скомпонованийз полів.

(database) file - представлення таблиці у фізичній моделі бази даних.

record - фізичне представлення рядка.

field - представлення (елемент рядка) значення стовпця у фізичній моделі бази даних.

search key - вибрані поля запису, на яких проводиться пошук. Може бути багато ключів для пошуку записів.

page (block) - фізична одиниця зберігання даних на диску. Дані перенесяться між буферами RAM і сторінками диска. Одна сторінка може утримувати цілий ряд записів.

data buffer - місце в RAM, де сторінка диска відновлена.

LRU - основна стратегія заміни сторінок в динамічній області буфера даних; сторінка, яка найменше недавно використовувалася, замінюється.

unordered heap file - файл, де записи зберігаються на сторінках ні в якому особливому порядку.

sorted file - файл, де записи впорядковуються по значенню пошукового ключа запису.

hash file - файл, який є набором ділянок пам?яті. Розділення записів в ділянках здійснюється на значенні функції під назвою хеш-функції, що ґрунтується на використанні пошукового ключа запису.

hash function - функція, яка призначає адресу ділянки для пошуку значень ключа.

Размещено на Allbest.ru