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

Цей розділ містить правописні, лексичні, граматичні, стилістичні або інші мовні помилки, які треба виправити. Ви можете допомогти вдосконалити цей розділ, погодивши його із чинними мовними стандартами. (квітень 2017)

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

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

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

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

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

Впорядкована плоска база даних[ред. | ред. код]

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

Структуровані файли[ред. | ред. код]

Купа[ред. | ред. код]

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

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

Хеш-бакети[ред. | ред. код]

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

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

B+ дерева[ред. | ред. код]

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

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

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

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

Орієнтація даних[ред. | ред. код]

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

Див. також[ред. | ред. код]

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

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