Haszowanie w DBMS: techniki mieszania statycznego i dynamicznego
Fiona Brown
⚡ Inteligentne podsumowanie
Haszowanie w systemach DBMS to technika, która oblicza lokalizację rekordu na dysku bezpośrednio na podstawie jego klucza, bez konieczności przeszukiwania indeksu. Funkcja haszująca mapuje klucze wyszukiwania na kontenery danych, a haszowanie statyczne lub dynamiczne zarządza rozrostem tych kontenerów.
Co to jest haszowanie w systemie DBMS?
W systemach DBMS haszowanie to technika bezpośredniego wyszukiwania lokalizacji żądanych danych na dysku bez użycia struktury indeksu. Metoda haszowania służy do indeksowania i pobierania elementów w bazie danych, ponieważ wyszukiwanie konkretnego elementu za pomocą krótszego klucza haszowanego jest szybsze niż wyszukiwanie jego oryginalnej wartości. Dane są przechowywane w postaci bloków danych, których adres jest generowany przez zastosowanie funkcji haszującej; lokalizacja w pamięci, w której przechowywane są te rekordy, nazywana jest… blok danych lub wiadro danych.
Dlaczego potrzebujemy haszowania?
Oto sytuacje w systemie DBMS, w których należy zastosować metodę haszującą:
- W przypadku ogromnej struktury bazy danych trudno jest przeszukać wszystkie wartości indeksów na wszystkich ich poziomach, a następnie dotrzeć do bloku danych docelowych i pobrać żądane dane.
- Haszowanie jest używane do indeksowania i pobierania elementów w bazie danych, ponieważ wyszukiwanie konkretnego elementu jest szybsze przy użyciu krótszego klucza haszowanego niż oryginalnej wartości.
- Haszowanie to doskonała metoda obliczania bezpośredniej lokalizacji rekordu danych na dysku bez korzystania ze struktury indeksu.
- Jest to również pomocna technika wdrażania słowników.
Ważne terminologie w haszowaniu
Poniżej przedstawiono ważne terminy stosowane w haszowaniu:
- Pojemnik z danymi: Pojemniki danych to lokalizacje w pamięci, w których przechowywane są rekordy. Są one również znane jako jednostki pamięci.
- Klawisz: a Klucz DBMS jest atrybutem lub zestawem atrybutów, który pomaga zidentyfikować wiersz (krotkę) w relacji (tabeli).
- Funkcja skrótu: Mapaping funkcja mapująca cały zestaw kluczy wyszukiwania na adres, pod którym umieszczone są rzeczywiste rekordy.
- Sondowanie liniowe: Stały odstęp między sondami. W tej metodzie do wprowadzenia nowego rekordu używany jest kolejny dostępny blok danych, zamiast nadpisywać starszy rekord.
- Badanie kwadratowe: pomaga ustalić nowy adres kontenera poprzez dodanie kolejnych wyników wielomianu kwadratowego do wartości początkowej otrzymanej w oryginalnym obliczeniu.
- Indeks skrótu: Adres bloku danych. Funkcja skrótu może być prostą funkcją matematyczną lub złożoną.
- Double Haszowanie: metoda używana w tablicach skrótów do rozwiązywania kolizji poprzez zastosowanie drugiej funkcji skrótu.
- Przepełnienie wiadra: Stan przepełnienia kontenera nazywa się kolizją. Jest to stan krytyczny dla każdej statycznej funkcji skrótu.
Rodzaje technik mieszania
W systemach DBMS stosuje się dwa główne rodzaje technik haszujących:
- Haszowanie statyczne
- Dynamiczne haszowanie
Różnica między nimi polega głównie na tym, czy liczba pojemników jest stała, co wyjaśniono w dwóch kolejnych sekcjach.
Haszowanie statyczne
W przypadku haszowania statycznego adres wynikowego kontenera danych zawsze pozostanie taki sam.
Dlatego jeśli wygenerujesz adres, powiedzmy, Identyfikator_ucznia = 10 korzystając z funkcji haszującej moda(3), wynikowym adresem zasobnika będzie zawsze 1. W związku z tym nie zauważysz żadnej zmiany w adresie kontenera.
Dlatego w metodzie haszowania statycznego liczba kontenerów danych w pamięci zawsze pozostaje stała.
Statyczne funkcje skrótu
- Wstawianie rekordu: Kiedy do tabeli trzeba wstawić nowy rekord, generujesz dla niego adres za pomocą klucza skrótu. Po wygenerowaniu adresu rekord jest zapisywany w tej lokalizacji.
- Badawczy: gdy trzeba pobrać rekord, ta sama funkcja skrótu jest używana do pobrania adresu kontenera, w którym przechowywane są dane.
- Usuń rekord: używając funkcji skrótu, najpierw pobierasz rekord, który chcesz usunąć, a następnie usuwasz rekord z tego adresu w pamięci.
Haszowanie statyczne dzieli się dalej na:
- Otwórz hashowanie
- Zamknięte haszowanie
Otwórz haszowanie
W metodzie otwartego haszowania, zamiast nadpisywać starszy rekord, do wprowadzenia nowego rekordu używany jest kolejny dostępny blok danych. Metoda ta jest również znana jako sondowanie liniowe.
Na przykład A2 to nowy rekord, który chcesz wstawić. Funkcja skrótu generuje adres 222, ale jest on już zajęty przez inną wartość. Dlatego system szuka kolejnego kontenera danych, 501, i przypisuje mu A2.
Zamknięte haszowanie
W przypadku metody haszowania zamkniętego, gdy kontenery są pełne, dla tego samego skrótu przydzielany jest nowy kontener, a wynik jest łączony po poprzednim.
Dynamiczne haszowanie
Dynamiczne haszowanie oferuje mechanizm, w którym kontenery danych są dodawane i usuwane dynamicznie i na żądanie. W tej metodzie haszowania funkcja haszująca pomaga tworzyć dużą liczbę wartości, a struktura rośnie lub kurczy się wraz z danymi. Dzięki temu jest to idealne rozwiązanie dla tabel, których rozmiaru nie można z góry przewidzieć, gdzie haszowanie statyczne marnowałoby miejsce lub powodowało przepełnienie.
Różnica między indeksowaniem uporządkowanym a haszowaniem
Poniżej przedstawiono najważniejsze różnice między indeksowaniem i haszowaniem:
| Parametry | Uporządkowane indeksowanie | Hashing |
|---|---|---|
| Zapisywanie adresu | Adresy w pamięci są sortowane według wartości klucza zwanej kluczem podstawowym. | Adresy są zawsze generowane przy użyciu funkcji skrótu na wartości klucza. |
| Wydajność | Może się zmniejszać w miarę zwiększania ilości danych, ponieważ dane są przechowywane w postaci posortowanej, a każde wstawienie, usunięcie lub aktualizacja powoduje ich zmianę kolejności. | Wydajność jest najlepsza przy ciągłym dodawaniu i usuwaniu danych. W przypadku ogromnej bazy danych utrzymanie pliku skrótu staje się droższe. |
| Używać do | Preferowane w przypadku pobierania zakresów, gdzie dane są pobierane dla konkretnego zakresu. | Idealne do pobierania konkretnego rekordu na podstawie klucza wyszukiwania i działa dobrze tylko wtedy, gdy klucz wyszukiwania jest przypisany do funkcji skrótu. |
| Zarządzanie pamięcią | Wiele nieużywanych bloków danych powstaje w wyniku operacji usuwania i aktualizacji i nie można ich zwolnić do ponownego wykorzystania, dlatego wymagana jest regularna konserwacja. | W przypadku haszowania statycznego i dynamicznego pamięć jest zawsze zarządzana, a przepełnienie kontenera jest obsługiwane w celu rozszerzenia haszowania statycznego. |
Krótko mówiąc, wybierz uporządkowane indeksowanie do zapytań zakresowych i haszowania w celu dokładnego dopasowania klucza.
Co to jest kolizja?
Kolizja haszowania to stan, w którym wynikowe hasze z dwóch lub więcej elementów w zestawie danych błędnie mapują się na to samo miejsce w tabela mieszania.
Jak radzić sobie z kolizją haszującą
Istnieją dwie techniki, których możesz użyć, aby uniknąć kolizji haszującej:
- Powtórzenie: Metoda ta wywołuje drugorzędną funkcję skrótu, która jest stosowana w sposób ciągły, aż do znalezienia pustego slotu, w którym można umieścić rekord.
- Łączenie: Metoda łańcuchowa tworzy listę powiązaną elementów, których klucze mają tę samą wartość skrótu. Ta metoda wymaga dodatkowego pola łączącego na każdej pozycji w tabeli.
