Index w bazie danych Oracle (innych też) jest strukturą powiązaną z tabelą, która pozwala przyspieszyć dostęp do danych. Index tworzy się na jednej lub kilku kolumnach tabeli. W tym wpisie (kursie) pokaże Ci czym jest i jak jest zbudowany oraz na co zwracać uwagę przy budowie indexu.

Ten wpis jest częścią Kurs Oracle SQL

Stosowanie indeksu jest jednym z podstawowych sposobów przyspieszania zapytań wyszukujących danych “SELECT”.

Złożoność znalezienia rekordu w zwykłej tabeli wynosi O(n) co oznacza, że w najgorszym przypadku należy wykonać n operacji aby znaleźć szukany rekord. Czyli gdy mamy tabelę zawierającą 1 000 000 000 (miliard) rekordów co jest całkiem standardową wielkością tabel w wielu bazach należy wykonać ok 1 000 000 000 operacji.

Złożoność znalezienia rekordu w indeksie (B-tree) wynosi O(logMn) gdzie M jest rzędem drzewa czyli w uproszczeniu jest to możliwa ilość kluczy w węźle. Dla analogicznego przykładu wyszukania jednego rekordu z indeksu wielkości 1 000 000 000 rekordów wyszukanie dla M=2 wynosi 30 operacje (pomijam tu oczywiście koszty na stworzenie i utrzymanie samego indeksu).

Budowa indeksu B-tree

B-tree index jest najczęstszym typem indexu w bazie Oracle. B-tree jest uporządkowaną listą wartości podzielonych na zakresy które dzielą się na dwa typy bloków:

  • Blok gałęzi “Branch Block” służący do wyszukiwania. Blok ten przechowuje minimalny prefiks z klucza potrzebny do podjęcia decyzji o rozgałęzieniu.
  • Blok liścia “Leaf Block” zawiera każdą indeksowaną wartość danych i odpowiadający jej wiersz używany do zlokalizowania rzeczywistego wiersza (ROWID). Sąsiadujące bloki liści są ze sobą powiązane. Dodatkowo bloki liści są posortowane według klucza i wartości.
index B tree
Index B-tree w Oracle

Na schemacie przedstawiony został przykład indeksu dla niewielkiej tabeli. Na szczycie widzimy, szczególny przypadek bloku gałęzi “root block” który jest miejscem wejścia do indeksu.

Blok ten wskazuje na rozgałęzienia 0-10 który wskazuje na lewy blok oraz 11-20 który wskazuje na prawy blok. Blok 0-10 rozgałęzia się dalej na bloki 0-3, 4-6 i 7-10. Każdy z tych bloków wskazuje na bloki liści z odpowiadającymi wartościami.

Indeks drzewa B jest zrównoważony, oznacza to że, wszystkie bloki liści pozostają na tej samej głębokości. Powoduje to, że pobieranie dowolnego rekordu z danymi zajmuje w przybliżeniu tyle samo czasu.

Same bloki liści poza tym, że są powiązane z blokami gałęzi są również powiązane między sobą. I tak np. blok 0-3 jest powiązany z blokiem 0-6 a ten z kolei z blokiem 0-7 itd. Zgodnie z dokumentacją bloki te nie muszą być powiązane w posortowanej kolejności co oznacza, że np. blok 0-3 może mieć powiązanie do bloku 14-16

Dane w samym liściu są również posortowane co oznacza, że baza danych podczas poszukiwania indeksu nie musi skanować całego liścia a jedynie rekordów których szuka.

Klucz indeksu

Kluczem indexu jest minimalny prefiks wartości potrzebny do podjęcia decyzji o rozgałęzieniu. Oznacza to w skrócie, że pierwsza kolumna lub kolumny w indeksie są kluczem a dokładniej to podzbiór tych wartości ponieważ nie musi to być dokładnie ta wartość a wystarczy jej minimalna część. W związku z tym, że indeks posortowany jest głównie po kolumnach w nim występujących bardzo ważne jest aby świadomie ustawić kolejność kolumn w indeksie. Szczególnie ważna jest pierwsza kolumna która nieraz może wystarczyć do przeszukiwania indeksu.

Unikalność klucza

W Oracle wystąpić mogą dwa rodzaje indeksu ze względu na unikalność klucza: indeks unikalny “unique” oraz indeks nieunikalny “nonunique”.

Unikalne indeksy gwarantują, że żadne dwa wiersze indeksu nie mają tych samych wartości w kluczu. Najczęściej indeksy unikalne są wtedy gdy zakładamy indeks na ID kolumny gdzie ID jednoznacznie określa rekord i w całej tabeli nie występują dwa rekordy z tym samym ID. W tej sytuacji dane w bloku liścia sortowane są tylko według klucza.

Nieunikalny indeks umożliwiają duplikowanie wartości w indeksowanej kolumnie lub kolumnach. Dla indeksu nonuniqe w liściu dane posortowane są po kluczu a następnie po rowid. Taki indeks często występuje gdy dana wartość w kolumnie tabeli może pojawić się kilka razy np. imię, nazwa ulicy, nr buta.

NULL w indeksie

Index typu B-tree nigdy nie przechowuje wartości całkowicie nullowych. Oznacza to, że dla indeksu jednokolumnowego baza nie przechowuje w ogóle wartości null. Konsekwencją zakładania indeksów na kolumny które mogą przechowywać nulle jest nieraz niemożność wykorzystania indeksu w przeszukiwaniu.

Podsumowanie

Indeks B-tree nie jest jedynym rodzajem indeksu występującym w Oracle ale jest zdecydowanie najpopularniejszy. Dzięki nim nasze bazy w ogóle działają i mamy szansę dostać się do naszych danych. Pozwalają nam na znalezienie w bazie klienta w ciągu milisekund.

Stosowanie indeksów oczywiście ma również swoje negatywne skutki jak spowolnienie operacji INSERT. Nieraz zdarza się, że w bazie przestrzeń na indeksy jest większa jak przestrzeń na dane a przeliczanie indeksów zajmuje całą noc jednak o tym poświęcony będzie inny wpis.

W kolejnym wpisie:

  • Przedstawię w jaki sposób praktycznie wykorzystać indeksy typu B-tree.
  • Pokażę, jak tworzyć oraz jakie znaczenie ma kolejność i rodzaj kolumn.
  • Nauczę jak pisać zapytania aby wykorzystać Indeksy
  • Pokażę na przykładach różne rodzaje metod dostępu do danych oraz jak nimi sterować poprzez tworzenie indeksów oraz jaki wpływ na zachowanie indeksu mają dane.
  • Poza wiedzą praktyczną pokażę, jak indeks działa, jaka jest sekwencja działań na bazie.
  • Jeżeli chcesz znaleźć więcej kursów dla średniozaawansowanych oraz poznać zasady optymalizacji zapytań zapoznaj się z pozostałymi kursami, sprawdź: Kurs Oracle SQL
  • Jeżeli chcesz poznać podstawy baz danych i kurs dla początkujących w SQL odwiedź Kurs SQL

2 komentarze

Dodaj komentarz

Twój adres e-mail nie zostanie opublikowany. Wymagane pola są oznaczone *