Indeksy
Wstęp
Indeksy są specjalnym mechanizmem bazy danych, który
pozwala na przyspieszenie wyszukiwania danych. Jest to
niewątpliwie bardzo ważny parametr charakteryzujący bazę
danych.
Szczególnie w bazach zawierających wiele tysięcy rekordów
mechanizm indeksów jest niezbędny do zapewnienia
rozsądnych czasów wyszukiwania danych
Przegląd zagadnień
Dostęp fizyczny do danych
Optymalizacja dostępu
Indeksy i ich zastosowanie
Rodzaje indeksów
Operacje na indeksach
Podsumowanie
Laboratorium
Dostęp fizyczny do danych
Jak wiadomo, dane w bazach danych w sposób trwały są
zapisywane na dyskach optycznych, magnetycznych lub
rodzinach nośników o dostępie bezpośrednim takich jak
macierze RAID.
SZBD najczęściej nie zajmuje się fizyczną obsługą dysków.
W procesie dostępu do danych biorą udział: menedżer
plików i menedżer dysku.
Menedżer plików ma odpowiednią wiedzę o strukturze
systemu plików i jest odpowiedzialny za odszukanie
odpowiedniego pliku.
Menedżer dysku ma natomiast niezbędną wiedzę na temat
fizycznej organizacji dysku i jest odpowiedzialny za
odnalezienie odpowiedniej strony danych.
Dostęp fizyczny do danych
Schemat łańcucha dostępu do danych
Optymalizacja dostępu
Zasadniczy czas dostępu do danych bazy to czas odczytu
tych danych z dysków.
W celu optymalizacji tego dostępu stosuje się metodę zwaną
klastrowaniem.
Klastrowanie polega na dążeniu do utrzymania blisko siebie
na dysku rekordów, które są logicznie powiązane.
Taka organizacja danych znacznie przyspiesza dostęp do
danych.
Aby odczytać dane powiązane i w związku z tym zapewne
razem wykorzystywane i odczytywane, głowica nie musi
wykonywać dużych ruchów, a tym samym maleją czasy
wyszukiwania.
Optymalizacja dostępu
Rozróżniamy przy tym dwa rodzaje klastrowania:
klastrowanie wewnątrzplikowe,
klastrowanie międzyplikowe.
Klastrowanie wewnątrzplikowe polega na grupowaniu
rekordów obok siebie wewnątrz jednego pliku.
Klastrowanie międzyplikowe polega na umieszczaniu na
stronie obok siebie rekordów pochodzących z więcej niż
jednego pliku (tabeli).
Optymalizacja dostępu do danych sprowadza się w zasadzie
do odpowiedniego zarządzania stronami i decydowania w
jaki sposób dane mają być klastrowane.
Optymalizacja dostępu
Jak to pokazano na powyższym rysunku, wszystkie
dane z tabeli relacyjnej bazy danych są
przechowywane na stronach danych (ang. page) na
dysku.
W serwerze MS SQL strona danych ma wielkość 8 KB.
Strony tworzą większe struktury zwane stertami (ang.
heap).
Optymalizacja dostępu
Sterta jest kolekcją stron danych. W każdej tabeli dane są
przechowywane w kolekcji 8 kilobajowych stron. 8 ciągłych
stron tworzy zakres (ang. extent).
Wiersze danych nie są na stronach przechowywane w
szczególnej kolejności, a strony danych nie są połączone w
listę. Jeśli podczas wstawiania danych do strony, strona
ulega przepełnieniu, to wtedy następuje podział takiej strony.
Ponieważ jeden wiersz tabeli musi zmieścić się na stronie
danych, więc w serwerze MS SQL występuje ograniczenie
co do wielkości wiersza i wynosi ono 8060 bajtów (ponieważ
na stronie zapisywane są jeszcze metadane -informacje o
obiekcie, którego dane przechowuje strona itd., dane nie
zajmują dokładnie pełnych 8 KB).
Optymalizacja dostępu
Indeksy i ich zastosowanie
Zastanowimy się teraz nad problemem wyszukiwania danych
w tabeli. Załóżmy, że w tabeli Studenci chcemy znalez
ć
studenta o nazwisku Nowak.
ID Nazwisko Imie Wydzial
1 Olacki Jan Elektryczny
2 Babicki Adam Mechaniczny
3 Nowak Jerzy Elektryczny
4 Adamski Adam Elektronika
Wiersze zapisane są w bazie w kolejności ich wpisywania i nie
są w szczególny sposób sortowane.
Co robi wobec tego system, kiedy wydajemy polecenie
odnalezienia rekordu zawierającego informacje o Nowaku
SELECT imie, nazwisko FROM Studenci
WHERE Nazwisko = 'Nowak'
Indeksy i ich zastosowanie
System musi przeszukać całą tabelę (skanowanie
wszystkich stron danych zawierających dane z tabeli) i
przejrzeć wszystkie rekordy tej tabeli, aby mieć pewność, że
odnalazł rekordy zawierające nazwiska Nowak. Operacja
taka jest oczywiście czasochłonna.
Podobnie jest, gdy w książce poszukujemy jakiegoś hasła
(na przykład w podręczniku do baz danych szukamy
informacji o indeksach).
Aby znalez
ć szukaną informację, powinniśmy przeczytać
całą książkę.
Na szczęście niektóre książki są wyposażone na końcu
w specjalne zestawienie haseł - czyli w indeks haseł.
Indeksy i ich zastosowanie
Nasze postępowanie przebiega wówczas następująco:
1. Odszukujemy poszukiwane hasło w indeksie, które jest
uporządkowany alfabetycznie (co znacznie ułatwia
nam odnalezienie hasła).
2. Odczytujemy w indeksie numer strony na której hasło
to występuje w książce.
2. Otwieramy książkę na odpowiedniej stronie.
3. Przeglądamy stronę w poszukiwaniu naszego hasła.
4. Odczytujemy informacje związane z szukanym
hasłem.
Idea działania indeksów w bazie danych jest dokładnie taka
sama.
Indeksy i ich zastosowanie
Indeks określony na atrybucie A relacji jest
mechanizmem, który pozwala na efektywne
wyszukiwanie krotek o ustalonej wartości składowej
atrybutu A.
Jak więc wyglądałby indeks dla tabeli Studenci?
Indeks określany jest dla konkretnego pola. Mówimy wówczas, że pole to
jest polem indeksowanym. W wypadku tabeli Studenci możemy jako
pole indeksowane wybrać pole nazwisko. Wówczas założenie indeksu na
tym polu będzie oznaczało założenie przez system dodatkowej tabeli, w
której umieszczone zostaną nazwiska studentów z tabeli Studenci oraz
dostarczy przesłankę, gdzie należy szukać (na której stronie danych)
pełnej informacji o danym studencie. Dodatkowo rekordy w tabeli indeksu
zostaną posortowane w kolejności alfabetycznej nazwisk. Poszukiwanie
studenta Nowaka będzie teraz przebiegać znacznie szybciej.
Indeksy i ich zastosowanie
Zalety Wady
Przyspieszają Zajmują
dostęp do miejsce na
danych dysku
Wymuszają Zwiększają
unikatowość obciążenie
wierszy systemu
Działanie i rola indeksów polega głównie na przyspieszeniu
wyszukiwania rekordów w bazie danych.
Niestety obciążają one dodatkowo system w czasie aktualizacji lub
wstawiania danych. SZBD musi bowiem oprócz umieszczenia rekordu w
bazie dokonać też wpisu w tabeli indeksu oraz ponownie posortować
rekordy tabeli indeksu.
Niektóre z pól warto jest indeksować, inne natomiast nie powinny
być nigdy indeksowane.
Indeksy i ich zastosowanie
Warto indeksować następujące pola:
klucze podstawowe i obce (często są automatycznie
indeksowane),
pola, po których często następuje wyszukiwanie,
pola, do których dostęp następuje w ustalonej,
uporządkowanej kolejności.
Nie należy indeksować:
pól, do których rzadko odwołują się zapytania,
pól, które zawierają tylko kilka wartości unikatowych,
pól zawierających dane typu image, bit czy obiekt OLE.
Indeksy i ich zastosowanie
Indeksy mogą być zakładane na jednym polu lub na większej liczbie pól
jednocześnie.
Dostęp do danych z wykorzystaniem indeksów nie zawsze jest najlepszym
rozwiązaniem. Czasem lepiej jest nie korzystać z indeksów, ale bezpośrednio
skanować tabelę.
SZBD sprawdza, czy dla danej tabeli istnieją indeksy, a następnie optymalizator
zapytań analizuje zapytanie i podejmuje decyzję, czy dostęp do danych będzie
prowadzony poprzez skanowanie tabeli, czy przy wykorzystaniu indeksu.
Rodzaje indeksów
Indeksy można klasyfikować w różny sposób.
Zasadniczo dzielimy je na dwie grupy:
indeksy grupowane (klastrowe),
indeksy niegrupowane (nieklastrowe).
Rodzaje indeksów 
Indeksy grupowane (ang. clustered)
Indeks grupowany działa na podobnej zasadzie jak książka
telefoniczna. Zawiera strony szybkiego dostępu do danych
(w książce telefonicznej na początku znajduje się
alfabetyczny spis mówiący o tym, na której stronie szukać
nazwisk, firm czy instytucji zaczynających się na daną literę
alfabetu).
Strony te są ułożone w odwrócone drzewo i przechowują
tylko ułożone alfabetycznie wartości indeksowanego pola
oraz wskaz
niki do stron znajdujących się w niższej warstwie
drzewa.
Na samym dole drzewa znajdują się strony zawierające
posortowane wg indeksowanego pola dane (w książce
telefonicznej zawartość też jest posortowana - wg nazwisk
lub nazw firm czy instytucji).
Rodzaje indeksów 
Indeksy grupowane (ang. clustered)
Przeszukiwanie indeksu odbywa się z góry na dół na
następującej zasadzie: porównywana jest szukana wartość
pola indeksowanego z wartościami zapisanymi (i
posortowanymi) na stronach indeksu - jeśli znajdzie się
wartość "większa" od wartości szukanej, wtedy następuje
skok jeden poziom niżej do strony wskazywanej przez
ostatnią pozycję (na ostatnio sprawdzej stronie), która nie
była "większa" od szukanej wartości.
Każda pozycja na stronach zawiera wskaz
nik do strony
danych jeden poziom niżej w hierarchii indeksu. Dzięki takiej
strukturze przeszukiwane są tylko wybrane strony z danymi,
nie zaś wszystkie strony zawierające dane z wybranej tabeli.
Rodzaje indeksów 
Indeksy grupowane (ang. clustered)
W indeksie grupowanym strony z danymi wchodzą w
skład indeksu i są posortowane po tym polu tabeli, które
jest indeksowane. Wynika z tego, że na indeks grupowany
należy przeznaczyć więcej miejsca na dysku niż na same
dane (posortowane dane + strony indeksu z najwyższych
warstw).
W związku z przedstawioną powyżej zasadą działania
indeksów nie wszystkie zapytania wykorzystują indeksy.
Np. zapytanie (w MS SQL Server)
SELECT imie, nazwisko FROM osoby
WHERE nazwisko LIKE '%mar%
nie wykorzysta indeksu na polu nazwisko, ponieważ
niemożliwe będzie porównanie wartości wzorca z
wartościami na stronach indeksu.
Rodzaje indeksów
Indeksy grupowane
Indeks grupowany może być dla danej tabeli tylko jeden
(jednoznaczne sortowanie danych w indeksie).
W MS SQL Server na wszystkich polach będących kluczami
głównymi tabel są domyślnie zakładane indeksy
grupowane.
Rodzaje indeksów 
Indeksy niegrupowane (ang. nonclustered)
Indeks niegrupowany działa na podobnej zasadzie jak indeks
typowej w książce (ale nie w telefonicznej).
Indeks niegrupowany budowany jest na stronach danych,
które nie są sortowane.
Składa się z co najmniej dwu poziomów: poziomu
niepomocniczego i poziomów pomocniczych. Na stronach
poziomu niepomocniczego podobnie jak w przypadku
indeksu grupowanego przechowywane są wartości
indeksowanego pola ze wskaz
nikami do poziomu niżej w
drzewie indeksu.
Strony poziomu pomocniczego zwane też liśćmi (ang. leaf)
zawierają wskaz
niki do konkretnych stron danych (które nie
są posortowane). Wskaz
nik taki zawiera następujące dane:
ID pliku, numer strony, numer wiersza na stronie.
Rodzaje indeksów 
Indeksy niegrupowane (ang. nonclustered)
Przeszukiwanie indeksu niegrupowanego odbywa się na
podobnej zasadzie, jak w indeksie grupowanym.
Po dojściu do poziomu pomocniczego następują skoki do
stron danych (do konkretnych wierszy).
Rodzaje indeksów 
Indeksy niegrupowane (ang. nonclustered)
Maksymalna ilość indeksów niegrupowanych w pojedynczej
tabeli zależy od SZBD.
W MS SQL Server 2000 w jednej tabeli można utworzyć
maksymalnie 249 takich indeksów.
Indeksy mają kluczowe znaczenie dla optymalizacji
wydajności baz danych. Dobrze zaprojektowane indeksy
mogą znacząco poprawić szybkość operacji przeszukiwania
bazy danych (najczęściej wykonywana operacja i dotyczy
największych ilości danych), ale z
le zaplanowane mogą
spowodować efekt odwrotny do pożądanego. Dlatego należy
starannie zaplanować ich strukturę.
Operacje na indeksach
Indeksy są tworzone najczęściej automatycznie dla kluczy
głównych oraz dla pól, dla którym ma być wymuszona
unikatowość.
Indeksy można też tworzyć dla innych pól korzystając z
polecenia języka SQL CREATE INDEX.
Poniżej podano przykład utworzenia indeksu
grupowanego dla tabeli memeber dla pola lastname.
Operacje na indeksach
Indeksy mogą wymuszać unikatowość pól lub nie.
Przykład deklaracja indeksu wymuszającego unikatowość
pola title_no podano poniżej.
Po założeniu takiego indeksu dodanie do tabeli rekordu o
istniejącej już wartości pola title_no nie będzie możliwe.
Operacje na indeksach
Indeks może też być zakładany na kilku polach jednocześnie. Poniższy
przykład pokazuje sposób definiowania unikalnego indeksu na polach isbn i
copy_no jednocześnie.
Założenie takiego indeksu spowoduje, że będzie można wprowadzić do tabeli
rekord o istniejącej już wartości pola isbn oraz rekord o istniejącej wartości
pola copy_no. Nie będzie natomiast możliwe wprowadzenie rekordu, w którym
para wartości isbn i copy_no będzie się powtarzać.
Podsumowanie
Indeksy stanowią ważny mechanizm przyspieszający dostęp
do danych zapisanych w bazie i wymuszający unikatowość
danych.
Z drugiej jednak strony obciążają dodatkowo system w
czasie wykonywania operacji aktualizacji i wstawiania
danych.
Dlatego też indeksy należy stosować z rozwagą starannie
planując, gdzie jakiego rodzaju indeksy założyć.
Decyzje o zakładaniu indeksów wynikają często ze specyfiki
użytkowania bazy (np. kryteriów wyszukiwania) i często są
podejmowane w czasie pierwszego okresu użytkowania
bazy - okresu dostrajania systemu.
Podsumowanie
Dostęp fizyczny do danych
Optymalizacja dostępu
Indeksy i ich zastosowanie
Rodzaje indeksów
Operacje na indeksach
Laboratorium
Przygotowanie tabeli
Wykonanie zapytania bez optymalizacji
Stworzenie indeksu
Wykonanie zapytania z optymalizacją