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 znaleźć

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 znaleźć 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ą

dostęp do

danych

Zajmują

miejsce na

dysku

Wymuszają

unikatowość

wierszy

Zwiększają

obciążenie

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 wskaź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 wskaź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 wskaźnikami do poziomu niżej w

drzewie indeksu.
Strony poziomu pomocniczego zwane też liśćmi (ang. leaf)

zawierają wskaźniki do konkretnych stron danych (które nie

są posortowane). Wskaź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 ź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ą