ку в упорядкованому масиві кількість циклів пошуку - log 2 N, де N - кількість записів у таблиці. Але сортування виробляють лише по одному полю. Після скоєння будь-якого дії над записами (додавання, зміни, видалення) приходиться робити упорядкування (пересортовування) таблиці, а число перестановок зростає в геометричній прогресії при збільшенні кількості записів.
Індексування. Індекси - це спеціальні конструкції, які дозволяють швидко знайти адресу потрібного запису і в даний час вони широко застосовуються на практиці. На одну таблицю можна створювати кілька індексів. Як приклад можна розглянути рекомендації щодо застосування індексів у ORACLE. Вони зводяться до наступного: рекомендується використовувати індекси для забезпечення унікальності записів; для прискорення вибірки даних; задавати індекси для тих полів, вибірку по яких проводиться найчастіше, і при цьому рекомендується задавати на таблицю не більше трьох індексів, що дуже мало. На практиці застосовують індекси наступним чином: в системних полях таблиць використовують один або два індекси, і ще один індекс - на поля найменування. Область даних майже ніколи не індексують, хоча відбір найчастіше відбувається саме по цих полях. Крім того, на оновлення індексів також вимагає часу, а самі індекси займають місце на диску (а іноді розмір індексів перевищує розмір основної таблиці). p align="justify"> Тому індексація таблиць не надто допомагає: індекси займають місце (а іноді можуть перевищувати розміри таблиць), а в разі відбору за неіндексовані полю вони не допомагають.
Хешування. При хешуванні записів під таблицю відразу виділяють із запасом деякий обсяг пам'яті, і адреса записи в цьому обсязі - деяка функція від вмісту одного з полів запису (хеш-функція). Хешування також проводять по одному полю. Недоліки цього способу: необхідність в надлишковій резервуванні пам'яті. Крім цього, навіть при досить великому виділеному об'ємі пам'яті можлива ситуація, при якому на деякий місце претендують відразу дві або більше записів, тобто виникає колізія. br/>
1.2 Загальні основи
Хешування - перетворення вхідного масиву даних довільної довжини в вихідну бітову рядок фіксованої довжини. Такі перетворення також називаються хеш-функціями або функціями згортки, а їх результати називають хешем <# "justify"> Хеш-функція - це деяка функція h (K), яка бере якийсь ключ K і повертає адресу, за яким здійснюється пошук в хеш -таблиці, щоб отримати інформацію, пов'язану з K. Наприклад, K - це номер телефону абонента, а шукана інформація - його ім'я. Функція в даному випадку нам точно скаже, за якою адресою знайти шукане. p align="justify"> Колізія - це ситуація, коли h (K1) = h (K2), в той час як K1? K2. У цьому випадку, очевидно, необхідно знайти нове місце для зберігання даних. Очевидно, що кількість...
