Haszowanie w DBMS: techniki mieszania statycznego i dynamicznego
Fiona Brown
Co to jest haszowanie w systemie DBMS?
W systemie DBMS hashowanie to technika bezpośredniego wyszukiwania lokalizacji żądanych danych na dysku bez użycia struktury indeksu. Metoda mieszania służy do indeksowania i pobierania elementów z bazy danych, ponieważ szybciej jest przeszukiwać konkretny element przy użyciu krótszego klucza mieszanego, zamiast używać jego oryginalnej wartości. Dane są przechowywane w formie bloków danych, których adres jest generowany poprzez zastosowanie funkcji skrótu w lokalizacji pamięci, w której przechowywane są te rekordy, zwanej blok danych lub wiadro danych.
Dlaczego potrzebujemy hashowania?
Oto sytuacje w systemie DBMS, w których należy zastosować metodę mieszania:
- W przypadku ogromnej struktury bazy danych trudno jest przeszukać wszystkie wartości indeksu na całym jej poziomie, a następnie trzeba dotrzeć do docelowego bloku danych, aby uzyskać żądane dane.
- Metoda mieszania służy do indeksowania i pobierania elementów z bazy danych, ponieważ szybciej jest przeszukiwać konkretny element przy użyciu krótszego klucza mieszanego, zamiast używać jego oryginalnej wartości.
- Haszowanie to idealna metoda obliczania bezpośredniej lokalizacji rekordu danych na dysku bez użycia struktury indeksu.
- Jest to również pomocna technika wdrażania słowników.
Ważne terminologie w haszowaniu
Oto ważne terminologie używane w haszowaniu:
- Wiadro danych – Pojemniki danych to miejsca w pamięci, w których przechowywane są rekordy. Jest również znany jako jednostka pamięci.
- Klawisz: Klucz DBMS to atrybut lub zestaw atrybutów, który pomaga zidentyfikować wiersz (krotkę) w relacji (tabela). Pozwala to znaleźć relację między dwiema tabelami.
- Funkcja skrótu: Funkcja skrótu to funkcja mapująca, która odwzorowuje cały zestaw kluczy wyszukiwania na adres, pod którym umieszczone są rzeczywiste rekordy.
- Sondowanie liniowe – Sondowanie liniowe to stały odstęp pomiędzy sondami. W tej metodzie do wprowadzenia nowego rekordu używany jest następny dostępny blok danych, zamiast nadpisywać starszy rekord.
- Sondowanie kwadratowe– Pomaga określić nowy adres wiadra. Pomaga dodać odstęp między sondami poprzez dodanie kolejnego wyniku wielomianu kwadratowego do wartości początkowej określonej w pierwotnym obliczeniu.
- Indeks skrótu – Jest to adres bloku danych. Funkcja skrótu może być prostą funkcją matematyczną, a nawet złożoną funkcją matematyczną.
- Double Hashing -Double haszowanie to metoda programowania komputerowego stosowana w tablicach mieszających w celu rozwiązania problemów związanych z kolizjami.
- Przepełnienie wiadra: Stan przepełnienia kubła nazywany jest kolizją. Jest to fatalny etap dla funkcjonowania każdego urządzenia statycznego.
Rodzaje technik mieszania
Istnieją głównie dwa typy metod/technik mieszania SQL:
- Haszowanie statyczne
- Dynamiczne haszowanie
statyczne haszowanie
W mieszaniu statycznym wynikowy adres zasobnika danych zawsze pozostanie taki sam.
Dlatego jeśli wygenerujesz adres np Identyfikator_ucznia = 10 za pomocą funkcji mieszającej moda(3), wynikowym adresem zasobnika będzie zawsze 1. Zatem nie zobaczysz żadnych zmian w adresie zasobnika.
Dlatego w tej statycznej metodzie mieszania liczba segmentów danych w pamięci zawsze pozostaje stała.
Statyczne funkcje skrótu
- Wstawianie rekordu: Kiedy nowy rekord wymaga wstawienia do tabeli, możesz wygenerować adres nowego rekordu, używając jego klucza skrótu. Po wygenerowaniu adresu rekord jest automatycznie zapisywany w tej lokalizacji.
- Badawczy: Kiedy chcesz odzyskać rekord, ta sama funkcja skrótu powinna być pomocna do odzyskania adresu segmentu, w którym powinny być przechowywane dane.
- Usuń rekord: Korzystając z funkcji skrótu, możesz najpierw pobrać rekord, który chcesz usunąć. Następnie możesz usunąć zapisy dla tego adresu z pamięci.
Mieszanie statyczne dzieli się dalej na
- Otwórz hashowanie
- Zamknij haszowanie.
Otwórz haszowanie
W metodzie Open hashing zamiast nadpisywać starszy, do wprowadzenia nowego rekordu używany jest następny dostępny blok danych. Metoda ta jest również nazywana sondowaniem liniowym.
Na przykład A2 to nowy rekord, który chcesz wstawić. Funkcja mieszająca generuje adres jako 222. Jednak jest on już zajęty przez inną wartość. Dlatego system szuka kolejnego zasobnika danych 501 i przypisuje mu A2.
Zamknij haszowanie
W metodzie ścisłego mieszania, gdy zasobniki są pełne, dla tego samego skrótu przydzielany jest nowy zasobnik, a wyniki są łączone po poprzednim.
Dynamiczne haszowanie
Dynamiczne mieszanie oferuje mechanizm, w którym zasobniki danych są dodawane i usuwane dynamicznie i na żądanie. W tym mieszaniu funkcja mieszająca pomaga utworzyć dużą liczbę wartości.
Różnica między indeksowaniem uporządkowanym a haszowaniem
Poniżej znajdują się kluczowe różnice między indeksowaniem a haszowaniem
| parametry | Indeksowanie zamówień | 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ę zmniejszyć, gdy dane w pliku hash rosną. Ponieważ przechowuje dane w posortowanej formie, gdy wykonywana jest jakakolwiek operacja (wstaw/usuń/aktualizuj), która zmniejsza jego wydajność. | Wydajność mieszania będzie najlepsza, gdy dane będą stale dodawane i usuwane. Jednakże, gdy baza danych jest ogromna, wówczas organizacja pliku skrótu i jego utrzymanie będą droższe. |
| Używać do | Preferowana do wyszukiwania danych dotyczących zakresu — co oznacza, że zawsze, gdy dostępne są dane dotyczące określonego zakresu, metoda ta jest idealną opcją. | Jest to idealna metoda, gdy chcesz wyszukać konkretny rekord na podstawie klucza wyszukiwania. Jednak będzie działać dobrze tylko wtedy, gdy funkcja skrótu jest na klawiszu wyszukiwania. |
| Zarządzanie pamięcią | Będzie wiele nieużywanych bloków danych z powodu operacji usuwania/aktualizowania. Te bloki danych nie mogą zostać zwolnione do ponownego użycia. Dlatego wymagana jest regularna konserwacja pamięci. | W statycznych i dynamicznych metodach mieszania pamięć jest zawsze zarządzana. Przepełnienie zasobnika jest również doskonale obsługiwane w celu rozszerzenia mieszania statycznego. |
Co to jest kolizja?
Kolizja skrótu to stan, w którym wynikowy skrót dwóch lub więcej danych w zbiorze danych błędnie odwzorowuje to samo miejsce w zbiorze tabela mieszania.
Jak sobie poradzić z kolizją haszującą?
Istnieją dwie techniki, których można użyć, aby uniknąć kolizji skrótu:
- Odświeżanie: Ta metoda wywołuje dodatkową funkcję skrótu, która jest stosowana w sposób ciągły aż do znalezienia pustego miejsca, w którym należy umieścić rekord.
- Łańcuch: Metoda łączenia tworzy połączoną listę elementów, których klucze mają tę samą wartość. Ta metoda wymaga dodatkowego pola łącza do każdej pozycji w tabeli.
Podsumowanie
- In DBMShaszowanie to technika bezpośredniego wyszukiwania lokalizacji żądanych danych na dysku bez użycia struktury indeksu.
- Metoda mieszania służy do indeksowania i pobierania elementów z bazy danych, ponieważ szybciej jest przeszukiwać konkretny element przy użyciu krótszego klucza mieszanego, zamiast używać jego oryginalnej wartości.
- Wiadro danych, klucz, funkcja skrótu, sondowanie liniowe, sondowanie kwadratowe, indeks skrótu, Double Haszowanie, przepełnienie Bucket to ważne terminologie stosowane w haszowaniu
- Dwa rodzaje metod mieszania to 1) mieszanie statyczne 2) mieszanie dynamiczne
- W mieszaniu statycznym wynikowy adres zasobnika danych zawsze pozostanie taki sam.
- Dynamiczne mieszanie oferuje mechanizm, w którym zasobniki danych są dodawane i usuwane dynamicznie i na żądanie.
- W celu indeksowania adresy w pamięci są sortowane według wartości krytycznej, natomiast podczas mieszania adresy są zawsze generowane przy użyciu funkcji mieszającej na wartości klucza.
- Kolizja skrótu to stan, w którym wynikowe mieszanie dwóch lub więcej danych w zestawie danych błędnie mapuje to samo miejsce w tabeli skrótów.
- Ponowne mieszanie i łączenie w łańcuchy to dwie metody, które pomagają uniknąć kolizji mieszającej.
