Haszowanie liniowe

Liniowe mieszanie ( LH ) to dynamiczna struktura danych, która implementuje tablicę mieszającą i zwiększa lub zmniejsza jeden segment na raz. Został wynaleziony przez Witolda Litwina w 1980 roku. Analizowali go Baeza-Yates i Soza-Pollman. Jest to pierwszy z wielu schematów znanych jako dynamiczne mieszanie, takich jak liniowe mieszanie Larsona z częściowymi rozszerzeniami, liniowe mieszanie z podziałem priorytetów, liniowe mieszanie z częściowymi rozszerzeniami i podziałem priorytetów lub rekurencyjne liniowe mieszanie.

Struktura plików dynamicznej struktury danych mieszających dostosowuje się do zmian rozmiaru pliku, dzięki czemu unika się kosztownej okresowej reorganizacji plików. Plik Linear Hashing rozszerza się, dzieląc z góry określony zasobnik na dwa i kurczy się, łącząc dwa z góry określone zasobniki w jeden. Wyzwalacz do rekonstrukcji zależy od smaku schematu; może to być przepełnienie w łyżce lub współczynnik obciążenia (liczba rekordów podzielona przez liczbę zasobników) wychodzących poza określony zakres. W Linear Hashing istnieją dwa rodzaje kubełków, te, które mają być podzielone, i te, które już zostały podzielone. Podczas gdy mieszanie rozszerzalne dzieli tylko przepełnione zasobniki, haszowanie spiralne (znane również jako spiralne przechowywanie) rozdziela rekordy nierównomiernie w zasobnikach, tak że zasobniki z wysokimi kosztami wstawienia, usunięcia lub pobrania są najwcześniej w kolejce do podziału.

Linear Hashing zostało również przekształcone w skalowalną rozproszoną strukturę danych, LH* . W LH* każdy zasobnik znajduje się na innym serwerze. Samo LH* zostało rozszerzone, aby zapewnić dostępność danych w przypadku awarii segmentów. Operacje oparte na kluczach (wstawianie, usuwanie, aktualizacja, odczyt) w LH i LH* zajmują maksymalny stały czas niezależny od liczby segmentów, a tym samym rekordów.

Szczegóły algorytmu

Rekordy w LR lub LR* składają się z klucza i treści, przy czym ta ostatnia to w zasadzie wszystkie inne atrybuty zapisu. Przechowywane są w wiadrach. Na przykład w implementacji Ellisa wiadro jest połączoną listą rekordów. Plik umożliwia operacje CRUD oparte na kluczach, tworzenie lub wstawianie, odczytywanie, aktualizowanie i usuwanie, a także operacje skanowania, które skanują wszystkie rekordy, na przykład w celu wykonania operacji wyboru bazy danych na atrybucie innym niż klucz. Rekordy są przechowywane w zasobnikach, których numeracja zaczyna się od 0.

Funkcje skrótu

Aby uzyskać dostęp do rekordu za pomocą klucza $. W dowolnym$ do $mieszającą$ stosowana jest rodzina funkcji mieszających, zwanych łącznie dynamiczną funkcją $}} .$ używane są najwyżej dwie funkcje skrótu $displaystyle h_ {i$ h Typowy przykład wykorzystuje operację dzielenia modulo x. Jeśli pierwotna liczba segmentów to ${\ displaystyle N}$ , to jest to rodzina funkcji mieszających

${\ Displaystyle h_ {i} (c) \ mapsto c {\ pmod {N \ cdot 2 ^ {i}}}}$

Ekspansja plików

Gdy plik rośnie dzięki wstawieniom, rozszerza się z wdziękiem poprzez podział jednego wiadra na dwa wiadra. Kolejność wiader do podziału jest z góry ustalona. Jest to podstawowa różnica w stosunku do schematów takich jak rozszerzalne mieszanie Fagina. $h_ {i+1}}$ przypadku dwóch nowych zasobników funkcja skrótu jest zastępowana przez . $displaystyle$ \ Numer segmentu do podziału jest częścią stanu pliku i nazywany jest wskaźnikiem podziału ${\ displaystyle s}$ .

Podziel kontrolę

Podział można wykonać zawsze, gdy wiadro się przepełni. To niekontrolowany podział. Alternatywnie plik może monitorować współczynnik obciążenia i przeprowadzać podział, gdy współczynnik obciążenia przekracza próg. To był kontrolowany podział.

Adresowanie

$.$ jest oparte na stanie pliku, składającym się ze wskaźnika $podziału$ poziomu $\ displaystyle h_ {l$ poziom wynosi ${$ skrótu to i $}}$ .

Algorytm LH dla klucza mieszającego ${\ displaystyle c}$ do

${\ Displaystyle a: = h_ {l} (c)}$

jeśli ${\ Displaystyle a <s: a: = h_ {l + 1} (c)}$

Rozdzielać

Gdy wiadro jest podzielone, wskaźnik podziału i ewentualnie poziom są aktualizowane zgodnie z

${\ Displaystyle s: = s + 1}$

jeśli ${\ Displaystyle s \ geq N \ razy 2 ^ {l}}$ : ${\ Displaystyle l + = 1, s = 0}$

Skurcz pliku

Jeśli przy kontrolowanym podziale współczynnik obciążenia spadnie poniżej progu, uruchamiana jest operacja scalania. Operacja scalania cofa ostatni podział, a także resetuje stan pliku.

Obliczanie stanu pliku

$Stan$ pliku składa się ze $podzielonego$ i . Jeśli oryginalny plik zaczynał się od zasobników, to liczba zasobników i stan pliku są powiązane poprzez $= 1$ ${\ displaystyle N$

${\ Displaystyle n = 2 ^ {l} + s}$

lewa*

Głównym wkładem LH* jest umożliwienie klientowi pliku LH* znalezienia zasobnika, w którym znajduje się rekord, nawet jeśli klient nie zna stanu pliku. W rzeczywistości klienci przechowują swoją wersję stanu pliku, która początkowo jest tylko wiedzą o pierwszym zasobniku, a mianowicie zasobniku 0. Na podstawie stanu pliku klient oblicza adres klucza i wysyła żądanie do tego zasobnika. W zasobniku żądanie jest sprawdzane, a jeśli rekordu nie ma w zasobniku, jest on przekazywany dalej. W rozsądnie stabilnym systemie, to znaczy, jeśli podczas przetwarzania żądania ma miejsce tylko jeden podział lub połączenie, można wykazać, że są co najwyżej dwa forwardy. Po przesłaniu dalej ostatni zasobnik wysyła komunikat o dostosowaniu obrazu do klienta, którego stan jest teraz bliższy stanowi pliku dystrybuowanego. Podczas gdy forwardy są dość rzadkie dla aktywnych klientów, ich liczbę można jeszcze bardziej zmniejszyć poprzez dodatkową wymianę informacji między serwerami a klientami

Adopcja w systemach językowych

Griswold i Townsend omówili przyjęcie liniowego haszowania w języku Icon . Omówili alternatywy implementacji dynamicznej tablicy stosowanego w haszowaniu liniowym oraz przedstawili porównania wydajności za pomocą listy aplikacji porównawczych Icon.

Adopcja w systemach bazodanowych

Liniowe mieszanie jest używane w systemie bazy danych Berkeley (BDB) , który z kolei jest używany przez wiele systemów oprogramowania, wykorzystując implementację C pochodzącą z artykułu CACM i opublikowaną po raz pierwszy w Usenecie w 1988 roku przez Esmonda Pitta.

Linki zewnętrzne

Zobacz też