Велика бібліотека української літератури
» » Внутрішня організація реляційної СУБД

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

Структури зовнішньої пам’яті, методи організації індексів
Реляційна СУБД володіє рядом особливостей, що впливають на організацію зовнішньої пам'яті. До найбільш важливих особливостей можна віднести наступні:
Наявність двох рівнів системи: рівня безпосереднього управління даними у зовнішній пам'яті (а також звичайно управління буферами оперативної пам'яті, управління транзакціями і журналізацією змін БД) і язикового рівня (наприклад, рівня, що реалізовує мову SQL). При такій організації підсистема нижнього рівня повинна підтримувати у зовнішній пам'яті набір базових структур, конкретна інтерпретація яких входить в число функцій підсистеми верхнього рівня.
Підтримка відносин-каталогів. Інформація, пов'язана з іменуванням об'єктів бази даних і їх конкретними властивостями (наприклад, структура ключа індексу), підтримується підсистемою язикового рівня. З точки зору структур зовнішньої пам'яті відношення-каталог нічим не відрізняється від звичайного відношення бази даних.
Регулярність структур даних. Оскільки основним об'єктом реляційної моделі даних є плоска таблиця, головний набір об'єктів зовнішньої пам'яті може мати дуже просту регулярну структуру.
При цьому необхідно забезпечити можливість ефективного виконання операторів язикового рівня як над одним відношенням (проста селекція і проекція), так і над декількома відносинами (найбільш поширено з'єднання декількох відносин). Для цього у зовнішній пам'яті повинні підтримуватися додаткові "керуючі" структури - індекси.
Нарешті, для виконання вимоги надійного зберігання баз даних необхідно підтримувати надмірність зберігання даних, що звичайно реалізовується у вигляді журналу змін бази даних.
Відповідно виникають наступні різновиди об'єктів у зовнішній пам'яті бази даних:
рядки відносин - основна частина бази даних, переважно безпосередньо видима користувачам;
керуючі структури - індекси, що створюються з ініціативи користувача (адміністратора) або верхнього рівня системи з міркувань підвищення ефективності виконання запитів і звичайно автоматично системи, що підтримуються нижнім рівнем;
журнальна інформація, що підтримується для задоволення потреби в надійному зберіганні даних;
службова інформація, що підтримується для задоволення внутрішніх потреб нижнього рівня системи (наприклад, інформація про вільну пам'ять).
Ми розглядали на прикладах System R і Ingres два альтернативних підходи до організації реляційної СУБД з точки розділення функцій між різними компонентами. Нагадаємо, що в СУБД System R існувала інтегрована підсистема управління даними, транзакціями і журналізацією, в той час як в Ingres управління даними, було відділено від управління транзакціями і журналізацією.
У обох цих підходів є свої переваги і недоліки. Підхід System R дозволяє використати більш ефективні методи за рахунок спільного розв'язання проблем фізичної і логічної синхронізації, використанні загальних протоколів при управлінні буферами і журналізації і т.д. Але при цьому в деякому розумінні підсистема нижнього рівня стає монолітом; при самої вдалій її структуризації компоненти залишаються пов'язаними загальними протоколами взаємодії. Непродумані локальні зміни одного компонента можуть призвести до фатальних наслідків для всієї системи. Підхід Ingres дозволяє спростити структуру системи і зробити її більш гнучкої, але це можливе тільки за рахунок огрублення алгоритмів: застосування більш грубих методів управління транзакціями; жорстких протоколів журналізації і т.д.
Зрештою будь-яка конкретна система засновується на конкретному комплексному рішенні. Ми розглядаємо тут фрагменти таких рішень (ескізи).
9.1. Зберігання відносин
Існують два принципових підходи до фізичного зберігання відносин. Найбільш поширеним є покортежне зберігання відносин (кортеж є одиницею фізичного зберігання). Природно, це забезпечує швидкий доступ до цілого кортежу, але при цьому у зовнішній пам'яті дублюються загальні значення різних кортежів одного відношення і, взагалі кажучи, можуть бути потрібні зайві обміни із зовнішньою пам'яттю, якщо потрібна частина кортежу.
Альтернативним (менш поширеним) підходом є зберігання відношення по стовпцях, тобто одиницею зберігання є стовпець відносин з виключеними дублікатами. Природно, що при такій організації сумарно в середньому тратиться менше зовнішній пам'яті, оскільки дублікати значень не зберігаються; за один обмін із зовнішньою пам'яттю в загальному випадку прочитується більше корисній інформації. Додатковою перевагою є можливість використання значень стовпця відношення для оптимізації виконання операцій з'єднання. Але при цьому потрібні істотні додаткові дії для збирання цілого кортежу (або його частини).
Оскільки набагато більш поширено зберігання по рядках, ми розглянемо трохи більш детально цей спосіб зберігання відносин. Типовою, успадкованою від System R, структурою сторінки даних є наступна:
До основних характеристик цієї організації можна віднести наступні:
Кожний кортеж володіє унікальним ідентифікатором (tid), не змінним під весь час існування кортежу. Структура tid виходить з приведеного вище малюнка.
Звичайно кожний кортеж зберігається цілком в одній сторінці. З цього слідує, що максимальна довжина кортежу будь-якого відношення обмежена розмірами сторінки. Виникає питання: як бути з "довгими" даними, які в принципі не вміщуються в одній сторінці? Застосовуються декілька методів. Найбільш простим рішенням є зберігання таких даних в окремих (поза базою даних) файлах із заміною "довгого" даного в кортежі на ім'я відповідного файла. У деяких системах (наприклад, в передостанній версії СУБД Informix) такі дані зберігалися в окремому наборі сторінок зовнішньої пам'яті, пов'язаному фізичними посиланнями. Обидва ці рішення сильно обмежують можливість роботи з довгими даними (як, наприклад, видалити декілька байтів з середини 2-мегабайтной рядка?). У цей час все частіше використовується метод, запропонований декілька років тому в проекті Exodus, коли "довгі" дані організуються у вигляді В-дерев послідовностей байтів.
Як правило, в одній сторінці даних зберігаються кортежі тільки одного відношення. Існують, однак, варіанти з можливістю зберігання в одній сторінці кортежів декількох відносин. Це викликає деякі додаткові витрати по частині службової інформації (при кожному кортежі треба зберігати інформацію про відповідне відношення), але зате іноді дозволяє різко скоротити число обмінів із зовнішньою пам'яттю при виконанні з'єднань.
Зміна схеми відносин, що зберігаються з доданням нового стовпця не викликає потреби в фізичній реорганізації відношення. Досить лише змінити інформацію в описувачі відношення і розширювати кортежі тільки при занесенні інформації в новий стовпець.
Оскільки відносини можуть містити невизначені значення, необхідна відповідна підтримка на рівні зберігання. Звичайно це досягається шляхом зберігання відповідної шкали при кожному кортежі, який в принципі може містити невизначені значення.
Проблема розподілу пам'яті в сторінках даних пов'язана з проблемами синхронізації і журналізації і не завжди тривіальна. Наприклад, якщо в ході виконання транзакції деяка сторінка даних спустошується, то її не можна перевести в статус вільних сторінок до кінця транзакції, оскільки при відкаті транзакції видалені при прямому виконанні транзакції і відновлені при її відкаті кортежі повинні отримати ті ж самі ідентифікатори.
Поширеним способом підвищення ефективності СУБД є кластеризація відношення по значеннях одного або декількох стовпців. Корисним для оптимізації з'єднань є спільна кластеризація декількох відносин.
З метою використання можливостей розпаралелювання обмінів із зовнішньою пам'яттю іноді застосовують схему декластеризованого зберігання відносин: кортежі із загальним значенням стовпця декластеризації розміщують на різних дискових пристроях, обміни з якими можна виконувати в паралель.
Що ж до зберігання відношення по стовпцях, то основна ідея складається в спільному зберіганні всіх значень одного (або декількох) стовпців. Для кожного кортежу відношення зберігається кортеж тієї ж міри, що складається з посилань на місця розташування відповідних значень стовпців. У останній лекції ми будемо розглядати особливості організації розподіленій реляційній СУБД. Одним з прийомів є так зване вертикальне розділення відносин, коли в різних вузлах мережі зберігаються різні проекції даного відношення. Зберігання відношення по стовпцях в деякому розумінні є граничним випадком вертикального розділення відносин.
9.2. Індекси
Як би не були організовані індекси в конкретній СУБД, їх основне призначення складається в забезпеченні ефективного прямого доступу до кортежу відношення по ключу. Звичайно індекс визначається для одного відношення, і ключем є значення атрибута (можливо, складового). Якщо ключем індексу є можливий ключ відношення, то індекс повинен володіти властивістю унікальності, тобто не містити дублікатів ключа. На практиці ситуація виглядає звичайно протилежно: при оголошенні первинного ключа відношення автоматично заводиться унікальний індекс, а єдиним способом оголошення можливого ключа, відмінного від первинного, є явне створення унікального індексу. Це пов'язано з тим, що для перевірки збереження властивості унікальності можливого ключа так чи інакше потрібна індексна підтримка.
Оскільки при виконанні багатьох операцій язикового рівня потрібне сортування відносин у відповідності зі значеннями деяких атрибутів, корисною властивістю індексу є забезпечення послідовного перегляду кортежів відношення в діапазоні значень ключа в порядку зростання або убування значень ключа.
Нарешті, одним з способів оптимізації виконання еквіз'єднання відносин (найбільш поширена з числа операцій, що дорого коштують) є організація так званих мультиіндексів для декількох відносин, що володіють загальними атрибутами. Будь-хто з цих атрибутів (або їх набір) може виступати як ключ мультиіндекса. Значенню ключа зіставляється набір кортежів всіх пов'язаних мультиіндексом відносин, значення виділених атрибутів яких співпадають зі значенням ключа.
Загальною ідеєю будь-якої організації індексу, підтримуючого прямий доступ по ключу і послідовний перегляд в порядку зростання або убування значень ключа є зберігання впорядкованого списку значень ключа з прив'язкою до кожного значення ключа списку ідентифікаторів кортежів. Одна організація індексу відрізняється від іншої головним чином в способі пошуку ключа із заданим значенням.
9.2.1. B-дерева
Видимо, найбільш популярним підходом до організації індексів в базах даних є використання техніки В-дерев. З точки зору зовнішнього логічного уявлення В-дерево - це збалансоване сильно гіллясте дерево у зовнішній пам'яті. Збалансованість означає, що довжина шляху від кореня дерева до будь-якого його листа одна і та ж. Гіллястість дерева - це властивість кожного вузла дерева посилатися але велике число вузлів-нащадків. З точки зору фізичної організації В-дерево представляється як мультиспискова структура сторінок зовнішньої пам'яті, тобто кожному вузлу дерева відповідає блок зовнішньої пам'яті (сторінка). Внутрішні і листові сторінки звичайно мають різну структуру.
У типовому випадку структура внутрішньої сторінки виглядає таким чином:
При цьому витримуються наступні властивості:
ключ(1) <= ключ(2) <=. .. <= ключ(n);
в сторінці дерева Nm знаходяться ключі k зі значеннями ключ(m) <= k <= ключ(m+1).
Листова сторінка звичайно має наступну структуру:
Листова сторінка володіє наступними властивостями:
ключ(1) < ключ(2) <. .. < ключ(t);
сп(r) - впорядкований список ідентифікаторів кортежів (tid), що включають значення ключ(r);
листові сторінки пов'язані одно - або двонаправленим списком.
Пошук в В-дереві - це проходження від кореня до листа відповідно до заданого значення ключа. Помітимо, що оскільки дерева сильно гіллясті і збалансовані, то для виконання пошуку по будь-якому значенню ключа буде потрібне одне і те ж (і звичайне невелике) число обмінів із зовнішньою пам'яттю. Більш точно, в збалансованому дереві, де довжини всіх шляхів від кореня до листа одні і ті ж, якщо у внутрішній сторінці вміщується n ключів, то при зберіганні m записів потрібне дерево глибиною logn(m), де logn обчислює логарифм по основі n. Якщо n досить велике (звичайний випадок), то глибина дерева невелика, і проводиться швидкий пошук.
Основною "родзинкою" В-дерев є автоматична підтримка властивості збалансованості. Розглянемо, як це робиться при виконанні операцій занесення і видалення записів.
При занесення нового запису виконується:
Пошук листової сторінки. Фактично, проводиться звичайний пошук по ключу. Якщо в В-дереві не міститься ключ із заданим значенням, то буде отриманий номер сторінки, в якій йому належить міститися, і відповідні координати всередині сторінки.
Приміщення запису на місце. Природно, що вся робота виготовляється в буферах оперативної пам'яті. Листова сторінка, в яку потрібно занести запис, прочитується в буфер, і в ньому виконується операція вставки. Розмір буфера повинен перевищувати розмір сторінки зовнішньої пам'яті.
Якщо після виконання вставки нового запису розмір частини буфера, що використовується не перевершує розміру сторінки, то на цьому виконання операції занесення запису закінчується. Буфер може бути негайно виштовхнений у зовнішню пам'ять, або тимчасово збережений в оперативній пам'яті в залежності від політики управління буферами.
Якщо ж виникло переповнення буфера (тобто розмір його частини, що використовується перевершує розмір сторінки), те виконується розщеплення сторінки. Для цього запитується нова сторінка зовнішньої пам'яті, частина буфера, що використовується розбивається грубо кажучи пополам (так, щоб друга половина також починалася з ключа), і друга половина записується у знову виділену сторінку, а в старій сторінці модифікується значення розміру вільної пам'яті. Природно, модифікуються посилання по списку листових сторінок.
Щоб забезпечити доступ від кореня дерева до наново заведеної сторінки, необхідно відповідним образом модифікувати внутрішню сторінку, що є предком листової сторінки, що раніше існувала, тобто вставити в неї відповідне значення ключа і посилання на нову сторінку. При виконанні цієї дії може знов статися переповнення тепер вже внутрішньої сторінки, і вона буде розщепленням на дві. У результаті зажадається вставити значення ключа і посилання на нову сторінку у внутрішню сторінки-предка вище по ієрархії і т.д.
Граничним випадком є переповнення кореневої сторінки В-дерева. У цьому випадку вона також розщеплюється на дві, і заводиться нова коренева сторінка дерева, тобто його глибина збільшується на одиницю.
При видаленні запису виконуються наступні дії:
Пошук запису по ключу. Якщо запис не знайдений, то значить видаляти нічого не треба.
Реальне видалення запису в буфері, в який прочитана відповідна листова сторінка.
Якщо після виконання цієї підоперації розмір зайнятої в буфері області виявляється таким, що його сума з розміром зайнятої області в листових сторінках, що є лівим або правим братом даної сторінки, більше, чим розмір сторінки, операція завершується.
Інакше проводиться злиття з правим або лівим братом, тобто в буфері проводиться новий образ сторінки, що містить загальну інформацію з даної сторінки і її лівого або правого брата. Та листова сторінка, що стала непотрібною заноситься в список вільних сторінок. Відповідним образом коректується список листових сторінок.
Щоб усунути можливість доступу від кореня до звільненої сторінки, треба видалити відповідне значення ключа і посилання на звільнену сторінку з внутрішньої сторінки - її предка. При цьому може виникнути потреба в злитті цієї сторінки з її лівим або правими братами і т.д.
Граничним випадком є повне спустошення кореневої сторінки дерева, яке можливе після злиття останніх двох нащадків кореня. У цьому випадку коренева сторінка звільняється, а глибина дерева меншає на одиницю.
Як видно, при виконанні операцій вставки і видалення властивість збалансованості В-дерева зберігається, а зовнішня пам'ять витрачається досить економно.
Проблемою є те, що при виконанні операцій модифікації дуже часто можуть виникати розщеплення і злиття. Щоб добитися ефективного використання зовнішньої пам'яті з мінімізацією числа розщеплень і злиття, застосовуються більш складні прийоми, в тому числі:
попереджуючі розщеплення, тобто розщеплення сторінки не при її переповненні, а трохи раніше, коли міра заповненості сторінки досягає деякого рівня;
переливання, тобто підтримка рівномірного заповнення сусідніх сторінок;
злиття 3-в-2, тобто породження двох листових сторінок на основі вмісту трьох сусідніх.
Потрібно помітити, що при організації мультидоступу до В-дерев, характерного при їх використанні в СУБД, доводиться вирішувати ряд нетривіальних проблем. Звичайно, грубі рішення очевидні, наприклад монопольне захоплення В-дерева на все виконання операції модифікації. Але існують і більш тонкі рішення, розгляд яких виходить за межі нашого курсу.
І останнє зауваження відносно В-дерев. У літературі вигляд розглянутих нами дерев прийнято називати В* або В+-деревами.
9.2.2. Хешування
Альтернативним і все більш популярним підходом до організації індексів є використання техніки хешування. Це дуже обширна тема, яка заслуговує окремого розгляду. Ми обмежимося лише декількома зауваженнями. Загальною ідеєю методів хешування є застосування до значення ключа деякої функції згортки (хеш-функції), що виробляє значення меншого розміру. Згортка значення ключа потім використовується для доступу до запису.
У самому простому, класичному випадку, згортка ключа використовується як адреса в таблиці, що містить ключі і записи. Основною вимогою до хеш-функції є рівномірний розподіл значення згортки. При виникненні колізій (одна і та ж згортка для декількох значень ключа) утворяться ланцюжки переповнення. Головним обмеженням цього методу є фіксований розмір таблиці. Якщо таблиця заповнена дуже сильно або переповнена, але виникне дуже багато ланцюжків переповнення, і головна перевага хешування - доступ до запису майже завжди за одне звернення до таблиці - буде втрачено. Розширення таблиці вимагає її повної переробки на основі нової хеш-функції (зі значенням згортки більшого розміру).
У разі баз даних такі дії є абсолютно неприйнятними. Тому звичайно вводять проміжні таблиці-довідники, що містять значення ключів і адреси записів, а самі записи зберігаються окремо. Тоді при переповненні довідника потрібна тільки його переробка, що викликає менше накладних витрат.
Щоб уникнути потреби в повної переробки довідників, при їх організації часто використовують техніку В-дерев з розщепленнями і злиттям. Хеш-функція при цьому міняється динамічно, в залежності від глибини В-дерева. Шляхом додаткового технічного хитрування вдається добитися збереження порядку записів у відповідності зі значеннями ключа. Загалом методи В-дерев і хешування все більш зближуються.
9.3. Журнальна інформація
Структура журналу звичайно є суто приватною справою конкретної реалізації. Ми відмітимо тільки самі загальні властивості.
Журнал звичайно являє собою чисто послідовний файл із записами змінного розміру, які можна переглядати в прямому або зворотному порядку. Обміни виробляються стандартними порціями (сторінками) з використанням буфера оперативної пам'яті. У грамотно організованих системах структура (і тим більше, значення) журнальних записів відома тільки компонентам СУБД, відповідальним за журналізацію і відновлення. Оскільки вміст журналу є критичним при відновленні бази даних після збоїв, до ведення файла журналу пред'являються особливі вимоги по частині надійності. Зокрема, звичайно прагнуть підтримувати дві ідентичні копії журналу на різних пристроях зовнішньої пам'яті.
9.4. Службова інформація
Для коректної роботи підсистеми управління даними у зовнішній пам'яті необхідно підтримувати інформація, яка використовується тільки цією підсистемою і не видна підсистемі язикового рівня. Набір структур службової інформації залежить від загальної організації системи, але звичайно потрібна підтримка наступних службових даних:
Внутрішні каталоги, що описують фізичні властивості об'єктів бази даних, наприклад, число атрибутів відношення, їх розмір і, можливо, типи даних; опис індексів, визначених для даного відношення і т.д.
Описувачі вільної і зайнятої пам'яті в сторінках відношення. Така інформація потрібно для знаходження вільного місця при занесенні кортежу. Окремо доводиться вирішувати задачу пошуку вільного місця у разах некластеризованих і кластеризованих відносин (в останньому випадку доводиться додатково використати кластеризований індекс). Як ми вже відмічали, нетривіальною є проблема звільнення сторінки в умовах мультидоступу.
Скріплення сторінок одного відношення. Якщо в одному файлі зовнішньої пам'яті можуть розташовуватися сторінки декількох відносин (звичайно до цього прагнуть), то треба якимсь чином зв'язати сторінки одного відношення. Тривіальний спосіб використання прямих посилань між сторінками часто приводить до ускладненнями при синхронізації транзакцій (наприклад, особливо важко звільняти і заводити нові сторінки відношення). Тому стараються використати непряме скріплення сторінок з використанням службових індексів. Зокрема, відомий загальний механізм для опису вільної пам'яті і скріплення сторінок на основі В-дерев.
© 2014 - 2019 BigLib.info — это сокращение от Big Library (большая библиотека).
Целью создания этого сайта было сделать украинскую литературу доступной для всех, кто желает ее читать.
Использование любых материалов сайта без согласования с администрацией запрещено.
Обратная связь