Пояснити необхідність застосування індексів у базах даних, склад та структура індексів, хешування, бінарні дерева, B–дерева.

Організація пошуку: перегляд всієї бази; пошук за номером запису; дихотомія-інформація в файлі зберігається впорядкованою за ключами, розбивається но 2 частини. Для швидкого виконання пошуку підтримуються спеціальні службові структури, які наз. пошуковими або індексами.

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

Структура індексу -прийнятий в пошуковій системі порядок зберігання полів, визначаючих склад та логічні зв’язки використовуваного індексу. Є багато різних типів структур: зворотній список(інвертований фаил),хеш –значення слів, масиви дерев тощо.

Класифікація пошукових структур:

 

В, В^* В⁺

Хешування: хеш (змішувати,перемішувати).Головна ідея хеш доступу полягає у побудові ф-ї, яка б відображала множину значень ключів на множині значень адрес. Така ф-я наз. хеш-функцією.

Вимоги до хеш-функції:вона не повинна мати велику обч. Складність;повинна бути якомога біль однозначною.

Множ. значень ключів є більш потужною ніж множ. значень адрес.

h(k2)=h(k2), k1 = k2 Така ситуація наз. колізією.

Методи вирішення колізій: застос. внутрішня або зовнішня адресація. Внутрішня - передбачає створення хеш-області фікс. розміру для розв»язання колізій застосовується так званий пробінг

Записи, які утв. в результаті пробінгу наз. синонімів, які відповідають одним значенням хеш-фун-ї:F(k,i)=h(k)+L(i). Функція пробінгу повинна бути такою, щоб забезпечувати перегляд всієї хеш-області.

Зовнішня адресація - полягає в тому,що створюється зовнішня динамічна пам»ять. В цю память виштовхуються всі синоніми. Память є статичною, тобто має фіксований розмір. Ефективність доступу за допомогою хешування визначається довжиною ланцюгів-синонімів. Недоліки хешування: відсутність можливості звернення до БД за зростанням, або за зменшенням; фіксований розмір хеш-області і відповідно, вірність існування пустих комірок.

Бінарні дерева:Це дерево зі ступенем розгалуження 2. Кожен вузол має не більше 2 нащадків. Інформація в бінарному дереві є впорядкованою.Для них виконуються наступні умови:

Бінарне дерево є впорядкованим зверху вниз та зліва направо,кожен вузол склад. З 4 частин:ключ,адреса в бд,показчик.Бінарні дерева можуть вироджуватись.Для запобігання виродження дерева застосов їх балансування.Найбільш поширене-балансування по висоті. Дерево є збалансованим по висоті,якщо висота лівого та правого піддерев відрізняються не більше ніж на 1.Висота дерева-це кількість рівнів або найбільша кіл-ть дуг. Загальна кількість рівнів-log₂(N+1). Кожен вузол дерева має наступну структуру:

К- ключ, А-адреса в БД,

L-покажчик на ліве піддерево, R-покажчик на праве піддерево.

В-дерева:дозволяють підвищувати швидкість доступу.В-дерево зі ступенем 2м має наступні властивості: кожен вузол,окрім кореня, має не меньше m і не більше 2 m ключів; корень утримує не меньше 1 і не білше 2м ключів;кожен вузол,який має х ключів,має (х+1) наступних.

В-дерево ніколи не вироджується бо воно завжди заповнене не менше ніж на 50 %.Операції з В-деревом включ.операції розщеплення та операції переливання. В-дерево завжди збалансовано.

Структура вузла:

N-кількість ключів,

K_i-ключ,

A_i-адреса в БД,

a_i-адреса піддерева

В1-дерева відрізняються від В-дерева тим, що адреси записів у файлах БД розміщуються тільки на нижньому рівні,а на проміжних рівнях застосовуються ключі-роздільники.