Хеширане в СУБД: Статични и динамични техники за хеширане

по: Фиона Браун Фиона Браун
Hours Обновено

⚡ Умно обобщение

Хеширането в СУБД е техника, която изчислява местоположението на запис на диска директно от неговия ключ, без да се обхожда индекс. Хеш функцията съпоставя ключовете за търсене с контейнери с данни, а статичното или динамичното хеширане управлява как тези контейнери нарастват.

  • ⚡ Основна идея: Хеш функцията превръща ключ в адрес на контейнер, така че записът се намира в една стъпка, а не чрез обхождане на индекса.
  • 🪣 Кофа с данни: Мястото в паметта или единицата за съхранение, където се поставят записи с един и същ хеш.
  • 📌 Статично хеширане: Броят на контейнерите е фиксиран, така че даден ключ винаги се съпоставя с един и същ адрес.
  • 📈 Динамично хеширане: Кофите се добавят и премахват при поискване, когато обемът на данните се променя.
  • 💥 Сблъсък: Карта с два ключаping към една и съща кофа, разрешено чрез сондиране, преформулиране или верижно свързване.
  • 🔍 Най-доброто за: Търсения с точно съвпадение по ключа за търсене, където хеширането е по-важно от подреденото индексиране.
  • 📊 Компромис: Подреденото индексиране е по-ефективно за заявки за диапазон; хеширането е по-ефективно за вмъкване на константи и търсене на точки.
Прочетете повече

Статично и динамично хеширане в СУБД

Какво е хеширане в СУБД?

В СУБД хеширането е техника за директно търсене на местоположението на желаните данни на диска, без да се използва индексна структура. Методът на хеширане се използва за индексиране и извличане на елементи в база данни, тъй като е по-бързо да се търси конкретен елемент, използвайки по-късия хеширан ключ, вместо оригиналната му стойност. Данните се съхраняват под формата на блокове данни, чийто адрес се генерира чрез прилагане на хеш функция; мястото в паметта, където се съхраняват тези записи, е известно като блок с данни или контейнер с данни.

Защо ни е необходимо хеширане?

Ето ситуациите в СУБД, в които е необходимо да приложите метода на хеширане:

  • За огромна структура на базата данни е трудно да се претърсят всички стойности на индекса през всичките им нива и след това да се достигне целевият блок данни, за да се получат желаните данни.
  • Хеширането се използва за индексиране и извличане на елементи в база данни, защото е по-бързо да се търси конкретен елемент, използвайки по-късия хеширан ключ, отколкото оригиналната стойност.
  • Хеширането е идеален метод за изчисляване на директното местоположение на запис с данни на диска, без да се използва индексна структура.
  • Това също е полезна техника за внедряване на речници.

Важни терминологии в хеширането

Ето важни термини, използвани при хеширането:

  • Кофа с данни: Кофите за данни са места в паметта, където се съхраняват записите. Известни са още като единица за съхранение.
  • Key: a СУБД ключ е атрибут или набор от атрибути, който ви помага да идентифицирате ред (кортеж) в релация (таблица).
  • Хеш функция: картаping функция, която съпоставя целия набор от ключове за търсене с адреса, където са поставени действителните записи.
  • Линейно сондиране: фиксиран интервал между сондите. При този метод следващият наличен блок данни се използва за въвеждане на новия запис, вместо да се презаписва по-старият запис.
  • Квадратно сондиране: помага за определянето на новия адрес на кофата чрез добавяне на последователния изход на квадратичен полином към началната стойност, дадена от оригиналното изчисление.
  • Хеш индекс: адресът на блока данни. Хеш функцията може да бъде проста математическа функция или сложна.
  • Double Хеширане: метод, използван в хеш таблици за разрешаване на колизии чрез прилагане на втора хеш функция.
  • Препълване на кофата: Състоянието на препълване на кофата се нарича колизия. Това е фатален етап за всяка статична хеш функция.

Видове техники за хеширане

В СУБД има основно два вида техники за хеширане:

  1. Статично хеширане
  2. Динамично хеширане

Двете се различават главно по това дали броят на кофите е фиксиран, както е обяснено в следващите два раздела.

Статично хеширане

При статично хеширане, полученият адрес на контейнера с данни винаги ще остане един и същ.

Следователно, ако генерирате адрес за, да речем, Student_ID = 10 използвайки хеш функцията мод (3), резултатният адрес на кофа винаги ще бъде 1Така че няма да видите никаква промяна в адреса на кофата.

Следователно, при метода на статично хеширане, броят на контейнерите с данни в паметта винаги остава постоянен.

СВЪРЗАНИ СТАТИИ

Статични хеш функции

  • Вмъкване на запис: Когато в таблицата трябва да се вмъкне нов запис, генерирате адрес за него, използвайки неговия хеш ключ. След като адресът бъде генериран, записът се съхранява на това място.
  • търсене: Когато е необходимо да извлечете записа, същата хеш функция се използва за извличане на адреса на кофата, където се съхраняват данните.
  • Изтриване на запис: Използвайки хеш функцията, първо извличате записа, който искате да изтриете, след което премахвате записа от този адрес в паметта.

Статичното хеширане се разделя допълнително на:

  1. Отворено хеширане
  2. Затворено хеширане

Отворете Хеширане

При метода на отворено хеширане, вместо да се презаписва по-старият запис, следващият наличен блок данни се използва за въвеждане на новия запис. Този метод е известен още като линейно сондиране.

Например, A2 е нов запис, който искате да вмъкнете. Хеш функцията генерира адрес 222, но той вече е зает от друга стойност. Ето защо системата търси следващия контейнер с данни, 501, и му присвоява A2.

Как работи отвореното хеширане с линейно сондиране
Как работи Open Hash

Затворено хеширане

При метода на затворено хеширане, когато кофите са пълни, се разпределя нова кофа за същия хеш и резултатът се свързва след предишната.

Динамично хеширане

Динамичното хеширане предлага механизъм, при който контейнерите с данни се добавят и премахват динамично и при поискване. При този метод на хеширане хеш функцията ви помага да създадете голям брой стойности, а структурата расте или се свива заедно с данните. Това го прави подходящ за таблици, чийто размер не може да бъде предвиден предварително, където статичното хеширане би довело до загуба на място или препълване.

Разлика между подредено индексиране и хеширане

По-долу са изброени ключовите разлики между индексиране и хеширане:

параметри Подредено индексиране хеширане
Съхраняване на адрес Адресите в паметта се сортират според ключова стойност, наречена първичен ключ. Адресите винаги се генерират с помощта на хеш функция върху стойността на ключа.
Изпълнение Може да намалява с увеличаване на данните, защото данните се съхраняват сортирани и всяко вмъкване, изтриване или актуализиране ги пренарежда. Производителността е най-добра при постоянно добавяне и изтриване на данни. За огромна база данни поддръжката на хеш файлове става по-скъпа.
Използвай за Предпочита се за извличане на диапазон, където данните се извличат за определен диапазон. Идеален за извличане на конкретен запис въз основа на ключа за търсене и работи добре само когато хеш функцията е на ключа за търсене.
Управление на паметта Много неизползвани блокове данни възникват от операции по изтриване и актуализиране и не могат да бъдат освободени за повторна употреба, така че е необходима редовна поддръжка. При статичното и динамичното хеширане паметта винаги се управлява и препълването на контейнера се обработва, за да се разшири статичното хеширане.

Накратко, изберете подредено Индексиране за заявки за диапазон и хеширане за търсения с точно съвпадение на ключа.

Какво е сблъсък?

Хеш колизията е състояние, при което получените хешове от два или повече елемента в набора от данни погрешно се съпоставят с едно и също място в хеш таблица.

Как да се справим със сблъсък при хеширане

Има две техники, които можете да използвате, за да избегнете колизия на хешовете:

  1. Преразказване: Този метод извиква вторична хеш функция, която се прилага непрекъснато, докато се намери празен слот, където може да се постави запис.
  2. верижно: Методът на верижно свързване изгражда свързан списък от елементи, чиито хеш ключове са с еднаква стойност. Този метод изисква допълнително поле за връзка на всяка позиция в таблицата.

Въпроси и Отговори

Статичното хеширане поддържа фиксиран брой контейнери, така че може да препълни данните с нарастването им. Динамичното хеширане добавя и премахва контейнери при поискване, така че се адаптира към променящия се размер на данните без пълно преструктуриране.

За заявки за диапазон. Хеширането разпръсква ключовете в контейнери, така че заявка „между“ или „по-голямо от“ не може да ги преглежда подредени. Подреденият индекс поддържа ключовете сортирани и е по-подходящ за тях.

Кофата препълва, когато към нея се хешират повече записи, отколкото може да побере. При статичното хеширане това е често срещано явление с нарастването на данните и се обработва чрез отворено адресиране, верижно свързване или контейнери за препълване.

Системите с изкуствен интелект използват хеширане за бързо търсене на характеристики и за хеширащия трик, който картографира категории с висока кардиналност във фиксиран вектор. Хеширането на сходство също така ефективно групира почти дублиращи се записи.

Повторното хеширане намира друг свободен слот в същата таблица, използвайки втора функция. Верижното свързване поддържа колизиращите се записи в свързан списък, прикачен към кофата, така че самата таблица никога не запълва слот два пъти.

Обобщете тази публикация с: