BD-1st-2.4-lab8.tresc-1.1-Slajd8
Indeksy
Rozważmy sytuację, w której w bazie danych znajdują się relacje, składujące dane, dla których nie założono żadnych struktur wspomagających przeszukiwanie tych relacji. W takiej sytuacji, realizacja dowolnego zapytania wymaga przynajmniej jednokrotnego przeczytania całej relacji w poszukiwaniu krotek spełniających warunek selekcji. Jak łatwo zauważyć, nawet jednokrotne przeczytanie relacji może zająć dużo czasu, gdyż bazy danych potrafią osiągać olbrzymie rozmiary. W celu przyspieszenia realizacji zapytań i ograniczenia wymaganej liczby odczytów z dysku stosuje się indeksy. W zależności od typów wspieranych zapytań indeksy mogą mieć różną strukturę. Ponieważ omawianie różnych typów indeksów nie wchodzi w zakres tego ćwiczenia omówimy jedynie pokrótce strukturę indeksu typu B+drzewo, który jest jednym z najpopularniejszych indeksów i jest stosowany w prawie każdym SZBD.
Na rysunku przedstawiono strukturę przykładowego indeksu typu B+drzewo, zbudowanego w celu wspierania realizacji zapytań na atrybucie NAZWISKO relacji PRACOWNICY. Pomarańczowe prostokąty na rysunku reprezentują pojedyncze bloki dyskowe, a zawarte w nich napisy, dane składowane w tym blokach. Niebieskie strzałki reprezentują wskaźniki, czyli lokalizacje innego bloku na dysku. Jak łatwo zauważyć, struktura przedstawiona na rysunku jest zrównoważonym drzewem. Każdy węzeł drzewa jest reprezentowany przez jeden blok dyskowy, a w każdym bloku dyskowym (w niniejszym przykładzie) można zapisać maksymalnie dwa nazwiska i trzy wskaźniki. W ogólności zawsze w węźle składowane jest n wartości atrybutu i n+1 wskaźników. Zacznijmy analizę węzłów tworzących liście B+drzewa. W kolejnych węzłach liści składowane są posortowane wartości atrybutu na którym założono indeks. Z każdą wartością atrybutu skojarzony jest wskaźnik, który wskazuje na położenie na dysku krotki, z której wartość ta pochodzi. Dodatkowy wskaźnik w liściu wskazuje na kolejny blok tworzący liść. Liście B+drzewa tworzą zatem posortowaną listę wartości atrybutu na którym założono indeks. Wskaźniki w węzłach pośrednich składowane są na przemian z wartościami atrybutu. Każdy z tych wskaźników wskazuje na węzeł niższego poziomu. Pierwszy wskaźnik w węźle pośrednim wskazuje na węzeł niższego poziomu, w którym wszystkie wartości są „mniejsze” od pierwszej wartości atrybutu w węźle. Przykładowo, pierwszy wskaźnik w węźle oznaczonym przez (1) wskazuje na węzeł, w którym znajdują się nazwiska „Dolny” i „Grzybowska”, które są w porządku alfabetycznym wcześniej niż nazwisko „Janicki”, które jest pierwszą wartością w węźle (1). Kolejne wskaźniki w węźle pośrednim B+drzewa wskazują na węzły niższego poziomu, w których znajdują się wartości większe lub równe wartości przed wskaźnikiem i mniejsze od wartości znajdującej się za wskaźnikiem. Przykładowo, drugi wskaźnik w węźle (1) wskazuje na węzeł zawierający wartości większe lub równe wartości „Janicki” i mniejsze od wartości „Kotlarczyk”. Ostatni wskaźnik w węźle pośrednim wskazuje na węzeł, w którym znajdują się wartości większe lub równe ostatniej wartości w węźle. Przykładowo, ostatni wskaźnik w węźle (1) wskazuje na węzeł, w którym znajdują się wartości większe lub równe wartości „Kotlarczyk”.
Indeks B+drzewo wspiera zapytania punktowe (ang. unique scan ), np. SELECT * FROM pracownicy WHERE nazwisko=‘Kowalski’, zapytania przedziałowe (ang. range scan ), np. SELECT * FROM pracownicy WHERE nazwisko BETWEEN ‘Krakowska’ AND ‘Nowicki’ oraz wspomaga sortowanie danych w relacji według atrybutu na którym założono indeks. Przykładowy sposób realizacji zapytania punktowego pokazuje czerwona linia oznaczona na rysunku przez (2). W zapytaniu tym szukamy krotki, w której wartość atrybutu nazwisko jest równa „Kowalski”. Realizację zapytania rozpoczyna się od korzenia. Ponieważ nazwisko „Kowalski” jest alfabetycznie przed nazwiskiem „Marecki” odczytujemy kolejny węzeł wskazywany przez wskaźnik umieszczony przed wartością „Marecki”. W kolejnym węźle okazuje się, że nazwisko „Kowalski” znajduje się w porządku alfabetycznym za nazwiskiem „Kotlarczyk”, a zatem wędrujemy wzdłuż wskaźnika znajdującego się za wartością „Kotlarczyk”. Po dotarciu do liścia jesteśmy w stanie sprawdzić, czy nazwisko „Kowalski” znajduje się w ogóle w relacji, i jeżeli tak, to można w łatwy sposób odczytać wskaźnik na krotkę z tym nazwiskiem. Zapytania przedziałowe realizowane są w podobny sposób. Odszukiwana jest pierwsza wartość przedziału szukanych wartości, a następnie, wykorzystując fakt, iż liście są zorganizowane w postaci listy, odczytywane są kolejne wartości, aż do napotkania wartości stanowiącej koniec wyszukiwanego przedziału. Realizację przykładowego zapytania przedziałowego pokazuje zielona linia, oznaczone na rysunku przez (3). W zapytaniu tym szukamy wszystkich krotek, w których nazwisko jest alfabetycznie większe lub równe nazwisku „Krakowska” i mniejsze lub równe nazwisku „Nowicki”. W pierwszym etapie odszukiwane jest w indeksie nazwisko „Krakowska”, a następnie, wędrując wzdłuż wskaźników do kolejnych liści, odczytywane są kolejne wartości i skojarzone z nimi wskaźniki do krotek. Napotkanie nazwiska „Nowicki” kończy realizację zapytania. Wspieranie sortowania polega na odczycie kolejnych wartości z listy utworzonej z liści B+drzewa, które są zawsze posortowane.
