uk %D0%A1%D1%82%D1%80%D1%83%D0%BA%D1%82%D1%83%D1%80%D0%B8 %D0%B1%D0%B0%D0%B7 %D0%B4%D0%B0%D0%BD%D0%B8%D1%85

Таблиці даних та індекси можуть бути збережені на диск в одній з декількох форм, включаючи впорядковані/невпорядковані плоскі файли, ISAM, хеш файли, хеш-таблиці, або B+ дерева. Кожна форма має свої особливі переваги та недоліки. Найбільш часто використовувані форми B+ дерева і ISAM^[1] (англ. Indexed Sequential Access Method — індексно-послідовний метод доступу). Такі форми або структури є одним з аспектів загальної схеми, яка використовується рушієм бази даних для зберігання інформації.

Невпорядкована плоска база даних

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

Невпорядковане збереження, як правило, зберігає записи в порядку, в якому вони додані. Таке зберігання забезпечує гарну ефективність при виконанні операції по додаванню нових даних ( $O\left(1\right)$ ), але погану ефективність під час пошуку ( $O\left(n\right)$ ).

На практиці пошук працює швидше ніж ( $O\left(n\right)$ ), оскільки більшість баз даних використовують індекси з первинними ключами, в результаті час пошуку становить $O\left(\log n\right)$ або $O\left(1\right)$ для ключів, які збігаються зі зміщенням строк бази даних в системі зберігання.

Впорядкована плоска база даних

Впорядковане збереження, як правило, зберігає записи впорядковано, при додаванні нового запису вимагається зміна порядку або збільшення розміру файлу, в результаті ми маємо низьку ефективність при додаванні нового запису. Проте, упорядковане збереження забезпечує більш ефективний пошук, коли записи попередньо відсортовані, у результаті чого складність становить $O\left(\log n\right)$ .

Структуровані файли

Купа

Тут мається на увазі невпорядковані записи змінного розміру, не плутати з купою - структурою даних, що є впорядкованою.

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

Хеш-бакети

Бакетом (англ. bucket — відро) називають набір елементів хеш‑таблиці зі співпадаючими/близькими за значеннями хеш‑функціями.

Хеш-функції обчислюють адресу сторінки, в якій записи зберігаються на основі одного або декількох полів запису
- функції хешування вибрані, щоб переконатися, що адреси рівномірно розподілені по всьому адресному просторі
- 'місткість' як правило, від 40 % до 60 % від загального розміру файлу
- унікальність адрес не гарантується, так що необхідно виявляти колізії і використовувати механізми для їх вирішення
Відкрита адресація
Зв'язані/розв'язані переповнення
Плюси і мінуси:
- ефективний для точного збігу ключових полів
- не підходить для вилучення діапазону, яке вимагає послідовне зберігання
- підраховує, де зберігаються записи на основі полів запису
- хеш-функції забезпечують рівномірне поширення даних
- можливі колізії, тому необхідне їх виявлення і відновлення

B+ дерева

Є найбільш часто використовуваними на практиці.

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

Коли індекс є повним індексом, тоді файл даних не повинен бути рядкованим

Плюси та мінуси:
- універсальна структура даних послідовного і довільного доступу
- швидкий доступ
- ефективно підтримується exact, range, part key та pattern matches
- летючі файли не є ефективними, тому що індекс — динамічно збільшується і зменшується, коли таблиця збільшується і зменшується
- менше підходить для відносно стабільних файлів — в цьому випадку, ISAM є більш ефективним

Орієнтація даних

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

Див. також

↑ Indexed Sequential Access Method (ISAM). www.ibm.com (амер.). Процитовано 8 серпня 2022.

[1] Indexed Sequential Access Method (ISAM). www.ibm.com (амер.). Процитовано 8 серпня 2022.

[1]

Структури баз даних