Wstęp do baz danych


Struktury plików dla metod indeksowanych



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

Struktury plików dla metod indeksowanych

Indeksowane metody organizacji plików oparte są o wykorzystanie indeksów dla poszukiwania rekordów. Zbiór indeksów może przedstawiać sobą osobny plik. Struktura każdego pliku indeksów związana jest z pewnym kluczem i zawiera rekordy z dwoma polami: polem klucza indeksu i pola adresu fizycznego strony, na której znajduje się rekord z kluczem równym wartości indeksu. Pojęcie pliku indeksów jest analogiczne indeksowi w książce: mając słowo kluczowe i indeks na końcu książki, można odnaleźć stronę książki, na której znajduje się wytłumaczenie tego słowa kluczowego.

Plik zawierający rekordy ma nazwę pliku danych, natomiast plik zawierający rekordy indeksów – plikiem indeksów. Wartości pól kluczy w pliku indeksów są posortowane według pola indeksowania – zazwyczaj według jednego z atrybutów tablicy bazy danych. Jeśli ten atrybut jest kluczem pierwotnym pewnej tablicy, indeks ma nazwę pierwotnego (głównego). Jeśli jako indeks wykorzystany jest inny atrybut tablicy, indeks nazywa się wtórnym (drugorzędnym), a sam ten atrybut kluczem wtórnym. Pliki danych mogą nie być posortowane według indeksu wtórnego.

Indeksy można realizować na różne sposoby. Jeśli indeks wskazuje bezpośrednio na stronę fizyczną pamięci, on ma nazwę jednopoziomowego indeksu. Pliki wykorzystujące taki indeks mają nazwę plików z indeksowo-szeregową metodą dostępu (Indexed Sequential Access Method) (Metoda była opracowana przez firmę IBM). Jeśli indeks wskazuje na inny indeks, on ma nazwę wielopoziomowego. Indeks może być rozrzedzonym (rzadkim) (sparse) lub pełnym (gęstym) (dense). Rozrzedzony indeks zawiera rekordy indeksowe tylko dla niektórych kluczowych wartości poszukiwanych w danym pliku. Pełny indeks ma rekordy indeksowe dla wszystkich kluczowych wartości poszukiwanych w pliku. Przykłady realizacji pełnego i rzadkiego indeksów sporządzonych dla tablicy pracowników firmy pokazane są na rys.41.

Jeśli rekordy w pliku są posortowane, nie ma potrzeby przechowywać pełny indeks – wystarczy trzymać tylko indeks ostatniego rekordu i wskaźnik na stronę (stronicę) fizyczną pamięci. Wtedy wszystkie rekordy z indeksami mniejszymi od danego oraz większymi od poprzedniego indeksu będą się znajdować na tej samej stronie pamięci.

Powiązany z indeksem pierwotnym plik danych zawsze jest posortowany według kluczy tego indeksu. Każdy pierwotny klucz jest unikalnym, dlatego nie istnieje dwóch jednakowych indeksów pierwotnych. Tzn. mamy wzajemnie jednoznaczną zależność pomiędzy rekordami pierwotnego indeksu i stronami pliku danych. Dla poszukiwania rekordów na podstawie kluczy w indeksie pierwotnym zazwyczaj stosuje się metoda przeszukiwania binarnego.



Wtórny indeks też jest posortowanym plikiem, analogicznie indeksowi pierwotnemu. Jednak plik danych nie musi być posortowany według wtórnego klucza. Klucz wtórnego indeksu może zawierać jednakowe wartości, co jest niedopuszczalne dla indeksu pierwotnego. Np. dla tablicy pracowników firmy można utworzyć wtórny indeks według pola numeru oddziału kampanii (Bno). Ponieważ wiele pracowników może pracować w jednym oddziale, ten indeks nie jest unikalnym. Dla pracy z takimi indeksami korzystają z pełnego wtórnego indeksu, w którym określono zależność dla każdego pola indeksu i odpowiedniej stronicy pliku danych.

Zwiększenie rozmiaru pliku indeksów i jego poszerzenie na dużą ilość stronic pamięci powodują znaczny wzrost czasu odnalezienia poszukiwanego indeksu. Np. przy wykorzystaniu metody przeszukiwania binarnego trzeba wykonać operacji odczytu i porównania w indeksie zajmującym p stron w pamięci. Korzystając z wielopoziomowego indeksu można zmniejszyć przedział przeszukiwania. Idea dostępu do stron fizycznych pamięci bazuje się na rozdzieleniu indeksu na kilka pod-indeksów mniejszego rozmiaru i utworzeniu dla nich nowego indeksu. Rys. 38 ilustruje przykład dwupoziomowego indeksu dla tablicy pracowników. W naszym przykładzie na każdej stronie fizycznej pliku danych można umieścić dwa rekordy (dwa wiersze tablicy).






Oprócz tego, na każdej stronicy indeksu pierwszego poziomu też znajdują się dwa rekordy (tylko w celu klarowności tłumaczenia). Każdy indeksowy rekord zawiera wartość klucza dostępu i adres strony pamięci. Przechowywana wartość klucza jest największą na adresowanej stronie.

Podczas poszukiwania według wartości atrybutu identyfikatora pracownika (np. SL14) najpierw sprawdzony zostaje indeks drugiego poziomu, w którym odszukana zostaje strona z wartością ostatniego klucza większą lub równą SL14. W naszym przypadku wartość ostatniego klucza jest równa SG37. Odnaleziony rekord zawiera adres stronicy indeksu pierwszego poziomu, w którym trzeba kontynuować poszukiwanie. Powtarzając opisaną procedurę otrzymujemy adres strony 2, gdzie znajduje się poszukiwany rekord.

Organizacja indeksów w postaci B-drzew (B-tree)

Wielopoziomowe indeksy mogą być realizowane w postaci drzewa. Drzewo składa się z hierarchii węzłów (node), w której każdy węzeł oprócz korzenia (root) ma węzeł macierzysty oraz jeden lub kilka węzłów potomnych (child). Korzeń nie ma węzła macierzystego. Węzeł, który nie ma węzłów potomnych nazywa się listkiem lub lisciem (leaf).

Głębokość drzewa – to jest maksymalna ilość poziomów od korzenia drzewa do liścia. Głębokość drzewa może być różna dla różnych ścieżek wiodących do liścia. Jeśli jednak ta głębokość jest wszędzie jednakowa, odpowiednie drzewo ma nazwę zbilansowanego lub B-drzewem (B-tree). Stopniem (degree) lub rzędem (order) drzewa nazywa się maksymalna liczba węzłów potomnych dla każdego węzła macierzystego. Drzewem binarnym (binary tree) nazywa się drzewo rzędu 2, tzn. każdy węzeł w którym ma nie więcej niż dwa węzły potomne. Drzewo binarne jest przypadkiem szczegółowym B-drzewa.

Dla przechowywania indeksów stosuje się modyfikacja B-drzewa, która ma nazwę drzewa B(+). Takie drzewo określa się następującą.



  • Jeśli korzeń drzewa nie jest liściem, on musi mieć co najmniej dwa węzła potomnych.

  • W drzewie N-tego rzędu każdy węzeł (za wyłączeniem korzenia i liścia) powinien mieć od N/2 do N wskaźników i węzłów potomnych. Jeśli N/2 nie jest liczbą całkowitą, to ta liczba zaokrągla się do najbliższej większej liczby całkowitej.

  • W drzewie N-tego rzędu B-drzewa ilość wartości kluczowych w liście powinna się znajdować w przedziale od (N-1)/2 do N/2. Jeśli liczba (N-1)/2 nie jest całkowitą, ta liczba zaokrągla się do najbliższej liczby całkowitej.

  • Ilość wartości kluczowych w węźle, który nie jest liściem jest o jeden mniejsza od ilości wskaźników.

  • Drzewo zawsze powinno być zbilansowanym, czyli wszystkie ścieżki od korzenia do liścia muszą mieć jednakową głębokość.

  • Liście drzewa są powiązane w kolejności zwiększenia wartości kluczowych.

Na rys. 43 przedstawiono indeks w postaci drzewa B(+) rzędu trzeciego dla tablicy zawierającej dane pracowników firmy. Każdy węzeł w tym drzewie ma postać::



*

Wartość kluczowa1

*

Wartość kluczowa2

*

Tu symbol (*) oznacza wskaźnik na inny rekord. Niektóre klucze oraz wskaźniki mogą być nieobecne w węźle.
Algorytm poszukiwania w B-drzewie.

Zaczynając od korzenia wykonujemy operacje porównania. Jeśli wartość poszukiwanego klucza jest mniejsza lub równa wartości klucza 1 lub klucza2 (w naszym przypadku), to dla przejścia do następnego węzła korzystamy z wskaźnika znajdującego się z lewa od pola tego klucza. W przypadku przeciwnym korzystamy z wskaźnika umieszczonego ostatnim w danym węźle.

Na przykład, dla odnalezienia rekordu „SL21” zaczynamy przeszukiwanie od korzenia drzewa. Ponieważ wartość „SL21” jest większa od „SG14”, trzeba przejść zgodnie z wskaźnikiem umieszczonym z lewa od „SL21”, tzn. na liść z adresem rekordu „SL21”.



Drzewo B(+) – jest najbardziej efektywna strukturą dla tworzenia indeksów. W praktyce każdy węzeł w drzewie jest realizowany na osobnej stronie fizycznej pamięci i zawiera więcej niż trzy wskaźniki i dwa kluczy.

W drzewie B(+) dostęp do dowolnego rekordu wymaga jednakowego czasu, ponieważ podczas przeszukiwania sprawdza się jednakowa ilość węzłów. Poza tym ten indeks jest pełnym (gęstym), tzn. każdy rekord jest adresowany indeksem. Dlatego sortować rekordy w pliku danych nie ma potrzeby, tzn. plik danych może przedstawiać sobą nieuporządkowany plik z dostępem szeregowym.






Pobieranie 8.37 Mb.

Share with your friends:
1   ...   33   34   35   36   37   38   39   40   ...   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