Будь-які дані можуть бути віднесені до одного з двох типів: основному (простому), форма подання якого визначається архітектурою ЕОМ, або складного, що конструюються користувачем для вирішення конкретних завдань.
Дані простого типу це - символи, числа і т.п. елементи, подальше дроблення яких не має сенсу. З елементарних даних формуються структури (складні типи) даних.
· Масив (функція з кінцевої областю визначення) - проста сукупність елементів даних одного типу, засіб оперування групою даних одного типу. Окремий елемент масиву задається індексом. Масив може бути одновимірним, двовимірним і т.д. Різновидами одновимірних масивів змінної довжини є структури типу кільце, стек, чергу і двостороння чергу.
· Запис (декартовій твір) - сукупність елементів даних різного типу. У найпростішому випадку запис містить постійну кількість елементів, які називають полями. Сукупність записів однакової структури називається файлом. (Файлом називають також набір даних у зовнішній пам'яті, наприклад, на магнітному диску). Для того. щоб мати можливість брати з файлу окремі записи, кожного запису присвоюють унікальне ім'я або номер, який служить її ідентифікатором і розташовується в окремому полі. Цей ідентифікатор називають ключем.
Такі структури даних як масив або запис займають в пам'яті ЕОМ постійний обсяг, тому їх називають статичними структурами. До статичних структурам відноситься також безліч.
Мал. 1.1. Класифікація типів даних
Вище ми розглянули кілька типів структур, які є сукупностями елементів даних: масив, дерево, запис. Більш складний тип даних може включати ці структури в якості елементів. Наприклад, елементами запису може бути масив, стек, дерево і т.д.
Існує велика різноманітність складних типів даних, але дослідження, проведені на великій практичному матеріалі, показали, що серед них можна виділити кілька найбільш загальних. Узагальнені структури називають також моделями даних. тому вони відображають уявлення користувача про дані реального світу.
Будь-яка модель даних повинна містити три компоненти:
1. структура даних - описує точку зору користувача на представлення даних.
2. набір допустимих операцій. виконуваних на структурі даних. Модель даних передбачає, як мінімум, наявність мови визначення даних (МОД), що описує структуру їх зберігання, і мови маніпулювання даними (ЯМД), що включає операції вилучення та модифікації даних.
3. обмеження цілісності - механізм підтримки відповідності даних предметної області на основі формально описаних правил.
В процесі історичного розвитку в СУБД використовувалося наступні моделі даних:
Останнім часом все більшого значення набуває об'єктно-орієнтований підхід до представлення даних.
Питання представлення даних тісно пов'язані з операціями, за допомогою яких ці дані обробляються. До числа таких операцій відносяться: вибірка, зміна, включення і виключення даних. В основі всіх перерахованих операцій лежить операція доступу. яку не можна розглядати незалежно від способу подання.
У завданнях пошуку передбачається, що всі дані зберігаються в пам'яті з певною ідентифікацією і, кажучи про доступ, мають на увазі, перш за все, доступ до даних (званим ключами), однозначно ідентифікує пов'язані з ними сукупності даних.
Нехай нам необхідно організувати доступ до файлу, який містить набір однакових записів, кожна з яких має унікальне значення ключового поля. Найпростіший спосіб пошуку - послідовно переглядати кожну запис в файлі до тих пір, поки не буде знайдена та, значення ключа якої задовольняє критерію пошуку. Очевидно, цей спосіб досить неефективний, оскільки записи в файлі не впорядковані за значенням ключового поля. Сортування записів у файлі також непридатна, оскільки вимагає ще більших витрат часу і повинна виконуватися після кожного додавання записи. Тому, надходять у такий спосіб - ключі разом з покажчиками на відповідні записи в файлі копіюють в іншу структуру, яка дозволяє швидко виконувати операції сортування і пошуку. При доступі до даних спочатку в цій структурі знаходять відповідне значення ключа, а потім по зберігається разом з ним вказівником отримують запис з фала.
Існують два класи методів, що реалізують доступ до даних по ключу:
· Методи пошуку по дереву,
1.2.1.Методи пошуку по дереву
Визначення: Деревом називається кінцеве безліч, що складається з одного або більше елементів, які називаються вузлами, таких, що:
1.между вузлами має місце відношення типу "вихідний - породжений";
2.Есть тільки один вузол, який не має вихідного вузла. Він називається коренем;
3.Все вузли за винятком кореня мають тільки один вихідний; кожен вузол може мати кілька породжених вузлів;
4.отношеніе "вихідний - породжений" діє тільки в одному напрямку, тобто жоден нащадок деякого вузла не може стати для нього предком.
Число породжених окремого вузла (число піддерев даного кореня) називається його ступенем. Вузол з нульовим ступенем називають листом або кінцевим вузлом. Максимальне значення ступеня всіх вузлів даного дерева називається ступенем дерева.
Якщо в дереві між породженими вузлами, що мають загальний вихідний, вважається істотним їх порядок, то дерево називається впорядкованим. У завданнях пошуку майже завжди розглядаються впорядковані дерева.
Впорядковане дерево, ступінь якого не більше 2 називається бінарним деревом. Бінарне дерево особливо часто використовується при пошуку в оперативній пам'яті. Алгоритм пошуку: спочатку аргумент пошуку порівнюється з ключем, що знаходяться в корені. Якщо аргумент збігається з ключем, пошук закінчений, якщо ж не збігається, то в разі, коли аргумент виявляється менше ключа, пошук триває в лівому поддереве, а в разі, коли більше ключа - в правом поддереве. Збільшивши рівень на 1, повторюють порівняння, вважаючи поточний вузол коренем.
Приклад: Нехай дано список студентів, що містить їхні прізвища і середній бал успішності (див. Таблицю 1.1). Як ключ використовується прізвище студента. Припустимо, що всі записи мають фіксовану довжину, тоді як покажчик можна використовувати номер запису. Зсув записи в файлі в цьому випадку буде обчислюватися як ([номер_запісі] -1) * [дліна_запісі]. Нехай аргумент пошуку "Петров". На малюнку 1.2 показано одне з можливих для цього набору даних бінарне дерево пошуку і шлях пошуку.
Мал. 1.2. Пошук за бінарним дереву
Зауважимо, що тут використовується наступне правило порівняння строкових змінних: вважається, що значення символу відповідає його порядковому номеру в алфавіті. Тому "І" менше "К", а "К" менше "С". Якщо поточні символи в порівнюваних рядках збігаються, то порівнюються символи в наступних позиціях.
Бінарні дерева особливо ефективні в разі, коли безліч ключів заздалегідь невідомо, або коли це безліч інтенсивно змінюється. Очевидно, що при змінному безлічі ключів краще мати збалансоване дерево.
Визначення: Бінарне дерево називають збалансованим (balanced), якщо висота лівого піддерева кожного вузла відрізняється від висоти правого піддерева не більше ніж на 1.
При пошуку даних у зовнішній пам'яті дуже важливою є проблема скорочення числа переміщень даних з ВЗП в оперативну пам'ять. Тому, в даному випадку в порівнянні з бінарними деревами більш вигідними виявляться сильно розгалужені дерева - тому що їх висота менше, то при пошуку буде потрібно менше звернень до зовнішньої пам'яті. Найбільше застосування в цьому випадку отримали По-дерева (В - balanced)
Визначення: В-деревом порядку n називається сильно гілкуються дерево ступеня 2n + 1, що володіє наступними властивостями:
- Кожен вузол, за винятком кореня, містить не менше n і не більше 2n ключів.
- Корінь містить не менше одного і не більше 2n ключів.
- Все листя розташовані на одному рівні.
- Кожен проміжний вузол містить два списки: упорядкований по зростанню значень список ключів і відповідний йому список покажчиків (для листових вузлів список покажчиків відсутня).
Для такого дерева:
· Порівняно просто може бути організований послідовний доступ, тому що все листя розташовані на одному рівні;
· При додаванні і зміні ключів всі зміни обмежуються, як правило, одним вузлом.
Мал. 1.3.Сбалансірованное дерево
В-дерево, в якому справжні значення містяться тільки в листі (кінцевих вузлах), називається В + - деревом. У внутрішніх вузлах такого дерева містяться ключі-роздільники, що задають діапазон зміни ключів для піддерев.
R-дерево (R -Tree) це індексна структура для доступу до просторових даних, запропонована А. Гуттманн (Каліфорнійський університет, Берклі). R-дерево допускає довільне виконання операцій додавання, видалення та пошуку даних без періодичної переиндексации.
Для представлення даних використовуються записи, кожна з яких має унікальний ідентифікатор (tuple-identifier). У кожному кінцевому вузлі (аркуші) дерева міститься запис виду (I, tuple-identifier). де I - n -мірний паралелепіпед, що містить покажчики на просторові дані (його також називають minimal bounding rectangle. MBR), а кожен елемент в tuple-identifier містить верхню і нижню межу паралелепіпеда у відповідному вимірі.
Некінцевим вузли містять записи виду (I, childnode-pointer). де I мінімальний обмежує паралелепіпед для MBR всіх вузлів, похідних по відношенню до даного. Childnode-pointer - це покажчик на похідні вузли.
Нехай M і m<= M/2 соответственно максимальное и мимимальное количество элементов, которое может быть размещено в узле. Тогда свойства R-дерева можно описать следующим образом:
· R-Tree є сильно збалансованим деревом, тобто все листя знаходяться на одному рівні.
· Кореневий вузол має, як мінімум, двох нащадків.
· Для кожного елемента (I, childnode-pointer) в некінцевим вузлі I є найменшим можливим параллелепипедом, тобто містить всі паралелепіпеди похідних вузлів.
· Кожен кінцевий вузол (лист) містить від m до M індексних записів.
· Для кожної індексного запису (I, tuple-identifier) в кінцевому вузлі I є параллелепипедом, який містить n -мірний об'єкт даних, на який вказує tuple-identifier.
1.2.2.Хешірованіе
Дамп БД Акорди