Засоби прискорення доступу до даних
Засоби прискорення доступу до даних - розділ Електроніка, Обробка даних засобами електронних таблиць Сучасним суб.
Сучасним СУБД доводиться оперувати величезними масивами інформації, обсяги яких досягають часом десятків терабайт. Виконуючи запити тисяч користувачів, вони мають забезпечити невеликий, не більше кількох секунд час відгуку. СУБД не зможе ефективно працювати за таких умов, не використовуючи методів прискорення вибірки даних. Мета цих методів - уникнути повного перебору рядків таблиць БД при виконанні реляційних операцій, наприклад, при з'єднанні відносин або пошуку рядків, що задовольняють умові.
У сучасних СУБД використовуються два основні методи прискорення доступу до даних: індексування та хешування. Ці методи забезпечують кращий у порівнянні з іншими час пошуку та модифікації таблиць БД.
Метод індексування ґрунтується на використанні індексів. Індекс відносин дуже схожий на предметний покажчик книги. У такому покажчику наведено список упорядкованих за алфавітом термінів, що зустрічаються у книзі. Кожному терміну зіставлено сторінку чи сторінку, де він зустрічається. Зазвичай предметний покажчик займає трохи більше кількох сторінок. Якщо нам потрібно знайти місце в книзі, де термін розкривається, ми знаходимо його в предметному покажчику, це легко зробити - покажчик невеликий, крім того, всі терміни там упорядковані за абеткою. Потім ми читаємо номер сторінки, який відповідає терміну, розкриваємо книгу на ній і знаходимо потрібний абзац. Якби предметний покажчик був відсутній, нам довелося б перегортати всі сторінки, щоб знайти цікаве для нас місце, і ми витратили б значно більше часу.
Індекс бази даних – не аркушіпаперу, це спеціальна структура даних, створювана автоматично або на запит користувача. Загалом робота з ним виглядає так само, як і з предметним покажчиком. Різниця лише в тому, що СУБД все робить автоматично, користувач може навіть не знати, що вона використовує індекс. У книзі наводиться предметний покажчик слів, у БД на формування індексу може бути використаний будь-який атрибут відносини, зокрема і складової. В індексі значення атрибута зберігаються впорядковано (за зростанням або зменшенням), кожному значенню відповідає покажчик на рядок відношення, яке його містить (аналог номера сторінки в предметному покажчику). Індекс займає значно менший, ніж таблиця, обсяг, тому навіть повний перебір значень у ньому вимагатиме менше часу, ніж зчитування та пошук інформації. Крім того, значення в індексі зберігаються впорядковано, що дозволяє швидко прискорити пошук потрібного рядка. Індекси дозволяють вибирати рядки відносин, значення атрибута, що індексується, належить деякому заданому інтервалу.
Для одного відношення можна створити кілька індексів. Якщо різні відносини містять однакові атрибути, то їм може бути сформований мультииндекс. У ньому кожному значенню загального атрибута відповідає кілька посилань, кожна з яких вказує на рядок з таким значенням у тому чи іншому відношенні. Мультиндекс застосовуються для оптимізації виконання операції з'єднання відносин.
Ще один цікавий підхід, що застосовується для підвищення ефективності доступу до даних, - хешування (hashing). Для методу хешування, на жаль, немає життєвого аналога, тому пояснити його «на пальцях» навряд чи вдасться. Основна ідея хешування – організація асоціативної пам'яті для зберігання рядків таблицівизначення місця рядка в таблиці за значеннями одного або декількох її ключових атрибутів. Місце рядка обчислюється хеш-функцією, аргументи якої значення атрибутів, а результат - ціле число в діапазоні номерів рядків таблиці. Ідеальна хеш-функція має давати різні значення номерів рядків для різних ключових атрибутів. Однак побудувати таку хеш-функцію – справа трудомістка і не завжди можлива.
Насправді використовуються, зазвичай, прості хеш-функції. Для цілих атрибутів як хеш-функції може бути використаний, наприклад, залишок від поділу на просте число:
деf- хеш-функція,k- цілісний атрибут, ар- просте число.
Якщо ключовий атрибут – рядок символів, то для обчислення хеш-функції вибирається найбільш підходящий у конкретній ситуації метод перетворення рядка на число, наприклад, обчислення контрольної суми.
Доступ до даних при хешуванні здійснюється так. На початку роботи з БД таблиця складається з порожніх рядків. Коли рядок з даними заноситься до таблиці, обчислюється значення хеш-функції для її атрибутів, і результат трактується як номер рядка відношення, до якого вона має бути записана. Якщо цей рядок вже зайнятий, то за деяким алгоритмом проводиться перевірка наступних рядків таблиці доти, доки не буде виявлено вільне місце (при цьому, як правило, вважається, що таблиця має кільцеву структуру). У це місце і міститься рядок, що записується. Для пошуку даних використовується аналогічний алгоритм. Спочатку обчислюється значення хеш-функції для необхідного значення ключового атрибуту та перевіряється рядок таблиці, номер якого обчислений хеш-функцією. Якщо значення атрибута, за яким відбувається доступ, відповідає значенню ключа рядка, пошук закінчується. Ув іншому випадку перевіряються наступні рядки таблиці до виявлення кортежу з потрібним значенням або порожнього рядка. Порожній рядок свідчить про відсутність кортежу з потрібним значенням ключа в таблиці – процедура занесення даних обов'язково використала б її, якби потрібний кортеж існував.
Хешування може використовуватися для пошуку рядків точного збігу значення атрибута кортежу з потрібним значенням ключа.