Indeks bazy danych - Database index

Indeks bazy danych jest struktura danych , która zwiększa szybkość operacji pobierania danych w tabeli bazy danych kosztem dodatkowych pisze i przestrzeni dyskowej do utrzymania struktury danych indeksu. Indeksy służą do szybkiego lokalizowania danych bez konieczności przeszukiwania każdego wiersza w tabeli bazy danych przy każdym dostępie do tabeli bazy danych. Indeksy można tworzyć przy użyciu jednej lub kilku kolumn tabeli bazy danych , co zapewnia podstawę zarówno do szybkiego wyszukiwania losowego, jak i wydajnego dostępu do uporządkowanych rekordów.

Indeks to kopia wybranych kolumn danych z tabeli, która ma na celu umożliwienie bardzo wydajnego wyszukiwania. Indeks zwykle zawiera „klucz” lub bezpośrednie łącze do oryginalnego wiersza danych, z którego został skopiowany, aby umożliwić wydajne pobranie całego wiersza. Niektóre bazy danych rozszerzają możliwości indeksowania, umożliwiając programistom tworzenie indeksów na wartościach kolumn, które zostały przekształcone przez funkcje lub wyrażenia . Na przykład można utworzyć indeks na upper(last_name), który przechowuje tylko wersje last_namepola pisane wielkimi literami w indeksie. Inną obsługiwaną czasami opcją jest użycie indeksów częściowych , gdzie pozycje indeksu są tworzone tylko dla tych rekordów, które spełniają pewne wyrażenie warunkowe. Kolejnym aspektem elastyczności jest umożliwienie indeksowania funkcji zdefiniowanych przez użytkownika , a także wyrażeń utworzonych z zestawu funkcji wbudowanych.

Stosowanie

Wsparcie dla szybkiego wyszukiwania

Większość oprogramowania bazodanowego zawiera technologię indeksowania, która umożliwia podliniowe wyszukiwanie czasu w celu poprawy wydajności, ponieważ wyszukiwanie liniowe jest nieefektywne w przypadku dużych baz danych.

Załóżmy, że baza danych zawiera N elementów danych i jeden musi zostać pobrany na podstawie wartości jednego z pól. Prosta implementacja pobiera i sprawdza każdy element zgodnie z testem. Jeśli jest tylko jeden pasujący element, może się to zatrzymać, gdy znajdzie ten pojedynczy element, ale jeśli jest wiele dopasowań, musi wszystko przetestować. Oznacza to, że liczba operacji w średnim przypadku wynosi O (N) lub czas liniowy . Ponieważ bazy danych mogą zawierać wiele obiektów, a wyszukiwanie jest powszechną operacją, często pożądane jest zwiększenie wydajności.

Indeks to dowolna struktura danych, która poprawia wydajność wyszukiwania. W tym celu stosuje się wiele różnych struktur danych . Istnieją złożone kompromisy projektowe dotyczące wydajności wyszukiwania, rozmiaru indeksu i wydajności aktualizacji indeksu. Wiele projektów indeksów wykazuje wydajność wyszukiwania logarytmicznego ( O (log(N))), aw niektórych aplikacjach można uzyskać wydajność płaską ( O (1)).

Kontrolowanie ograniczeń bazy danych

Indeksy są używane do kontrolowania ograniczeń bazy danych , takich jak UNIQUE, EXCLUSION, PRIMARY KEY i FOREIGN KEY . Indeks może być zadeklarowany jako UNIQUE, co tworzy niejawne ograniczenie w tabeli bazowej. Systemy baz danych zwykle niejawnie tworzą indeks na zbiorze kolumn zadeklarowanych PRIMARY KEY, a niektóre mogą używać już istniejącego indeksu do kontrolowania tego ograniczenia. Wiele systemów baz danych wymaga indeksowania zarówno zestawów kolumn, do których istnieją odwołania, jak i zestawów kolumn w ograniczeniu FOREIGN KEY, co poprawia wydajność wstawiania, aktualizowania i usuwania tabel uczestniczących w ograniczeniu.

Niektóre systemy baz danych obsługują ograniczenie WYKLUCZENIA, które zapewnia, że ​​dla nowo wstawionego lub zaktualizowanego rekordu określony predykat nie będzie obowiązywał dla żadnego innego rekordu. Można to wykorzystać do zaimplementowania ograniczenia UNIQUE (z predykatem równości) lub bardziej złożonych ograniczeń, takich jak zapewnienie, że w tabeli nie będą przechowywane żadne nakładające się zakresy czasu lub żadne przecinające się obiekty geometryczne. Indeks obsługujący szybkie wyszukiwanie rekordów spełniających predykat jest wymagany do nadzorowania takiego ograniczenia.

Architektura indeksu i metody indeksowania

Nieklastrowane

Dane występują w dowolnej kolejności, ale kolejność logiczna jest określona przez indeks. Wiersze danych mogą być rozmieszczone w całej tabeli niezależnie od wartości indeksowanej kolumny lub wyrażenia. Drzewo indeksu nieklastrowego zawiera klucze indeksu w kolejności posortowanej, przy czym poziom liścia indeksu zawiera wskaźnik do rekordu (strona i numer wiersza na stronie danych w aparatach zorganizowanych według stron; przesunięcie wiersza w aparatach zorganizowanych według plików ).

W indeksie nieklastrowym,

  • Fizyczna kolejność wierszy nie jest taka sama jak kolejność indeksu.
  • Kolumny indeksowane są zazwyczaj kolumnami kluczy innych niż podstawowe używane w klauzulach JOIN, WHERE i ORDER BY.

W tabeli bazy danych może znajdować się więcej niż jeden indeks nieklastrowany.

Klastrowy

Grupowanie zmienia blok danych w określonej kolejności, aby dopasować indeks, w wyniku czego dane wiersza są przechowywane w kolejności. Dlatego w danej tabeli bazy danych można utworzyć tylko jeden indeks klastrowy. Indeksy klastrowe mogą znacznie zwiększyć ogólną szybkość wyszukiwania, ale zwykle tylko wtedy, gdy dostęp do danych uzyskuje się sekwencyjnie w tej samej lub odwrotnej kolejności indeksu klastrowego, lub gdy wybrany jest zakres pozycji.

Ponieważ fizyczne rekordy znajdują się na dysku w takiej kolejności sortowania, następny wiersz w sekwencji znajduje się bezpośrednio przed lub za ostatnim, a zatem wymagana jest mniejsza liczba odczytów bloków danych. Podstawową cechą indeksu klastrowego jest zatem uporządkowanie fizycznych wierszy danych zgodnie z blokami indeksu, które na nie wskazują. Niektóre bazy danych rozdzielają bloki danych i indeksu na oddzielne pliki, inne umieszczają dwa zupełnie różne bloki danych w tym samym pliku fizycznym.

Grupa

Gdy łączy się wiele baz danych i wiele tabel, nazywa się to klastrem (nie mylić z opisanym wcześniej indeksem klastrowym). Rekordy dla tabel dzielących wartość klucza klastra powinny być przechowywane razem w tych samych lub pobliskich blokach danych. Może to poprawić łączenie tych tabel w kluczu klastra, ponieważ pasujące rekordy są przechowywane razem i do ich zlokalizowania potrzeba mniej operacji we/wy. Konfiguracja klastra definiuje układ danych w tabelach będących częścią klastra. Klaster może być kluczowany indeksem B-Tree lub tablicą mieszającą . Blok danych, w którym przechowywany jest rekord tabeli, jest zdefiniowany przez wartość klucza klastra.

Kolejność kolumn

Ważna jest kolejność, w jakiej definicja indeksu definiuje kolumny. Możliwe jest pobranie zestawu identyfikatorów wierszy przy użyciu tylko pierwszej indeksowanej kolumny. Jednak nie jest możliwe ani wydajne (w większości baz danych) pobieranie zestawu identyfikatorów wierszy przy użyciu tylko drugiej lub większej indeksowanej kolumny.

Na przykład w książce telefonicznej uporządkowanej najpierw według miasta, potem nazwiska, a następnie imienia, w danym mieście można łatwo wyodrębnić listę wszystkich numerów telefonów. Jednak znalezienie wszystkich numerów telefonów dla konkretnego nazwiska byłoby bardzo żmudne. Należałoby zajrzeć do sekcji każdego miasta, aby znaleźć wpisy z tym nazwiskiem. Niektóre bazy danych mogą to zrobić, inne po prostu nie będą używać indeksu.

W przykładzie książki telefonicznej ze złożonym indeksem utworzonym na kolumnach ( city, last_name, first_name), jeśli szukamy, podając dokładne wartości dla wszystkich trzech pól, czas wyszukiwania jest minimalny — ale jeśli podajemy wartości dla cityi first_nametylko, wyszukiwanie wykorzystuje tylko citypole aby pobrać wszystkie dopasowane rekordy. Następnie wyszukiwanie sekwencyjne sprawdza dopasowanie za pomocą first_name. Tak więc, aby poprawić wydajność, należy upewnić się, że indeks jest tworzony w kolejności kolumn wyszukiwania.

Zastosowania i ograniczenia

Indeksy są przydatne w wielu aplikacjach, ale mają pewne ograniczenia. Rozważmy następującą instrukcję SQL : SELECT first_name FROM people WHERE last_name = 'Smith';. Aby przetworzyć tę instrukcję bez indeksu, oprogramowanie bazy danych musi sprawdzić kolumnę last_name w każdym wierszu tabeli (jest to znane jako pełne skanowanie tabeli ). W przypadku indeksu baza danych po prostu podąża za strukturą danych indeksu (zazwyczaj B-drzewo ), dopóki nie zostanie znaleziony wpis Smith; jest to znacznie mniej kosztowne obliczeniowo niż pełne skanowanie tabeli.

Rozważmy następującą instrukcję SQL: SELECT email_address FROM customers WHERE email_address LIKE '%@wikipedia.org';. To zapytanie dałoby adres e-mail dla każdego klienta, którego adres e-mail kończy się na „@wikipedia.org”, ale nawet jeśli kolumna email_address została zindeksowana, baza danych musi wykonać pełne skanowanie indeksu. Dzieje się tak, ponieważ indeks budowany jest przy założeniu, że słowa biegną od lewej do prawej. Dzięki symbolowi wieloznacznemu na początku wyszukiwanego terminu oprogramowanie bazy danych nie może użyć podstawowej struktury danych indeksu (innymi słowy, klauzula WHERE nie jest sargable ). Ten problem można rozwiązać poprzez dodanie innego indeksu utworzonego na reverse(email_address)i zapytania SQL takiego: SELECT email_address FROM customers WHERE reverse(email_address) LIKE reverse('%@wikipedia.org');. Spowoduje to umieszczenie symbolu wieloznacznego w prawej części zapytania (teraz gro.aidepikiw@%), którą może spełnić indeks na reverse(email_address).

Gdy symbole wieloznaczne są używane po obu stronach wyszukiwanego słowa jako %wikipedia.org% , indeks dostępny w tym polu nie jest używany. Przeprowadzane jest raczej tylko wyszukiwanie sekwencyjne, które zajmuje czas O(N).

Rodzaje indeksów

Indeks bitmapowy

Indeks bitmapy to specjalny rodzaj indeksowania, który przechowuje większość swoich danych w postaci tablic bitowych (map bitowych) i odpowiada na większość zapytań, wykonując bitowe operacje logiczne na tych mapach bitowych. Najczęściej używane indeksy, takie jak drzewa B+ , są najbardziej wydajne, jeśli wartości, które indeksują, nie powtarzają się lub powtarzają się niewielką liczbę razy. Natomiast indeks bitmapowy jest przeznaczony do przypadków, w których wartości zmiennej bardzo często się powtarzają. Na przykład pole płeć w bazie danych klientów zwykle zawiera co najwyżej trzy różne wartości: mężczyzna, kobieta lub nieznana (niezarejestrowana). W przypadku takich zmiennych indeks bitmapowy może mieć znaczną przewagę wydajności nad powszechnie używanymi drzewami.

Gęsty indeks

Gęsty indeks w bazach danych to plik z parami kluczy i wskaźników dla każdego rekordu w pliku danych. Każdy klucz w tym pliku jest powiązany z określonym wskaźnikiem do rekordu w posortowanym pliku danych. W indeksach klastrowych ze zduplikowanymi kluczami gęsty indeks wskazuje na pierwszy rekord z tym kluczem.

Rzadki indeks

Rzadki indeks w bazach danych to plik z parami kluczy i wskaźników dla każdego bloku w pliku danych. Każdy klucz w tym pliku jest powiązany z określonym wskaźnikiem do bloku w posortowanym pliku danych. W indeksach klastrowych ze zduplikowanymi kluczami indeks rzadki wskazuje najniższy klucz wyszukiwania w każdym bloku.

Odwrotny indeks

Indeks klucza odwrotnego odwraca wartość klucza przed wprowadzeniem go do indeksu. Np. wartość 24538 staje się w indeksie 83542. Odwracanie wartości klucza jest szczególnie przydatne w przypadku indeksowania danych, takich jak numery sekwencyjne, w przypadku których nowe wartości klucza są monotonicznie zwiększane.

Indeks podstawowy

Indeks podstawowy zawiera pola kluczowe tabeli i wskaźnik do pól niekluczowych tabeli. Indeks podstawowy jest tworzony automatycznie podczas tworzenia tabeli w bazie danych.

Indeks wtórny

Służy do indeksowania pól, które nie są ani polami porządkowymi, ani polami kluczowymi (nie ma pewności, że plik jest zorganizowany według pola kluczowego lub pola klucza podstawowego). Jeden wpis indeksu dla każdej krotki w pliku danych (indeks gęsty) zawiera wartość indeksowanego atrybutu i wskaźnik do bloku lub rekordu.

Indeks skrótu

Implementacje indeksowe

Indeksy mogą być implementowane przy użyciu różnych struktur danych. Popularne indeksy obejmują wyważonych drzew , b + drzew i skrótów .

W programie Microsoft SQL Server , do węzła liści z klastrowych odpowiada indeksu do rzeczywistych danych, a nie tylko wskaźnik do danych, który znajduje się w innym miejscu, jak to jest w przypadku indeksu nieklastrowanym. Każda relacja może mieć jeden indeks klastrowany i wiele indeksów nieklastrowanych.

Kontrola współbieżności indeksu

Dostęp do indeksu jest zwykle uzyskiwany jednocześnie przez kilka transakcji i procesów, dlatego wymaga kontroli współbieżności . Chociaż w zasadzie indeksy mogą korzystać ze wspólnych metod kontroli współbieżności baz danych, istnieją wyspecjalizowane metody kontroli współbieżności dla indeksów, które są stosowane w połączeniu z typowymi metodami w celu znacznego zwiększenia wydajności.

Indeks pokrycia

W większości przypadków indeks służy do szybkiego lokalizowania rekordów danych, z których odczytywane są wymagane dane. Innymi słowy, indeks służy tylko do lokalizowania rekordów danych w tabeli, a nie do zwracania danych.

Indeks pokrywający to szczególny przypadek, w którym sam indeks zawiera wymagane pola danych i może odpowiadać na wymagane dane.

Rozważ poniższą tabelę (pominięto inne pola):

NS Nazwa Inne pola
12 Wtyczka ...
13 Lampa ...
14 Bezpiecznik ...

Aby znaleźć Nazwę dla ID 13, indeks na (ID) jest przydatny, ale rekord musi być jeszcze odczytany, aby uzyskać Nazwę. Jednak indeks (ID, Nazwa) zawiera wymagane pole danych i eliminuje potrzebę wyszukiwania rekordu.

Indeksy pokrywające są każdy dla określonej tabeli. Zapytania, które łączą się / uzyskują dostęp do wielu tabel, mogą potencjalnie rozważyć objęcie indeksów w więcej niż jednej z tych tabel.

Indeks pokrywający może znacznie przyspieszyć pobieranie danych, ale sam może być duży ze względu na dodatkowe klucze, które spowalniają wstawianie i aktualizowanie danych. Aby zmniejszyć taki rozmiar indeksu, niektóre systemy umożliwiają uwzględnienie w indeksie pól niekluczowych. Pola niekluczowe same w sobie nie są częścią porządkowania indeksów, ale są zawarte tylko na poziomie liścia, co pozwala na indeks pokrywający o mniejszym ogólnym rozmiarze indeksu.

Normalizacja

Żaden standard nie definiuje sposobu tworzenia indeksów, ponieważ standard ISO SQL nie obejmuje aspektów fizycznych. Indeksy są jedną z fizycznych części koncepcji baz danych, między innymi takich jak przechowywanie (obszar tabel lub grupy plików). Wszyscy dostawcy RDBMS udostępniają składnię CREATE INDEX z pewnymi określonymi opcjami, które zależą od możliwości ich oprogramowania.

Zobacz też

Bibliografia