W poprzednim wykładzie zostały omówione trzy podstawowe organizacje pliku rekordów: nieuporządkowana, posortowana i haszowana. Ze względu na różne sposoby dostępu do rekordów w danym pliku (np. ze względu na wartości różnych pól) potrzebne są osobne struktury danych wspomagające te sposoby dostępu. Obiekty bazy danych, które odpowiadają tym strukturom danym, nazywają się indeksami.
Wykład składa się z trzech części. W pierwszej części są omawiane podstawy struktur indeksowych w tym ich klasyfikacja.
W drugiej części są omawiane podstawowe struktury danych dla indeksów.
W trzeciej części jest rozważany centralny dla operacji na bazie danych problem sortowania zewnętrznego.
W przykładach są używane tabele Emp i Dept znajome z nauki SQL i
PL/SQL.
Na początku tego wykładu przedstawimy ogólne definicje związane z indeksami oraz ogólne ich klasyfikacje.
Indeks jest to struktura danych na dysku umożliwiająca szybkie wyszukiwanie danych w bazie danych na podstawie wartości klucza wyszukiwania takiego jak np. nazwisko osoby. Indeks w bazie danych ma takie samo znaczenie jak skorowidz (indeks) w książce!
W najprostszej postaci wyszukiwanie polega na tym, że mając wartość poszukujemy rekordów, w których ta wartość występuje w danym polu.
Rys. 9.1 Wyszukiwanie rekordów według wartości w polu
Na przykład:
Operacja wyszukiwania może być nie trywialna do przeprowadzenia gdy liczba rekordów w pliku jest bardzo duża np. liczy kilkanaście milionów. Indeksy są strukturami danych, które wspomagają szybkie znajdowanie odpowiedzi na tego rodzaju zapytania.
Klucz wyszukiwania dla indeksu jest to wybrane pole lub pola rekordu względem których ma się odbywać wyszukiwanie. Indeks jest to struktura danych składająca się z węzłów, w których są zapisywane rekordy indeksu następujących postaci:
Zawartość indeksu jest przechowywana w pliku nazywanym plikiem indeksowym.
Indeks nazywamy pogrupowanym (wewnętrznym) (ang. clustered) gdy zachodzi przypadek 1i) w definicji pozycji danych oraz plik danych jest posortowany według wartości klucza wyszukiwania tego indeksu. W rezultacie, rekordy o tej samej wartości klucza lub zbliżonej znajdują się na tej samej stronie lub tylko na kilku stronach dyskowych. Może być tylko jeden indeks pogrupowany, bo plik danych można posortować według wartości tylko jednego klucza wyszukiwania. Indeks, który jest nie pogrupowany jest nazywany indeksem zewnętrznym.
Rys. 9.2 Dwa typy indeksów
Gdy klucz wyszukiwania zawiera klucz główny, indeks nazywa się indeksem
głównym.
Gdy klucz wyszukiwania zawiera klucz jednoznaczny, indeks nazywa się indeksem
jednoznacznym.
Złożone klucze wyszukiwania stanowią kombinację pól np. <sal,age>. W indeksie uporządkowanym kolejność pozycji danych w indeksie z kluczem złożonym jest oparta na porządku leksykograficznym.
Rys. 9.3 Pojedyncze i złożone klucze wyszukiwania
Na rysunku 9.3 oba indeksy ze złożonym kluczem wyszukiwania wspomagają wykonanie zapytania z
klauzulą WHERE: age=20 AND sal=75
Natomiast tylko indeks z kluczem <age,sal> wspomaga
wykonywanie zapytań
zakresowych z klazulami WHERE: age<20 oraz
age=20 AND sal>10
Pseudo-wartość NULL stanowi problem przy wyszukiwaniu przez indeks, ponieważ nie można o żadnej wartości powiedzieć czy jest równa NULL czy nie. Obsługa NULL jest potrzebna w indeksie ponieważ za pomocą indeksu sprawdzane są więzy spójności klucza jednoznacznego a w składowych wartości klucza jednoznacznego są możliwe wartości NULL. Przyjmiemy założenie, że indeksowane są wszystkie wiersze, w których co najmniej jedna składowa klucza wyszukiwania indeksu nie jest NULL.
Na przykład, z powodu NULL za pomocą indeksu na kolumnie Comm nie można zrealizować wyszukiwania wierszy z nieokreśloną wartością w polu Comm:
SELECT Ename
FROM Emp
WHERE Comm IS NULL;
Rozważymy kilka rodzajów
indeksów umożliwiających szybkie wyszukiwanie rekordów w dużym pliku rekordów.
Popularną metodą wyszukiwania klucza w pliku (w ciągu) posortowanym jest wyszukiwanie binarne. Porównujemy poszukiwany klucz z kluczem rekordu znajdującym się w środku ciągu i w zależności od wyniku porównania poszukujemy klucza albo w lewej części albo w prawej – stosując rekurencyjnie opisywaną metodę.
Jak wskazaliśmy to na poprzednim wykładzie, trudno jest stosować wyszukiwanie binarne do dynamicznego ciągu uporządkowanego. Ponadto musimy brać pod uwagę fakt, że elementy ciągu czyli rekordy nie znajdują się w indeksowanej tablicy, gdzie łatwo wyliczyć środkowy indeks, a tylko na dysku.
W przypadku przechowywania rekordów na dysku, wyszukiwanie binarne jest łatwiej zastosować - nie bezpośrednio do pliku rekordów - ale do pliku zawierającego same klucze rekordów k1< k2< … <kN: gdzie ki jest najmniejszym kluczem na stronie o numerze i. Plik z kluczami stanowi plik indeksowy.
Rys. 9.4 Jednopoziomowy plik indeksowy
Wyszukiwanie binarne, zamiast na pliku rekordów, zostaje wykonane na znacznie mniejszym pliku indeksowym! Po wyznaczeniu najbliższego pasującego klucza wystarczy przejść do strony, na której znajduje się rekord o danym kluczu, o ile jest taki w pliku.
Nie ma przeszkód aby, tak jak dla posortowanego ciągu rekordów, tym razem do pliku indeksowego dobudować kolejny poziom sekwencyjnego indeksu z kluczami rekordów. Możemy tak postępować aż otrzymamy pojedynczy węzeł, a wszystkie poziomy sekwencyjnych indeksów dadzą nam strukturę drzewa. Dobieramy tak liczbę elementów w węźle aby jego zawartość była zapisywana na jednej stronie (ewentualnie kilku sąsiednich).
Nie ma przeszkód aby, tak jak dla posortowanego ciągu rekordów, tym razem do pliku indeksowego dobudować kolejny poziom sekwencyjnego indeksu z kluczami rekordów. Możemy tak postępować aż otrzymamy pojedynczy węzeł, a wszystkie poziomy sekwencyjnych indeksów dadzą nam strukturę drzewa. Dobieramy tak liczbę elementów w węźle aby jego zawartość była zapisywana na jednej stronie (ewentualnie w jednym ekstencie czyli na kilku sąsiednich stronach). Powstające w ten sposób drzewo nazywamy drzewem ISAM (skrót od ang. Indexed Sequential Access Method).
Zauważmy, że przy reprezantacji ciągu uporządkowanego za pomocą drzewa, element "środkowy" znajdujemy w korzeniu drzewa a ograniczenie wyszukiwania do podciągu realizujemy przez przejście krawędzią na kolejny, niższy poziom w drzewie.
Strona indeksu (węzeł drzewa)
Rys. 9.5 Strona indeksu
Strona indeksu składa się z pozycji indeksu <Ki,Pi>,
gdzie Ki jest
kluczem a Pi jest wskaźnikiem do węzła niższego poziomu.
Pierwszą pozycję na stronie stanowi wskaźnik P0 do węzła niższego poziomu.
|
Na rysunku 9.6 są pokazane zasady wyboru gałęzi w poszukiwaniu danego klucza.
Rys. 9.6 Zasady wyboru
gałęzi przy wyszukiwaniu
Na rysunku 9.7 jest przedstawiona struktura drzewa ISAM.
Rys. 9.7 Struktura drzewa ISAM
Przykład drzewa ISAM
Rys. 9.8 Przykład drzewa ISAM
Wstawiamy 23*, 48*, 41*, 42*. Otrzymujemy drzewo ISAM:
Rys. 9.9 Drzewo ISAM po wstawieniach
Ponieważ na stronach głównych nie było wolnego miejsca, utworzyły się doczepione do nich strony nadmiarowe - tworzące listy nieuporządkowane.
Struktura stron indeksu i stron głównych jest niezmienna. Gdy nie wystarczy miejsca na stronach głównych, doczepiane są strony nadmiarowe. Może się zdarzyć, że do jednej strony głównej trzeba doczepić długą listę stron nadmiarowych, co spowoduje, że wyszukiwanie rekordów na takiej liście będzie wymagać sprowadzenia do pamięci RAM wielu stron i może trwać długo.
Reasumując, drzewa ISAM dobrze nadają się do wyszukiwania rekordu na podstawie
wartości jego klucza a także rekordów z zakresu wartości klucza: A<= klucz <=B lub
A<= klucz
lub klucz <=B. Gdy liczba rekordów w pliku
jest mniej więcej stała, struktura ISAM jest dobra. Z powodu niebezpieczeństwa
grupowania się kluczy w ciągi na stronach
nadmiarowych nie jest strukturą pewną w przypadku ogólnym. Na szczęście, istnieje jej niewielka modyfikacja do tak zwanych drzew B+, która nie ma już
tej wady.
Drzewo B+ (nazywane też B+ drzewem) jest to drzewo o strukturze drzewa ISAM, którego kształt dynamicznie zmienia się w zależności od liczby pozycji danych i w którym nie używa się stron nadmiarowych. Drzewo B+ jest wyważone względem wysokości (ang. height-balanced), to znaczy każdy liść znajduje się w nim na tej samej głębokości. Ponadto, wymagana zajętość każdej strony indeksu wynosi minimum 50% (z wyjątkiem korzenia).
Maksymalna długość ścieżki w drzewie B+ od korzenia do liścia jest co najwyżej clog N gdzie N = #liści gdzie c jest stałą uzależnioną od średniej liczby pozycji indeksu na jednej stronie. Stąd wynika, że wyszukiwanie/wstawianie/usuwanie pozycji danych odbywa się w czasie rzędu logarytmicznego clog N.
Wyszukiwanie zaczyna się w korzeniu a porównania klucza wyszukiwania prowadzą do liścia tak jak dla drzewa ISAM.
Rys. 9.10 Drzewo B+
Do pozycji z kluczem 5 dochodzimy porównując w korzeniu 5 z 13 i wybierając skrajnie lewą gałąź.
Wyszukując 15, w korzeniu znajdujemy gałąź po której należy zejść, mianowicie leżącą między kluczami 13 i 17. W liściu znajdujemy tylko elementy 14 i 16. To znaczy elementu 15 nie ma w tym drzewie.
Aby przekonać się czy element znajduje się w drzewie czy nie, wystarczy przejść ścieżką zaczynającą się w korzeniu drzewa a kończącą się w jednym z jego liści. Każdą stronę indeksu na tej ścieżce należy sprowadzić do buforu w pamięci RAM.
Aby wyznaczyć wszystkie elementy większe lub równe 24, znajdujemy najpierw element 24 (ogólnie najmniejszy element większy lub równy 24), następnie idąc w prawo po kolejnych liściach znajdujemy wszystkie elementy większe lub równe 24.
Przyjmujemy, że liście drzewa znajdują się na dwukierunkowej strukturze listowej - ułatwia ona wykonywanie zapytań zakresowych takich jak powyższe.
Tak jak opisaliśmy to na początku wykładu indeks może być pogrupowany i wtedy pozycje danych pokrywają się z rekordami danych – to znaczy rekordy danych są zapisywane w strukturze B+ drzewa zgodnie z porządkiem klucza wyszukiwania.
Albo indeks jest nie pogrupowany i wtedy rekordy z danymi są przechowywane poza indeksem w dowolnym porządku.
Dla jednej tabeli może być zbudowany tylko jeden indeks pogrupowany i wiele indeksów nie pogrupowanych względem różnych kluczy wyszukiwania.
W indeksie pogrupowanym zbudowanym na B+ drzewie rekordy z danymi są zapisywane na stronach reprezentujących liście drzewa. Z definicji algorytmów wstawiania i usuwania wynika, że rekordy mogą być przesuwane między stronami. To znaczy rekordy mogą zmieniać stronę a zatem nie może być do nich z zewnątrz bezpośrednich wskaźników używających identyfikatora strony. Za identyfikator rekordu używa się wtedy wartość jego klucza głównego a dostęp do rekordu jest realizowany poprzez indeks główny.
Są możliwe dwa przypadki. Na ogół, SZBD wymaga aby indeks pogrupowany był jednocześnie indeksem głównym. Wtedy wyszukiwanie rekordu według wartości klucza wyszukiwania indeksu nie pogrupowanego wymaga przejścia dwóch indeksów: najpierw nie pogrupowanego, w którym znajdujemy wartość klucza głównego szukanego rekordu, a następnie indeksu pogrupowanego głównego, w którym w oparciu o wartość klucza głównego znajdujemy szukany rekord.
Jest też możliwe, że indeks główny jest indeksem nie pogrupowanym, w którego pozycjach danych są zapisywane (zmienne) wskaźniki do rekordów. W tym przypadku, przy zmianie położenia rekordu w indeksie pogrupowanym jego adres w pozycji danych indeksu głównego też musi być uaktualniony. Reasumując, przy wyszukiwaniu rekordu przechodzimy tak jak poprzednio dwa indeksy: nie pogrupowany i główny. Natomiast przy zmianach położenia rekordu w indeksie pogrupowanym wymagane jest znalezienie pozycji danych tego rekordu w indeksie głównym i zapisanie w niej nowego adresu tego rekordu.
Zatem, z jednej strony
zbudowanie i użycie indeksu pogrupowanego przyśpiesza wyszukiwanie przez ten
indeks - szczególnie w przypadku mało selektywnego
wyszukiwania np. zakresowego dla indeksu pogrupowanego - jednak z drugiej strony spowalnia on wyszukiwania przez pozostałe indeksy.
|
Drzewa B+ w praktyce - oszacowania
|
Indeks jest zapisywany w pliku i jego strony są sprowadzane do buforów w pamięci RAM tak jak strony rekordów z danymi. Dla pliku indeksowego:
LRU nie jest dobrą metodą!
Dla drzew B+ lepszą strategią jest następująca:
Wszystkie komercyjne systemy zarządzania bazą danych implementują B+ drzewa, z tym że na ogół pozostawiają w drzewie usunięte pozycje indeksu i danych. Na życzenie użytkownika lub w przypadku gdy zajętość w drzewie spada poniżej pewnego progu – następuje wywołanie operacji REBUILD, która tworzy indeks od nowa lub COALESCE, która łączy ze sobą sąsiednie strony o zajętości poniżej 50%.
Gdy na samym początku mamy dany duży zbiór rekordów, to wtedy zamiast powtarzania kolejnych operacji INSERT opłaca się zastosować algorytm Bulk Loading, którego działanie polega na posortowaniu rekordów, a następnie dobudowaniu nad posortowanym ciągiem kolejnych poziomów indeksowych drzewa B+.
Dla pełności tematu pokazujemy na rys. 9.11 schemat węzła zwykłego B drzewa (bez plusa).
Rys. 9.11 Węzeł zwykłego B drzewa
Wyszukiwanie w zwykłych B drzewach jest szybsze. Natomiast z powodu
niejednolitości
węzłów dla B drzew
operacje INSERT i DELETE są bardziej skomplikowane. Dlatego w bazach danych preferuje się
B+ drzewa.
Podsumowanie drzew
|
Indeks haszowany umożliwia szybkie wyszukiwanie rekordów w oparciu o wartość klucza wyszukiwania. Nie umożliwia wyszukiwania zakresowego. Indeks haszowany jest oparty na tej samej strukturze danych tablicy haszowanej co plik haszowany.
Indeks haszowany to struktura danych oparta na rozłożeniu pozycji danych do segmentów (ang. bucket) na podstawie wartości funkcji haszującej od klucza wyszukiwania. Segment składa się ze strony głównej i ewentualnie listy stron nadmiarowych. Wartość funkcji haszującej określa adres strony głównej segmentu, gdzie należy szukać rekordu. W przypadku większej liczby rekordów tworzone są strony nadmiarowe doczepiane do strony głównej.
|
|
Rys. 9.12 Indeks haszowany
Przy prawidłowo dobranych: funkcji haszującej oraz wartości M prawie zawsze wszystkie pozycje danych znajdują się na stronie głównej i nie ma stron nadmiarowych (średnia długość listy stron dla jednej wartości funkcji haszującej wynosi 1.2). Stąd dla indeksu haszowanego średnia liczba operacji We/Wy przy wyszukiwaniu rekordu wynosi 1.2. (Używamy tu założenia, że adres segmentu dla danej wartości funkcji haszującej jest przechowywany bądź może być wyliczony w oparciu o informacje zapisane w buforze w RAM.)
Przykładowa funkcja haszująca:
h(k) = k mod M = numer segmentu, do którego należy pozycja danych o kluczu k (M = #segmentów).
Przykład indeksu haszowanego po wykonaniu ciągu operacji INSERT (przy założeniu 2 rekordów na stronie) jest pokazany na rys. 9.13.
Rys. 9.13 Przykład indeksu haszowanego
Mówimy o statycznym haszowaniu, gdy liczba segmentów jest ustalana na samym początku i nie zmienia się. Wraz ze wzrostem liczby pozycji danych (rekordów danych) zwiększa się rozmiar segmentów i co za tym idzie czas wyszukiwania, który jest proporcjonalny do liczby stron w segmencie. W przypadku dynamicznego haszowania liczba segmentów dopasowuje się dynamicznie do liczby pozycji danych. Oto dwie metody dynamicznego haszowania:
1. Okresowa (np. raz na dzień) przebudowa REBUILD pliku haszowanego przez zmianę liczby segmentów. Jest pożądane aby funkcja haszująca miała własność umożliwiającą łatwe podwojenie rozmiaru indeksu przez podział każdego segmentu na dwa. Wspomniana powyżej funkcja mod ma tę własność.
2. Metoda rozszerzalnego haszowania
Unika się stron nadmiarowych przez dynamiczną rozbudowę struktury segmentów. Wprowadza się pośredni katalog kierujący do stron. Gdy strona segmentu się przepełni, rozdziela się ją na dwie.
|
Podsumowanie klasyfikacji indeksów Klasyfikacja indeksów obejmuje cztery ortogonalne wymiary:
Własności indeksu wynikają z zaliczenia jego do odpowiedniej grupy uzyskanej przez wybór konkretnych czterech atrybutów z tych czterech wymiarów; na przykład: pogrupowany zwykły indeks drzewowy czy nie pogrupowany jednoznaczny indeks haszowany. |
Rozpatrzmy konkretny problem: posortować 2GB danych w buforze pamięci RAM rozmiaru 100MB. Klasyczne metody sortowania wewnętrznego w pamięci RAM nie dadzą się bezpośrednio zastosować.
W bazach danych tego typu problem sortowania pojawia się często. Oto przykłady:
Sortowanie zewnętrzne to problem sortowania pliku rekordów, który nie mieści się w pamięci wewnętrznej RAM.
Metodą stosowaną w bazach danych jest wielofazowe sortowanie zewnętrzne przez scalanie. Algorytm składa się z dwóch etapów:
Etap 1: Tworzenie początkowych uporządkowanych bloków rekordów (ang. run) – za pomocą jednej z metod sortowania wewnętrznego i dystrybucja ich do dwóch lub więcej obszarów dyskowych. Oznaczmy ich liczbę przez B.Etap 2: Wielofazowe odczytywanie obszarów dyskowych z danymi, scalanie kolejnych bloków z zapisywaniem ich do obszarów dyskowych – powtarzane dopóki nie otrzyma się pojedynczego, uporządkowanego bloku rekordów.
Rys. 9.15 Scalanie danych w puli buforów
W każdej fazie odczytujemy i zapisujemy każdą stronę w pliku.
Rys.9.16 Przykład wielofazowego sortowania zewnętrznego przez scalanie
Liczba operacji We/Wy przy wykonywaniu sortowania zewnętrznego jest <= 2N*#faz gdzie N jest liczbą stron w pliku rekordów a współczynnik 2 bierze się stąd, że każdą stronę trzeba odczytać i zapisać.
W praktyce średnio liczba faz scalania nie przekracza 3. Łącznie z fazą tworzenia początkowych bloków liczba wszystkich faz jest średnio co najwyżej 4. Zatem liczba operacji We/Wy potrzebnych do wykonania sortowania zewnętrznego jest co najwyżej 8N (N jest liczbą stron w pliku rekordów).
Załóżmy, że na pliku rekordów jest założony indeks na B+ drzewie z uporządkowaniem względem wartości klucza sortowania. Czy przejście po liściach tego drzewa od lewej strony do prawej z wypisywaniem kolejnych rekordów jest dobrą metodą sortowania względem wartości klucza sortowania (klucza indeksu)? Tak, ale tylko wtedy, gdy indeks jest pogrupowany!
Jeśli indeks nie jest pogrupowany trzeba ściągnąć do pamięci wewnętrznej tyle stron dyskowych ile jest rekordów (a nie tyle, na ilu stronach są zapisane rekordy w pliku!) – co przy dużej liczbie rekordów może dać czas większy niż czas wielofazowego sortowania przez scalanie ~ 8N operacji We-Wy, gdzie N jest liczbą stron w pliku rekordów.
Rys. 9.17 Ilustracja indeksu nie pogrupowanego.
Zaletą sortowania za pomocą B+ drzew jest interaktywny charakter wyznaczania wyników. W przeciwieństwie do sortowania zewnętrznego wypisywanie wyników na ekran użytkownika może się rozpocząć prawie natychmiast bez konieczności obliczania całości. Gdy użytkownik ogląda pierwszą partię wyników, w tym czasie system może wyliczać następną ich część.
W wykładzie tym zaznajomiliśmy się z budową indeksów oraz z sortowaniem zewnętrznym.
klucz wyszukiwania (rekordu) - wybrane pola rekordu względem których ma odbywać się wyszukiwanie. Może być wiele kluczy wyszukiwania rekordu.
indeks - struktura danych na dysku umożliwiająca szybkie wyszukiwanie danych w bazie danych na podstawie klucza wyszukiwania rekordu np. nazwiska osoby. Indeks jest zapisywany w pliku nazywanym indeksowym.
plik indeksowy - plik, w którym jest przechowywany indeks.
indeks pogrupowany - indeks, który organizuje pozycje danych i rekordy danych w kolejności uporządkowanej względem wartości klucza wyszukiwania. Oznacza to, że rekordy o tej samej wartości klucza lub zbliżonej znajdują się na tej samej stronie lub tylko kilku stronach dyskowych. W przeciwnym razie indeks nazywamy niepogrupowanym. Może być tylko jeden indeks pogrupowany ale wiele niepogrupowanych.
indeks główny - indeks, którego klucz wyszukiwania zawiera klucz główny. Może być tylko jeden indeks główny.
indeks jednoznaczny - indeks, którego klucz wyszukiwania zawiera klucz jednoznaczny. Może być wiele indeksów jednoznacznych.
drzewo ISAM - implementacja indeksu w postaci statycznego drzewa opartego na wyszukiwaniu binarnym.
drzewo B+ - implementacja indeksu w postaci dynamicznego drzewa opartego na wyszukiwaniu binarnym.
indeks haszowany - implementacja indeksu w postaci tablicy haszowanej.
sortowanie zewnętrzne - sortowanie pliku danych, który nie mieści się w pamięci wewnętrznej RAM.
wielofazowe sortowanie zewnętrzne przez scalanie -
podstawowa metoda sortowania zewnętrznego. Składa się z dwóch etapów:
tworzenia początkowych uporządkowanych bloków rekordów
– za pomocą jednej z metod sortowania wewnętrznego oraz wielofazowego odczytywania uporządkowanych bloków rekordów
i sukcesywnego ich scalania, dopóki nie otrzyma się pojedynczego uporządkowanego bloku
rekordów.
1. Opracuj algorytmy dynamicznego haszowania rozwijając idee 1 i 2 naszkicowane w czasie wykładu.