Wstęp do baz danych


Struktury plików dla metod dostępu bezpośredniego (dowolnego)



Pobieranie 8.37 Mb.
Strona36/97
Data29.10.2017
Rozmiar8.37 Mb.
1   ...   32   33   34   35   36   37   38   39   ...   97

Struktury plików dla metod dostępu bezpośredniego (dowolnego)


Do tej grupy metod należą metody mieszające (hash’owania) i metody indeksowe.

Metody mieszające


W pliku hash’owanym rekordy nie muszą być zapisywane szeregowo. Zamiast tego dla obliczenia adresu strony (stronicy), na której znajduje się poszukiwany rekord, wykorzystują funkcja mieszająca (hash-function), argumentami której są wartości jednego lub kilku pól tego rekordu. Te pola mają nazwy klucza „hash” (hash key). Rekordy w pliku hash’owanym umieszczone w dowolnym porządku (rys.39-1). Dlatego pliki hash’owane nazywają również plikami ze dowolną strukturą (random files). Jasne, że one mogą się znajdować tylko na urządzeniach pamięci z dostępem bezpośrednim.

Funkcja mieszająca “hash” wybiera się w taki sposób, żeby rekordy wewnątrz pliku były umieszczone równomiernie. Przypadkiem idealnym jest tu zależność liniowa między wartością klucza (hash key) K i adresem fizycznym strony, na której ten rekord się znajduje (rys.40). W tym przypadku gwarantuje się jednoznaczna zależność między fizycznymi i logicznymi rekordami. Jednak nie zawsze udaje się skonstruować taką zależność. Często się zdarza, że wartości kluczy znajdują się w różnych przedziałach (rys.40). W tym przypadku funkcja F(k) będzie miała zbiór zbędnych wartości odpowiadających nieistniejącym wartościom klucza. Wtedy stosują różne metody konstruowania funkcji mieszającej “hash”. N
iżej będzie rozpatrzono kilka z nich.



Metoda spłotu (folding). Bazuje się na wykonaniu operacji arytmetycznych na różnych częściach argumentów funkcji “hash”. W przypadku, kiedy argumenty mają typ symbolowy, one najpierw zostają przekształcone do typu liczbowego. Na przykład, jeśli identyfikator rekordu (klucz pierwotny) numeru pracownika przedstawia sobą dwie litery i dwie cyfry, to pierwsze dwa znaki przekształcane są do formatu liczbowego. Następnie otrzymany wynik dodaje się do pozostałej części klucza. Otrzymana w ten sposób suma wykorzystuje się jako adres fizyczny strony (stronicy), na której będzie zapisany odpowiedni rekord.

Metoda reszty od dzielenia (division-remainder). Ta metoda korzysta z funkcji MOD, argumentem której jest pole klucza rekordu. Funkcja MOD dzieli to pole na pewną liczbę, a reszta od dzielenia jest adresem fizycznym strony, na której będzie się znajdował odpowiedni rekord.

Przykład. Mamy 7 stron (stronic) fizycznych pamięci. Na jednej stronie można umieścić 3 rekordy z tablic bazy danych. Maksymalnie możliwa ilość rekordów w tablicy – 20. Numer strony fizycznej obliczamy jako MOD (identyfikator,7), tzn. jako reszta od dzielenia identyfikatora rekordu (klucza) przez liczbę 7. Rekord z kluczem 1 będzie umieszczony na stronie 1, rekord 7 na stronie 0, rekord 18 – na stronie 4, itd.

Problem, powiązany z wykorzystaniem większości funkcji mieszających „hash” polega na tym, że one nie mogą gwarantować unikalności obliczonego adresu, ponieważ ilość możliwych wartości argumentów funkcji może być znacznie więcej od ilości dostępnych do zapisu adresów. Przypadek, kiedy ten sam adres zostaje obliczony dla dwóch i więcej różnych argumentów nazywa się kolizją (collision), natomiast podobne rekordy nazywają synonimami. W tym przypadku nowy rekord trzeba umieścić w inne miejsce (pod innym adresem), ponieważ jego miejsce już jest zajęte. Istnieją różne strategie rozwiązania kolizji (konfliktów).

Jedną z nich jest rozwiązanie kolizji za pomocą obszaru przepełnienia pamięci. Zgodnie z tą strategią pamięć dzieli się na dwa obszary(rys.40_1):



  1. Obszar główny.

  2. Obszar przepełnienia.

Dla każdego rekordu na stronie fizycznej pamięci dodaje się wskaźnik na rekord, który ma synonim w pamięci przepełnienia. W ten sposób wszystkie synonimy są połączone w jeden „łańcuch”. W ostatnim rekordzie łańcucha w polu wskaźnika znajduje się znak końca łańcucha.



Dla każdego nowego rekordu oblicza się wartość funkcji mieszającej „hash” – adres w obszarze głównym pamięci. Jeśli to miejsce już jest zajęte, rekord zostaje zapisany do obszaru przepełnienia na pierwsze wolne miejsce, a w rekordzie-synonimie znajdującym się w pamięci głównej w polu wskaźnika wpisuje się adres nowego rekordu w obszarze przepełnienia. Jeśli pole wskaźnika też już jest zajęte, łańcuch wskaźników modyfikuje się w taki sposób, żeby nowy rekord-synonim okazał się drugim w obszarze przepełnienia. W taki sposób czas umieszczenia dowolnego rekordu nie przekracza czasu wykonania dwóch operacji wymiany informacji z dyskiem.

Przy wykonaniu operacji poszukiwania (odczytu) rekordu też najpierw obliczona zostaje wartość adresu rekordu umieszczonego w obszarze głównym pamięci – pierwszego rekordu w łańcuchu. Jeśli ten rekord nie jest poszukiwanym, dalej wykonuje się poszukiwanie rekordu w obszarze przepełnienia poruszając po łańcuchu rekordów-synonimów. Szybkość przeszukiwania zależy od długości łańcucha, dlatego jakość funkcji mieszającej „hash” określa się na podstawie maksymalnej długości łańcucha. Dobrym wynikiem na praktyce uważa się długość nie przekraczająca 10.

W celu usunięcia dowolnego rekordu najpierw określa się jego miejsce. Jeśli usuwany jest pierwszy rekord w łańcuchu, to po usunięciu na jego miejsce zostaje zapisany drugi w łańcuchu rekord, przy czym wszystkie wskaźniki na synonimy pozostają bez zmian.

Jeśli usuwany rekord znajduje się wewnątrz łańcucha rekordów-synonimów, to trzeba zmodyfikować wskaźniki: w pole wskaźnika rekordu znajdującego się przed usuwanym wpisuje się wskaźnik z rekordu usuwanego. Jeśli to jest ostatni rekord w łańcuchu, w pole wskaźnika wpisuje się znacznik końca łańcucha.

Rozwiązanie kolizji komplikuje obsługę hash’owanych plików i zmniejsza wydajność pracy systemu.



Wady metod mieszających:

1. Brak możliwości efektywnego przeszukiwania danych na podstawie zadanej maski lub zadanego przedziału wartości. Ten rodzaj przeszukiwania wymaga wstępnego posortowania wartości funkcji mieszającej F. Np., jeśli Rmin i Rmax określają graniczne wartości przedziału kluczy poszukiwanych rekordów, to musi być spełniony warunek F(Rmin) < F(Rmax).

2. Brak możliwości przeszukiwania na podstawie dowolnego innego pola (oprócz pola kluczy).



Pobieranie 8.37 Mb.

Share with your friends:
1   ...   32   33   34   35   36   37   38   39   ...   97




©operacji.org 2020
wyślij wiadomość

    Strona główna
warunków zamówienia
istotnych warunków
przedmiotu zamówienia
wyboru operacji
Specyfikacja istotnych
produktu leczniczego
oceny operacji
rozwoju lokalnego
strategii rozwoju
kierowanego przez
specyfikacja istotnych
Nazwa przedmiotu
Karta oceny
ramach działania
przez społeczno
obszary wiejskie
dofinansowanie projektu
lokalnego kierowanego
Europa inwestująca
Regulamin organizacyjny
przetargu nieograniczonego
kryteria wyboru
Kryteria wyboru
Lokalne kryteria
Zapytanie ofertowe
Informacja prasowa
nazwa produktu
Program nauczania
Instrukcja obsługi
zamówienia publicznego
Komunikat prasowy
programu operacyjnego
udzielenie zamówienia
realizacji operacji
opieki zdrowotnej
przyznanie pomocy
ramach strategii
Karta kwalifikacyjna
oceny zgodno
Specyfikacja techniczna
Instrukcja wypełniania
Wymagania edukacyjne
Regulamin konkursu
lokalnych kryteriów
strategia rozwoju
sprawozdania finansowego
ramach programu
ramach poddziałania
kryteriów wyboru
operacji przez
trybie przetargu