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

Таблиці даних та індекси можуть бути збережені на диск в одній з декількох форм, включаючи впорядковані/невпорядковані плоскі файли, ISAM, хеш файли, хеш-таблиці, або B+ дерева. Кожна форма має свої особливі переваги та недоліки. Найбільш часто використовувані форми B+ дерева і ISAM (англ. 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+ дерево

B+ дерева

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

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

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

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

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

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

Див. також

• Індекс таблиці бази даних
• Плоскі бази даних
• Різниця між ISAM та B+ деревами на прикладах