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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

Таблиці та індекси можуть бути збережені на диск в одній з декількох форм, включаючи впорядковані/невпорядковані плоскі файли, ISAM, хеш файли, хеш-таблиці, або B+ дерева. Кожна форма має свої особливі переваги і недоліки. Найбільш часто використовувані форми B+ дерева і ІСАМ. Такі форми або структури є одним з аспектів загальної схеми, яка використовується ядром бази даних для зберігання інформації.

Невпорядковане збереження[ред. | ред. код]

Невпорядковане збереження, як правило, зберігає записи в порядку, в якому вони вставлені. Таке зберігання забезпечує гарну ефективність вводу (), але погану ефективність відновлення (). Як правило, таке відновлення краще, тому що, більшість баз даних використовують індекси з первинними ключами, в результаті чого відновлення п або для ключів, які такі ж, як у базі зміщення рядка в пам'яті системи.[джерело?]

Впорядковане збереження[ред. | ред. код]

Впорядковане збереження, як правило, зберігає записи впорядковано та дозволяє змінювати або збільшувати розмір файлу при вставці нового запису, в результаті ми маємо низьку ефективність вставки. Тим не менш, упорядковане збереження забезпечує більш ефективне відновлення запису, коли записи попередньо відсортовані, у результаті чого складністю є .[джерело?]

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

Файли куч[ред. | ред. код]

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

Heap файли є списками з невпорядкованними записами змінного розміру. Хоча і мають схожу назву, heap файли сильно відрізняються від таких же в пам'яті. В пам'яті heap є впорядкованими, на відміну від heap в фалі

Hash блоки[ред. | ред. код]

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

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

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

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

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

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

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

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

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