Spis treści:

Kategoria:IndeksySQL Server


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.

[Struktura B-drzewa.png],

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ć:

M*8+(M+1)*4<4096
M*8+M*4+4<4096
M*12<4092
M<511,5

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

, 2013-12-20

Komentarze:

czywszystkogra (2015-01-30 14:52:57)
Jesli mamy M+1 wskaźników w kazdym poziomie i M kluczy, to oznacza, ze w nastepnym poziomie przeglądamy M kluczy z kazdego z M+1 wkaźników poprzedniego poziomu. Oznacza to, ze trzeci poziom może przejrzeć nie M(M+1)(M+1) kluczy tylko (M+1)(M+1)M kluczy. Czyli nie 261632*(M+1) tylko (511+1)(511+1)*M=262144*M, co w sumie daje ten sam efekt.
Dodaj komentarz
Wyślij
Ostatnie komentarze
To samo pytanie co wyżej. Mam za zadanie dodać kolumnę do istniejącej tabeli łącząc obie inne kolumny ze sobą, ale nie mam pojęcia jak za to się zabrać
działa :) tylko była literówka :)
Podziękował. Trochę późno, po 8 latach, ale dzięki za testy (rozumiem że dla SQL2012 robione). Tak się właśnie zastanawiałem ile złego czynię stosując czasem __(max).
Super robota, korzystając z innych internetowych kalkulatorow po prostu wątpiłem w ich prawdomówność, w końcu trafiłem tutaj i wynik w końcu jest wiarygodny. 40 km w 2 h 810 kcal, ciekawostka: na fitatu wyliczyło mi 5700 kcal 😊 najlepiej będzie chyba jak kupię zegarek sportowy.
Wielkie dzieki za solidne wyjasnienia tematu.