Внутрішня організація реляційної СУБД

Структури зовнішньої пам’яті, методи організації індексів

Реляційна СУБД володіє рядом особливостей, що впливають на організацію зовнішньої пам'яті. До найбільш важливих особливостей можна віднести наступні:

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

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

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

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

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

Відповідно виникають наступні різновиди об'єктів у зовнішній пам'яті бази даних:

рядки відносин - основна частина бази даних, переважно безпосередньо видима користувачам;

керуючі структури - індекси, що створюються з ініціативи користувача (адміністратора) або верхнього рівня системи з міркувань підвищення ефективності виконання запитів і звичайно автоматично системи, що підтримуються нижнім рівнем;

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

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

Ми розглядали на прикладах System R і Ingres два альтернативних підходи до організації реляційної СУБД з точки розділення функцій між різними компонентами. Нагадаємо, що в СУБД System R існувала інтегрована підсистема управління даними, транзакціями і журналізацією, в той час як в Ingres управління даними, було відділено від управління транзакціями і журналізацією.

У обох цих підходів є свої переваги і недоліки. Підхід System R дозволяє використати більш ефективні методи за рахунок спільного розв'язання проблем фізичної і логічної синхронізації, використанні загальних протоколів при управлінні буферами і журналізації і т.д. Але при цьому в деякому розумінні підсистема нижнього рівня стає монолітом; при самої вдалій її структуризації компоненти залишаються пов'язаними загальними протоколами взаємодії. Непродумані локальні зміни одного компонента можуть призвести до фатальних наслідків для всієї системи. Підхід Ingres дозволяє спростити структуру системи і зробити її більш гнучкої, але це можливе тільки за рахунок огрублення алгоритмів: застосування більш грубих методів управління транзакціями; жорстких протоколів журналізації і т.д.

Зрештою будь-яка конкретна система засновується на конкретному комплексному рішенні. Ми розглядаємо тут фрагменти таких рішень (ескізи).

9.1. Зберігання відносин

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

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

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

До основних характеристик цієї організації можна віднести наступні:

Кожний кортеж володіє унікальним ідентифікатором (tid), не змінним під весь час існування кортежу. Структура tid виходить з приведеного вище малюнка.

Звичайно кожний кортеж зберігається цілком в одній сторінці. З цього слідує, що максимальна довжина кортежу будь-якого відношення обмежена розмірами сторінки. Виникає питання: як бути з "довгими" даними, які в принципі не вміщуються в одній сторінці? Застосовуються декілька методів. Найбільш простим рішенням є зберігання таких даних в окремих (поза базою даних) файлах із заміною "довгого" даного в кортежі на ім'я відповідного файла. У деяких системах (наприклад, в передостанній версії СУБД Informix) такі дані зберігалися в окремому наборі сторінок зовнішньої пам'яті, пов'язаному фізичними посиланнями. Обидва ці рішення сильно обмежують можливість роботи з довгими даними (як, наприклад, видалити декілька байтів з середини 2-мегабайтной рядка?). У цей час все частіше використовується метод, запропонований декілька років тому в проекті Exodus, коли "довгі" дані організуються у вигляді В-дерев послідовностей байтів.

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

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