Хеш-Індексування

У певних ситуаціях виникає потреба у використанні індексу для ефективного пошуку інформації, але застосування B-tree індексу може бути надмірно складним і зайвим. У таких випадках більш доцільним варіантом може стати хеш-індекс.

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

Як це працює?

У хеш-індексі процес хешування полягає у перетворенні значення ключа індексу у хеш-код за допомогою хеш-функції. Цей хеш-код використовується для визначення розташування, або «відра», де у індексі зберігаються відповідні дані.

Розглянемо хеш-індекс для системи бібліотечного каталогу, де кожна назва книги індексується за її ISBN (Міжнародний стандартний книжковий номер).

У цьому прикладі ми використовуємо хеш-функцію для перетворення ISBN книги у шістнадцятковий хеш-код, наприклад 0x7FA4, за допомогою ряду математичних операцій над цифрами ISBN.
Цей хеш-код виступає у ролі унікального ідентифікатора, визначаючи слот у хеш-таблиці, де міститься посилання на відповідний рядок у таблиці з усією інформацією про цю книгу.

Основні характеристики

1. Швидкий пошук: хеш-індекси забезпечують швидкий пошук для операцій рівності. Під час пошуку конкретного значення PostgreSQL обчислює хеш цього значення і безпосередньо звертається до відповідного місця в індексі, що робить отримання даних дуже ефективним;

2. Обмежена підтримка операторів: на відміну від B-tree індексів, хеш-індекси підтримують лише операції рівності (=), але не підтримують діапазонні запити (<, >, <=, >=) чи сортування. Це обмеження робить хеш-індекси менш універсальними порівняно з B-tree індексами;

3. Вища швидкість для окремих сценаріїв: у випадках, коли навантаження складається переважно з запитів на рівність, наприклад, для забезпечення унікальності або первинного ключа, хеш-індекси можуть працювати швидше за B-tree індекси. Однак їхня перевага зникає при діапазонних запитах або для даних, які погано підходять для хешування.

Реалізація

Хеш-індекс у SQL можна створити за допомогою наступного оператора:

CREATE INDEX hash_index_name ON table_name USING HASH (column_name1, column_name2,... );

У результаті значення стовпців column_name1, column_name2,... будуть хешовані, і буде створено хеш-таблицю. Це забезпечить швидший доступ до потрібних рядків даних.