Хешування БАЗИ ДАНИХ

Хешування (Зване також хеш-адресацією, а іноді, не зовсім правильно, хеш-індексацією) являє собою метод забезпечення швидкого прямого доступу до конкретної записи з урахуванням заданого значення певного поля Розглянуте поле звичайно (але не обовязково) є первинним ключем Нижче наведено короткий опис методу хешування

■ Кожен запис збожеволіє в базу даних в таке місце, адреса якого (тобто ідентифікатор запису або, можливо, просто номер сторінки) обчислюється так деяка функція (Нази ваемая хеш-функцією) від значення певного поля цього запису (зване хешірованного полем – Hash field, або іноді хешірованного ключем – Hash key але останній термін у даному додатку не використовується) Адреса, обчислений за допомогою хеш-функції, називається хеши ванням адресою

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

■ Для подальшої вибірки записи з використанням значення хешірованного поля СУБД проводить такі ж обчислення, як і колись, і видає диспетчеру файлів команду читання / запису по обчисленому адресою

В якості простого прикладу припустимо, що значення номерів постачальників становлять S100, S200, S300, S400, S500 (а не SI, S2, S3, S4, S5) і для кожного запису постачальника потрібна ціла окрема сторінка, а також розглянемо наступну хеш-функцію:

хешірованного адресу (тобто номер сторінки) = залишок після поділу числової частини значення S # на 13

Це – найпростіший приклад дуже широко вживаного класу хеш-функцій, які називаються функціями хешування з використанням залишку від ділення,або простохеш-функціями розподіл / залишок – Division / remainder hash function (З причин, опис яких виходить за рамки даного додатка, в якості подільника в хеш-функції «розподіл / залишок зазвичай використовується просте число, як в даному прикладі) Таким чином, номери сторінок для цих пяти постачальників, відповідно, приймають значення 9, 5, 1, 10, 6, в результаті чого створюється відображення між номерами постачальником і номерами сторінок, показане на рис Г 14

З наведеного вище опису має бути очевидно, що хешування відрізняється від індексації по наступного важливого ознакою – в той час як будь-який конкретний файл може мати будь-яку кількість індексів, для нього може бути передбачено не більше однієї хешірованного структури Інакше цю думку можна висловити таким чином – файл може мати будь-яку кількість індексованих полів, але тільки одне хешірованное полі (Дане зауваження відноситься до методу

прямого хешування– Direct hashing На відміну від цього, з файлом може бути повязано довільну кількість структур непрямого хешування – Indirect hash Див [Г24])

Розглянутий приклад показує не тільки принципи роботи методу хешування, а й

дозволяє зрозуміти, чому потрібно хеш-функція Було б теоретично можливо використовувати

“Ідентичну хеш-функцію, іншими словами, як хешірованного адреси безпосередньо

застосовувати значення первинного ключа (при цьому, безумовно, мається на увазі, що первинний ключ

є числовим) Але такий метод зазвичай не може використовуватися на практиці, оскільки

діапазон можливих значень первинного ключа найчастіше набагато перевищує діапазон доступних

адрес Наприклад, припустимо, що фактично номера постачальників знаходяться в межах від S000 до

S999, як показано в наведеному вище прикладі У такому випадку кількість можливих різних

номерів постачальників дорівнюватиме 1000, тоді як насправді кількість діючих постачальників приблизно дорівнює 10 Тому для запобігання значних непродуктивних

витрат простору памяті в ідеалі слід знайти таку хеш-функцію, яка буде перетворювати

будь-яке значення в діапазоні 000-999 в одне значення (скажімо) в діапазоні 0-9 Але для створення

невеликого резерву для майбутнього зростання зазвичай прийнято розширювати цільовий діапазон адрес приблизно

на 20% саме тому в даному прикладі обрана функція, яка виробляє значення в

діапазоні 0-12, а не 0-9

Цей приклад також показує один з недоліків хешування: фізична послідовність записів у файлі майже напевно не буде збігатися з послідовністю первинних ключів, а також, зрозуміло, з будь-якої іншої послідовністю, яка має якусь осмислену логічну інтерпретацію (Крім того, між поспіль йдуть записами можуть перебувати проміжки довільних розмірів) Насправді, фізична послідовність записів у файлі з хешірованного структурою найчастіше (але не завжди) розглядається як що не представляє какойлибо певній логічній послідовності

Примітка Безумовно, завжди можливо накласти будь-яку бажану логічну послідовність на хешірованного файл за допомогою індексу а насправді, можливо накласти кілька таких послідовностей за допомогою декількох індексів, по одному на кожну таку послідовність Гляньте [Г35] і [Г37], де розглядаються можливості створення схем хешування, що зберігають логічну послідовність записів в доглянутому файлі

Ще одним недоліком методу хешування в цілому є те, що завжди залишається можливість колізій, тобто появи двох або кількох різних записів (синонімів), хешування яких відбувається по одному і тому ж адресою Наприклад, припустимо, що файл постачальників (з даними про постачальників S100, S200 і тд) включає також постачальника з номером S1400 При використанні хешфункціі, розглянутої в даному прикладі (поділити на 13 і взяти залишок), запис цього постачальника буде конфліктувати із записом постачальника S100, що знаходиться по хешірованному адресою

9 Таким чином, очевидно, що хеш-функція в тому вигляді, в якому вона тут описана, не забезпечує нормальної роботи і повинна бути якимось чином доповнена, щоб можна було впоратися з проблемою колізій

У термінах даного первісного прикладу одним можливим доповненням є те, що залишок від ділення на 13 повинен розглядатися не як хешірованного адресу як такої, а швидше як відправна точка для послідовного перегляду Таким чином, щоб вставити запис постачальника S1400 (за умови, що записи постачальників S100-S500 вже існують), необхідно перейти на сторінку 9 і виконати пошук вперед від цієї позиції до першої вільної сторінки Припустимо, що нова запис постачальника буде збережена на сторінці 11 Надалі для вибірки даних про це постачальнику необхідно пройти аналогічну процедуру Такий метод, званий лінійним пошуком (Linear search), може виявитися цілком прийнятним, якщо на кожній сторінці зберігається трохи записів (як зазвичай і буває на практиці) Припустимо, що на кожній сторінці може знаходитися п записів У такому випадку всі п перших записів з одним і тим же хешірованного адресою р, що потрапили в колізію, будуть збережені на сторінці р, а лінійний пошук серед цих записів буде повністю обмежуватися однією цій сторінкою Але наступна, (п +1)-я колізія, безумовно, призведе до того, що відповідний запис доведеться зберегти на якійсь окремій сторінці переповнення і буде потрібно ще одна операція вводу-виводу

Ще один підхід до вирішення проблеми колізій, який, мабуть, більш часто застосовується в реальних системах, полягає в тому, що результат використання хеш-функції, скажімо, а, розглядається не як адресу зберігання запису даних, але скоріше як точка привязки (Anchor point) Потім ця точка привязки з адресою зберігання а застосовується як початок ланцюжка покажчиків (або ланцюжка колізій– Collision chain), що звязує один з одним всі записи (або всі сторінки записів), у яких відбулася колізія за адресою а У кожній конкретній ланцюжку колізій записи, що потрапили в колізію, зазвичай зберігаються в послідовності значень хешірованного поля для спрощення подальшого пошуку

Джерело: Дейт К Дж, Введення в системи баз даних, 8-е видання: Пер з англ – М: Видавничий дім «Вільямс», 2005 – 1328 с: Ил – Парал тит англ

Схожі статті:


Сподобалася стаття? Ви можете залишити відгук або підписатися на RSS , щоб автоматично отримувати інформацію про нові статтях.

Коментарів поки що немає.

Ваш отзыв

Поділ на параграфи відбувається автоматично, адреса електронної пошти ніколи не буде опублікований, допустимий HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

*

*