Indeksy w SQL Server - podstawy teoretyczne

Co to jest indeks?

Indeks w bazie danych to rodzaj struktury ściśle związanej z tabelą lub widokiem, która pomaga w znaczny sposób przyspieszyć pobieranie danych z tych źródeł. Indeks zawiera klucze zawierające jedną, bądź kilka połączonych kolumn tabeli lub widoku. Klucze w indeksie przechowywane są w strukturze zwanej B-drzewem (nie należy mylić tej struktury danych z drzewem binarnym). B-drzewo pozwala mechanizmom SQL Server znaleźć pożądany rekord szybciej i wydajniej, ale tylko wtedy, gdy wyszukiwanie w tym drzewie odbywa się za pomocą klucza.

B-drzewa

B-drzewo, jak sama nazwa wskazuje, jest strukturą drzewiastą, która pozwala uzyskiwać dostęp do elementów, wyszukiwać je, wstawiać nowe i usuwać istniejące w krótkim czasie. Z logarytmicznego punktu widzenia złożoność tych operacji wynosi O(logM(n)). B-drzewo to pewien rodzaj spłaszczenia drzewa binarnego. W drzewa binarnym każdy rodzic może mieć maksymalnie dwóch potomków, natomiast w B-drzewie każdy rodzic może mieć tych potomków więcej. B-drzewo zoptymalizowane jest do pracy z systemami, w których operacje wejścia/wyjścia działają znacznie wydajniej operując większymi porcjami danych. Ilość potomków w B-drzewie wynika bezpośrednio ze struktury wewnętrznej systemu operacyjnego. Dla systemu operacyjnego Windows strona pamięci wirtualnej wynosi 4 kB lub wielokrotność tej wartości. Ilość danych odczytywanych w jednym pakiecie z pamięci masowej także może się różnić. Wszystko zależy od konkretnego urządzenia, ale także są to najczęsciej wielokrotności 4 kB (16 kB, 32 kB). Takie minimalne paczki odczytywane są z dysku twardego niezależnie od tego, czy potrzebujemy 2 bajty, czy 3000 bajtów. Zrównoważone drzewo binarne posiada więcej poziomów niż zrównoważone B-drzewo, które może mieć więcej niż dwóch potomków.

W drzewie binarnym każdy kolejny poziom ma dwa razy więcej elementów niż poprzedni. W B-drzewie każdy kolejny poziom n zawiera n'*(M+1) elementów, gdzie n' to ilość elementów poprzedniego poziomu, natomiast M to rząd drzewa, czyli maksymalna ilość potomków, które mogą się zawierać w jednym elemencie rodzica. Pierwszym poziom drzewa binarnego rozumie się jako jeden element, podczas gdy pierwszy poziom B-drzewa to M elementów (kluczy).

Na rysunku 1. pokazano strukturę B-drzewa.

O ile w drzewie binarnym każdy element składa się z klucza (wartości) oraz wskazania na lewego i prawego potomka (weskaźniki mogą być puste, jeżeli nie ma potomka), o tyle w B-drzewie struktura przedstawia się nieco inaczej. Jest to naprzemienna sekwencja wskaźników i kluczy postaci W0-K1-W1-K2-W2-...-KM-WM. Co warte podkreślenia, sekwencja zaczyna się i kończy wskaźnikiem. Drugą ważną rzeczą jest fakt, że K1<K2<K3<...<KM, czyli to, że klucze są posortowane. Wszystkie elementy potomne wskazywane przez W0 mają wartości mniejsze od K1, elementy wskazywane przez W1 mają wartości z przedziału <K1,K2>, W2 zawiera elementy z przedziału <K2,K3> i tak dalej. Taka konstrukcja sprawia, że złożoność algorytmu w zakresie wyszukiwania wynosi O(logM(n)) i jest lepsza niż w drzewie binarnym, bo tam wynosi O(log2(n)). Oczywiście mowa tu o operacjach odczytów z dysku twardego lub innej pamięci masowej. Odczyt jednego elementu zawierającego M kluczy wymaga dodatkowego ich przetworzenia już mniej wydajnym algorytmem z punktu widzenia złożoności obliczeniowej, ale pamiętajmy, że główny nacisk kładziony jest na minimalizację odczytów z pamięci masowych. Operacje wykonywane w pamięci operacyjnej są o kilka rzędów wielkości szybsze i nawet mniej wydajny algorytm (o złożoności liniowej) działa wtedy dość sprawnie.

Załóżmy zatem, że strona odczytywane w jednej paczce z pamięci masowej wynosi 4096 B, a wskaźnik ma 4 bajty (adresuje 4 GB obszar pamięci). Kluczem niech w naszym przypadku będzie wartość całkowita dodatnia, zajmująca 8 bajtów (wartości od 0 do 2^64). W jednym elemencie może się wtedy zmieścić:

W związku z tym, że M musi być liczbą całkowitą, przyjmujemy, że będzie to 511. W jednym odczycie możemy zatem pobrać 511 kluczy. Co to oznacza? A no to, że wykonując drugi odczyt możemy wybrać jeden spośród M*(M+1) kluczy, czyli jeden spośród 261632. Mając dany konkretny klucz potrzebujemy zaledwie dwóch operacji dyskowych do rozróżnienia 261632 wartości. Trzeci poziom to 261632*(M+1)=133955584. Jest to wartość, która zadowoli chyba zdecydowaną większość osób odpowiedzialnych za bazy danych.

W SQL Server stosowany jest mechanizm określany w logarytmice jako B+drzewo. Jest to szczególna odmiana B-drzewa, w którym kopie kluczy przechowywane są we wszystkich wewnętrznych elementach drzewa, natomiast klucze z konkretnymi wartościami przechowywane są tylko w liściach, czyli na najnizszym poziomie.

Kategoria:IndeksySQL Server