Хешування в СУБД: статичні та динамічні методи хешування
Фіона Браун
Що таке хешування в СУБД?
У СУБД хешування — це метод прямого пошуку розташування потрібних даних на диску без використання структури індексу. Метод хешування використовується для індексування та отримання елементів у базі даних, оскільки швидше шукати певний елемент за допомогою коротшого хешованого ключа замість використання його початкового значення. Дані зберігаються у формі блоків даних, адреса яких генерується шляхом застосування хеш-функції в місці пам’яті, де зберігаються ці записи, відомому як блок даних або сегмент даних.
Навіщо нам хешування?
Ось ситуації в СУБД, коли потрібно застосувати метод хешування:
- Для величезної структури бази даних важко шукати всі значення індексу на всьому її рівні, а потім вам потрібно досягти цільового блоку даних, щоб отримати потрібні дані.
- Метод хешування використовується для індексування та отримання елементів у базі даних, оскільки швидше шукати певний елемент за допомогою коротшого хешованого ключа замість використання його початкового значення.
- Хешування є ідеальним методом обчислення прямого розташування запису даних на диску без використання структури індексу.
- Це також корисна техніка для впровадження словників.
Важливі термінології в хешуванні
Ось важливі терміни, які використовуються в хешуванні:
- Відро даних – Блоки даних – це місця пам’яті, де зберігаються записи. Він також відомий як одиниця зберігання.
- ключ: Ключ СУБД це атрибут або набір атрибутів, який допомагає вам ідентифікувати рядок (кортеж) у відношенні (таблиці). Це дозволяє знайти зв’язок між двома таблицями.
- Функція хешу: Хеш-функція – це функція відображення, яка відображає весь набір ключів пошуку на адресу, де розміщено фактичні записи.
- Лінійне зондування – Лінійне зондування – це фіксований інтервал між зондуваннями. У цьому методі для введення нового запису використовується наступний доступний блок даних замість перезапису старішого запису.
- Квадратичне зондування– Це допомагає вам визначити нову адресу відра. Це допомагає вам додати інтервал між зондами шляхом додавання послідовного результату квадратичного полінома до початкового значення, заданого вихідним обчисленням.
- Хеш-індекс – Це адреса блоку даних. Хеш-функція може бути як простою математичною функцією, так і навіть складною математичною функцією.
- Double Хешування -Double Хешування — це метод комп’ютерного програмування, який використовується в хеш-таблицях для вирішення проблем зіткнення.
- Переповнення відра: Умова переповнення ковша називається зіткненням. Це фатальний етап для функціонування будь-якої статики.
Типи методів хешування
В основному існує два типи методів/технік хешування SQL:
- Статичне хешування
- Динамічне хешування
статичне хешування
У статичному хешуванні результуюча адреса сегмента даних завжди залишатиметься незмінною.
Тому, якщо ви згенеруєте адресу для скажімо Student_ID = 10 за допомогою функції хешування мод(3), результуюча адреса сегмента завжди буде 1. Отже, ви не побачите жодних змін в адресі сегмента.
Тому в цьому методі статичного хешування кількість сегментів даних у пам’яті завжди залишається постійною.
Статичні хеш-функції
- Вставка запису: Коли новий запис потрібно вставити в таблицю, ви можете створити адресу для нового запису, використовуючи його хеш-ключ. Коли адреса генерується, запис автоматично зберігається в цьому місці.
- Пошук: Коли вам потрібно отримати запис, ця сама хеш-функція може бути корисною для отримання адреси сегмента, де мають зберігатися дані.
- Видалити запис: Використовуючи хеш-функцію, ви можете спочатку отримати запис, який ви хочете видалити. Потім ви можете видалити записи для цієї адреси в пам’яті.
Статичне хешування далі поділяється на
- Відкрити хешування
- Закрити хешування.
Відкрийте Хешування
У відкритому методі хешування замість перезапису старішого для введення нового запису використовується наступний доступний блок даних. Цей метод також відомий як лінійне зондування.
Наприклад, A2 – це новий запис, який потрібно вставити. Хеш-функція генерує адресу як 222. Але вона вже зайнята іншим значенням. Ось чому система шукає наступне відро даних 501 і призначає йому A2.
Закрити хешування
У методі закритого хешування, коли відра заповнені, нове відро виділяється для того самого хешу, а результати зв’язуються після попереднього.
Динамічне хешування
Динамічне хешування пропонує механізм, у якому сегменти даних додаються та видаляються динамічно та на вимогу. У цьому хешуванні функція хешування допомагає створити велику кількість значень.
Різниця між упорядкованим індексуванням і хешуванням
Нижче наведено основні відмінності між індексуванням і хешуванням
| параметри | Індексація замовлення | Хешування |
|---|---|---|
| Зберігання адреси | Адреси в пам'яті сортуються відповідно до значення ключа, яке називається первинним ключем | Адреси завжди генеруються за допомогою хеш-функції для значення ключа. |
| продуктивність | Він може зменшуватися, коли дані в хеш-файлі збільшуються. Оскільки він зберігає дані у відсортованому вигляді, коли виконується будь-яка операція (вставлення/видалення/оновлення), що знижує його продуктивність. | Ефективність хешування буде найкращою, коли відбувається постійне додавання та видалення даних. Однак, коли база даних величезна, організація хеш-файлу та його обслуговування будуть дорожчими. |
| Використовувати для | Рекомендується для пошуку даних у діапазоні. Це означає, що якщо є дані для певного діапазону, цей метод є ідеальним варіантом. | Це ідеальний метод, коли ви хочете отримати певний запис на основі ключа пошуку. Однак він працюватиме добре лише тоді, коли хеш-функція знаходиться на ключі пошуку. |
| Управління пам'яттю | Буде багато невикористаних блоків даних через операцію видалення/оновлення. Ці блоки даних не можна надати для повторного використання. Тому необхідно регулярно обслуговувати пам'ять. | У статичних і динамічних методах хешування пам'яттю завжди керують. Переповнення відра також ідеально обробляється для розширення статичного хешування. |
Що таке зіткнення?
Хеш-колізія – це стан, коли отримані хеші з двох або більше даних у наборі даних неправильно відображають те саме місце в хеш-таблиця.
Як боротися з колізією хешування?
Є дві техніки, які можна використовувати, щоб уникнути геш-колізії:
- Повторення: Цей метод викликає вторинну хеш-функцію, яка безперервно застосовується, доки не буде знайдено порожній слот, куди слід розмістити запис.
- Прикування: Метод ланцюжка створює пов’язаний список елементів, хеші ключа яких однакові. Цей метод вимагає додаткового поля посилання на кожну позицію таблиці.
Підсумки
- In СУБД, хешування — це техніка прямого пошуку розташування потрібних даних на диску без використання структури індексу.
- Метод хешування використовується для індексування та отримання елементів у базі даних, оскільки швидше шукати певний елемент за допомогою коротшого хешованого ключа замість використання його початкового значення.
- Відро даних, ключ, хеш-функція, лінійне дослідження, квадратичне дослідження, хеш-індекс, Double Хешування, переповнення відра — це важливі терміни, які використовуються в хешуванні
- Два типи методів хешування: 1) статичне хешування 2) динамічне хешування
- У статичному хешуванні результуюча адреса сегмента даних завжди залишатиметься незмінною.
- Динамічне хешування пропонує механізм, у якому сегменти даних додаються та видаляються динамічно та на вимогу.
- У порядку індексування адреси в пам’яті сортуються відповідно до критичного значення, тоді як у хешуванні адреси завжди генеруються за допомогою хеш-функції для значення ключа.
- Хеш-колізія – це стан, коли результуючі хеші двох або більше даних у наборі даних неправильно відображають те саме місце в хеш-таблиці.
- Повторне хешування та ланцюжок — два методи, які допомагають уникнути колізій хешування.
