Динамічні бази даних
Зміст.
Зміни в версіях.
Повна версія розділу задається у вигляді: версія.подверсія.випуск.
Бази даних для вбудованих додатків.
Доступ до записів бази даних здійснюється з використанням ключа. Ключ являє собою набір окремих полів запису, за значенням яких і проводиться все операції: пошук запису, її додавання, видалення та інші. База даних може мати кілька ключів, дозволяючи здійснювати доступ з різних логічним шляхах. Деякі бази підтримують можливість застосування дубльованих ключів, коли кілька записів мають однакові значення всіх ключових полів. Однак працювати з такими даними досить незручно і слід настійно рекомендувати використання лише унікальних ключів. Якщо існуючих полів недостатньо для того, щоб сформувати такий ключ, доцільно додати поле, яке забезпечить унікальність ключа.
В якості базових операцій з даними будемо розглядати пошук запису по ключу, додавання нового запису, її видалення і перехід до наступної або попередньої в ключовому порядку записи. Для характеристики часу виконання базових операцій використовується параметр O (О велике), який характеризує відносний порядок необхідного числа елементарних машинних операцій в залежності від кількості записів бази (її розміру). Так, O (N) означає, що час виконання базової операції пропорційно розміру бази, а O (logN) вказує на те, що час операції збільшується лише пропорційно логарифму від числа записів бази.
Невпорядкований список.
У неврегульованих списку дані розміщуються в міру надходження без будь-якої сортування. У разі видалення запису на її місце може бути поміщена новий запис з довільним значенням ключа.
Тимчасові е характеристики і алгоритми операцій невпорядкованого списку:
Таким чином, всі основні операції з даними, розміщеними в неврегульованих списку, досить важкі - число необхідних елементарних операцій зростає пропорційно розміру бази. Проте, простота програмної реалізації такого списку цілком виправдовує його використання, коли число записів бази не перевищує близько ста. Відзначимо, що робота з неврегульованим списком алгоритмічно подібна використання умовних операторів if, else if для вибіркового доступу до звичайних даними.
Упорядкований масив з обмеженим діапазоном значень.
Тимчасові е характеристики і алгоритми операцій упорядкованого масиву з обмеженим діапазоном значень:
Відносний порядок часу виконання
Алгоритм виконання базової операції
Упорядкований масив даних.
Упорядкований масив є одним з варіантів класичної бази даних і не накладає обмежень ні на діапазон значень ключа, ні на число різних ключів. Можливі дві реалізації бази даних в такому масиві з точки зору організації ключових полів. Перший спосіб передбачає впорядкування всієї бази по первинному ключу, в якості якого використовується одне або кілька полів даних.
Інша реалізація передбачає поділ бази даних на НЕ впорядковане тіло і один або кілька впорядкованих ключових масивів. Такий підхід дає можливість сформувати кілька різних ключів. Крім того, знижуються витрати на додавання записів, якщо розмір не ключових даних досить великий. Недоліком такого рішення є необхідність доповнення кожній ключовій записи покажчиком і дублювання ключових полів в масиві даних. Якщо такого дублювання не здійснювати, то для повного складання записи бази буде потрібно введення зворотних покажчиків від даних на відповідні їм записи ключів.
Тимчасові е характеристики і алгоритми операцій упорядкованого масиву даних:
Пряма вибірка записи.
Пошук необхідного запису в базі здійснюється методом половинного ділення масиву ключа, або самої бази, якщо вона містить первинний ключ (алгоритм бінарного пошуку). Зверніть увагу, що час знаходження будь-якого запису бази має гарантовано логарифмічну залежність від її розміру O (logN). Це дозволяє прогнозувати максимальний час доступу до записів, що є помітною перевагою для вбудованих додатків. Не випадково алгоритм бінарного пошуку включений в багато стандартні бібліотеки мов програмування.
Однак, операції додавання і видалення записів пов'язані з необхідністю розсунення або змикання масиву, а тому досить важкі. Практичне обмеження на розмір бази, виконаної у вигляді упорядкованого масиву, становить близько десяти тисяч записів, що досить для більшості вбудованих додатків. У тих випадках, коли визначальним стає зниження витрат саме на операції додавання / видалення, доцільно розглянути можливість використання рішень на основі хеш-таблиць, структур даних типу дерев або спеціалізованих списків.
Програмна реалізація невпорядкованого списку.
У програмі наведена універсальна реалізація трьох базових операцій: пошуку, додавання і видалення записів. Оскільки невпорядкований список є мінімалістським способом організації бази даних, для його зберігання доцільно використовувати масив фіксованої довжини. Крім того, самі алгоритми нерідко реалізуються спеціалізованим чином. Так, в якості прапора вільного елементу масиву нерідко використовується виділений значення ключа, а контроль його дублювання може і не здійснюватися.
Деякі компілятори інтерпретують типи, що не містять ключового слова signed як без знакові. Це викликає змішані почуття, але оскільки факт має місце, доцільно застосовувати явне визначення знаковості (signed або unsigned).
Функція search_object (obj) здійснює пошук запису бази за значенням ключа. Алгоритм пошуку - повне сканування бази [so_4]. Для кожної активної (зайнятою) записи [so_5] порівнюється її ключ [so_6], при збігу якого функція позвращает не негативна число, що визначає елемент масиву шуканої записи. При невдалому завершенні пошуку повертається мінус 1 [so_9].
Функція add_object (obj) додає запис в базу даних. Контроль унікальності ключа змушує проводити повне сканування бази [ao_5]. При виявленні в одній з активних записів збігається значення ключа повертається помилка дублювання [ao_9]. Для занесення в базу нового запису фіксується перший виявлений вільне місце [ao_6, ao_7]. У разі, якщо такого в базі не виявилося, повертається помилка переповнення [ao_12]. В іншому випадку на виявленому вільному місці розміщується новий запис [ao_13, ao_14].
Функція delete_object (obj) позначає відповідну ключу запис бази [do_6] як вільну [do_7]. У разі, коли необхідний запис серед активних [do_5] не знайдено, повертається код помилки "запис не знайдено" [do_12].
При ініціалізації бази все її записи позначаються як і активні (вільні) [id_4].
Упорядкований масив з первинним ключем.
В нашій реалізації використовується доповнення бази даних кінцевими записами, які містять максимальні і мінімальні значення всіх ключових полів і відповідно є першим і останнім елементами упорядкованого масиву бази. Це дозволяє спростити і оптимізувати алгоріми пошуку робочих записів, зберігаючи самі кінцеві записи недоступними. Причому забезпечується можливість додавання в базу робочих записів, також містять граничні значення ключових полів. Всі наведені алгоритми роботи з базою припускають обов'язкову наявність кінцевих результатів. Рішення, що передбачає такі записи, може виявитися вельми корисним і при використанні класичних баз даних.
Програма звертається до функцій стандартних бібліотек С. З
Деякі компілятори інтерпретують типи, що не містять ключового слова signed як без знакові. Це викликає змішані почуття, але оскільки факт має місце, доцільно застосовувати явне визначення знаковості (signed або unsigned).
Функція key_object (obj1, obj2) визначає співвідношення ключів двох записів бази. Спочатку порівнюється перше поле ключів [ko_2, ko_3], що має більш високий пріоритет. Якщо це поле в обох ключів однаково, здійснюється порівняння другого поля [ko_4, ko_5]. За результатами цих порівнянь приймається рішення про співвідношення ключів (більше, менше, дорівнює) двох записів бази.
Функція search_object (obj) здійснює бінарний пошук запису бази за значенням ключа, що міститься в об'єкті obj. покажчик на який є вхідним параметром функції. При виявленні в базі даних шуканої записи повертається невід'ємне число - положення (зміщення) записи щодо початку бази [so_12]. Якщо ж такої не виявлено, функція повертає мінус 1 [so_14].
Функція insert_object (obj, pos) виробляє вставку нового запису, положення якої (зміщення відносно початку бази) задається параметром pos. Для цього здійснюється розсунення бази: інкремент номера максимальної записи [io_4] і цикл копіювання масиву бази [io_5. io_7]. Потім на позицію, що звільнилася заноситься новий запис [io_8]. Саме необхідність проведення раздвижки при додаванні запису обумовлює пропорційну залежність O (N) відносного числа операцій від розміру бази.
Функція add_object (obj) здійснює комплекс операцій по додаванню записи в базу. У разі, якщо виділений раніше масив пам'яті вже заповнений [ao_6]. робиться запит додаткового обсягу пам'яті [ao_8. ao_10]. Параметр INC_OBJECTS. задає інкремент розміру бази по мірі її заповнення, вибирається таким, щоб звернення до функції виділення пам'яті [ao_10] було не надто частим (це дуже витратна операція), а з іншого боку, в базі не залишалося б занадто багато порожніх записів (їх число може досягати INC_OBJECTS-1). Помилка додавання пам'яті може виникати як при невдалому завершенні запиту [ao_10], так і в разі перевищення максимального розміру бази (не виконана умова [ao_9]).
Якщо всі необхідні операції по виділенню додаткової пам'яті завершилися успішно, проводиться бінарний пошук місця [ao_18. ao_26], в яку необхідно вставити новий запис. При цьому контролюється можливе дублювання ключа і при виявленні такого повертається код помилки [ao_25]. У разі успішного знаходження положення нового запису виробляється її вставка [ao_27]. Як і в функції пошуку записи по ключу, алгоритм адаптований для випадку, коли в базі присутні кінцеві записи, причому їх наявність є обов'язковим.
Функція delete_object (obj) видаляє з бази запис із значенням ключа, що містяться в об'єкті obj. покажчик на який передається в якості вхідного параметра. Якщо шукана запис виявлена, проводиться зрушення бази, що видаляє цей запис [цикл do_6], і номер максимальної записи зменшується на одиницю [do_9].
Упорядкований масив із зовнішніми ключами.
В нашій реалізації бази даних використовується додаток масивів зовнішніх ключів кінцевими записами, які містять максимальні і мінімальні значення всіх полів, будучи першим і останнім елементами упорядкованого масиву ключа. Це дозволяє спростити і оптимізувати алгоріми пошуку по ключу, зберігаючи самі кінцеві записи недоступними. Причому забезпечується можливість додавання в базу робочих записів, також містять граничні значення ключових полів. Всі наведені алгоритми роботи з базою припускають обов'язкову наявність кінцевих результатів. Рішення, що передбачає такі записи, може виявитися вельми корисним і при використанні класичних баз даних.
Програма звертається до функцій стандартних бібліотек С. З
Деякі компілятори інтерпретують типи, що не містять ключового слова signed як без знакові. Це викликає змішані почуття, але оскільки факт має місце, доцільно застосовувати явне визначення знаковості (signed або unsigned).
Функція key_1_compare (k1, k2) визначає співвідношення перших ключів бази. Спочатку порівнюється перше поле ключів [k1c_2, k1c_3], що має більш високий пріоритет. Якщо це поле в обох ключів однаково, здійснюється порівняння другого поля [k1c_4, k1c_5]. За результатами цих порівнянь приймається рішення про співвідношення ключів (більше, менше, дорівнює).
Функція search_object_k1 (key) здійснює бінарний пошук запису за значенням першого ключа key. покажчик на який є вхідним параметром функції. При виявленні в базі ключів шуканої записи повертається невід'ємне число - положення (зміщення) відповідного запису тіла бази щодо її початку [so1_12]. Якщо підходящої ключовий записи не виявлено, функція повертає мінус 1 [so1_14].
Функція search_object_k2 (key) здійснює бінарний пошук запису за значенням другого ключа key. покажчик на який є вхідним параметром функції. При виявленні в базі ключів шуканої записи повертається невід'ємне число - положення (зміщення) відповідного запису тіла бази щодо її початку [so2_10]. Якщо підходящої ключовий записи не виявлено, функція повертає мінус 1 [so2_12]. Оскільки другий ключ не є складовим, використовуються операції безпосереднього порівняння значення ключового поля [so2_8, so2_9].
Функція add_object (obj) здійснює комплекс операцій по додаванню записи в базу. У разі, якщо виділені раніше масиви пам'яті вже заповнені ([ao_8] для тіла бази, [ao_20] для масивів ключів). робиться запит додаткового обсягу пам'яті [ao_10. ao_12] для тіла бази і [ao_23. ao_26] для ключів. Параметр INC_OBJECTS. задає інкремент розміру всіх масивів бази по мірі її заповнення, вибирається таким, щоб увійти до меню виділення пам'яті [ao_12, ao_25, ao_26] були не надто частими (це дуже витратна операція), а з іншого боку, в базі не залишалося б занадто багато порожніх записів (їх число може досягати INC_OBJECTS-1). Помилка додавання пам'яті може виникати як при невдалому завершенні запитів, так і в разі перевищення максимального розміру бази (не виконані умови [ao_11, ao_24]).
Якщо всі необхідні операції по виділенню додаткової пам'яті завершилися успішно, проводиться бінарний пошук місця вставки ключових записів: [ao_35. ao_45] для першого ключа і [ao_46. ao_54] для другого. При цьому контролюється можливе дублювання по кожному ключу і при виявленні такого повертається код помилки [ao_44] - перший ключ, [ao_53] другий. У разі успішного завершення всіх перевірок проводиться вставка нового запису в кінець тіла бази [ao_56] і установ відповідних покажчиків в ключах [ao_57, ao_58]. Потім здійснюється розсунення баз ключів [ao_60, ao_64] і вони заносяться в певні для них позиції [ao_63, ao_67]. Як і в функції пошуку записи по ключу, алгоритм адаптований для випадку, коли в базі присутні кінцеві записи, причому їх наявність є обов'язковим.
Функція delete_object (obj) видаляє з бази запис зі значеннями ключів, що містяться в об'єкті obj. покажчик на який передається в якості вхідного параметра. Шукана запис шукається незалежно по кожному ключу [do_12, do_26]. Якщо вона виявлена в обох масивах ключів, проводиться їх зрушення: цикл [do_37] видаляє перший ключ, а [do_40] другий. Відповідно номер максимальної записи ключових баз зменшується на одиницю [do_43].
На тому можна було б і завершити видалення - відповідний запис тепер недоступна при пошуку по будь-якому ключу. Але в такому випадку в тілі бази будуть накопичуватися неробочі записи, тому має сенс також їх видаляти. Це досить трудомістка операція. Спочатку проводиться зрушення тіла бази [do_44] (розташування видаляється записи було зафіксовано в [do_36]). Потім для підтримання спроможності посилань ключів необхідно здійснити відповідне коригування (декремент) покажчиків, що посилаються на записи тіла бази, які розміщувалися слідом за віддаленої [do_48]. Таким чином, тяжкість повного видалення запису досить висока. Однак в додатках ця операція зазвичай найбільш рідкісна і з підвищеним обсягом обчислювальної роботи цілком можна змиритися.