Indeks (baza danych)
W informatyce , w bazach danych , Indeks jest struktura danych używana i utrzymuje system zarządzania bazami danych (DBMS), aby umożliwić mu szybko znaleźć dane. Korzystanie z indeksu upraszcza i przyspiesza operacje wyszukiwania, sortowania, łączenia lub agregacji wykonywane przez DBMS.
Wskaźnik umieszczony na stole pozwoli DBMS aby uzyskać dostęp do rejestrów bardzo szybko, w zależności od wartości jednego lub więcej pól .
Zasada
Indeks to automatycznie utrzymywana struktura, która ułatwia lokalizowanie rekordów w pliku. Stosowanie indeksów opiera się na następującej obserwacji: aby znaleźć książkę w bibliotece, zamiast badać każdą książkę po kolei (co odpowiada wyszukiwaniu sekwencyjnemu ), szybciej zajrzeć do katalogu, w którym są one uporządkowane tematycznie, autor i tytuł. Każdy wpis w indeksie ma wartość pobraną z danych i wskaźnik do jego pierwotnej lokalizacji. Nagranie można więc łatwo znaleźć, wyszukując jego lokalizację w indeksie.
Indeks można uporządkować, posiekać, zagęścić lub skąpić:
- Uporządkowany indeks zawiera listę wartości pobranych z tabeli i posortowanych.
- W indeksie mieszanym wartości są przekształcane przez funkcję skrótu .
- W gęstym indeksie istnieją odwołania do wszystkich rekordów w tabeli.
- W indeksie rozproszonym istnieją odniesienia tylko do części rekordów.
Podstawowy indeks z tabeli jest pierwszym, który służy do zlokalizowania rekordów. Tabela może również zawierać indeksy pomocnicze oprócz indeksu podstawowego. Każda tabela może mieć jeden lub więcej indeksów. Indeks może pochodzić z jednego pola lub może łączyć kilka pól.
Techniczny
Indeksy są używane przez DBMS do wielu operacji. Indeksy ułatwiają sortowanie, znajdowanie, grupowanie i dołączanie. Najczęstszym struktura indeksu jest B-drzewo . Istnieją inne struktury, ale są rzadko używane - ISAM , tablice skrótów lub mapy bitowe.
- struktura drzewa: pień, do którego przymocowane są gałęzie z odgałęzieniami i liśćmi na końcu. Wszystkie wyszukiwania są wykonywane począwszy od bagażnika. Przeszukując gałęzie pod kątem tego, który zawiera wartość do znalezienia, aż dotrzesz do liścia.
Aby przyspieszyć operacje, drzewa indeksów są zapisywane w bloku o bardzo dużej liczbie następstw: Dyski twarde, na których zapisywane są indeksy, odczytują dane w blokach po kilka kilobajtów, a czas potrzebny do odczytania bloku jest zwykle znacznie krótszy niż czas potrzebny do zlokalizowania go. Przy takiej konstrukcji wyszukanie rekordu z partii kilku milionów wymaga wtedy tylko 2 lub 3 operacji.
Indeksy można dodawać za pomocą polecenia SQL . Istnienie indeksów ma kluczowe znaczenie dla przyspieszenia operacji manipulacji danymi. Główną przyczyną rozczarowań jest nieodpowiednie wykorzystanie indeksów. System zarządzania bazą danych (w skrócie DBMS) nie znajdzie indeksów, które są niezbędne do efektywnego wykonywania żądanych operacji. Przyczyną niewłaściwego użycia jest to, że dokumentacja DBMS dotycząca użycia indeksów jest często niejasna i zwięzła oraz podkreśla raczej ich wady niż zalety.
Indeksy są wykorzystywane w szczególności przez optymalizator zapytań :
- Optymalizator jest komponentem DBMS, który znajduje najbardziej ekonomiczny sposób wykonania zapytania. Optymalizator analizuje różne możliwe scenariusze i szacuje liczbę operacji wymaganych dla każdego scenariusza, a następnie wybiera scenariusz, który wymaga najmniej. Liczba wymaganych operacji zależy od obecności indeksów, a także liczby wierszy w tabeli i rozkładu wartości.
Typy indeksów
- Najpopularniejszą strukturą indeksu jest drzewo B ( drzewo b ). Przechowując różne wartości pola w zrównoważonym drzewie , DBMS będzie w stanie nadać priorytet rekordom zgodnie z polem, którego zakres wartości jest nieskończony (lub prawie).
- Innym rodzajem indeksu jest indeks mapy bitowej . Składa się z prostej tabeli wskazującej, dla każdej możliwej wartości pola, listę rekordów posiadających tę wartość dla tego pola.
- Istnieją również indeksy według tabeli skrótów . Główną wadą takiego indeksu jest to, że dopuszcza on tylko selekcje według równości, ponieważ nie zachowuje pojęcia porządku. Jeśli n jest liczbą rekordów w tabeli, użycie zrównoważonej tabeli skrótów może zmniejszyć liczbę rekordów do przeglądania , pierwiastek kwadratowy z n (wówczas tabela składa się z wartości skrótu, z którego każdy uzyskuje dostęp do rekordów). Ta sama uwaga dotycząca wydajności istnieje dla indeksu mapy bitowej: DBMS musi mieć możliwość bezpośredniego dostępu do danej wartości skrótu, bez konieczności przeglądania listy możliwych wartości skrótu.
Wpływ na wydajność modyfikacji
Podczas wstawiania lub aktualizowania rekordu bazy danych następuje nieznaczne pogorszenie wydajności: DBMS musi rzeczywiście zaktualizować indeksy, aby nadal odzwierciedlały stan rekordów. Z tego powodu przy projektowaniu bazy danych będziemy starać się zdefiniować tylko te indeksy, które będą używane przez system. Ponadto zostaną one dobrze zidentyfikowane jedynie poprzez analizę systemu (aw szczególności mechanizmów przeszukiwania baz danych) pod kątem jego optymalizacji.
Inne formy indeksacji
Inne typy struktur oferują funkcję indeksowania:
- Tabele grupowane
- Zmaterializowany widok
Uwaga dotycząca indeksów wielokolumnowych
W przypadku indeksu wielokolumnowego DBMS może „zdecydować” o jego częściowym użyciu, w kolejności kolumn indeksu. Innymi słowy, indeks kolumn (c1, c2, c3, c4) może być użyty jako indeks (c1, c2, c3), (c1, c2) lub (c1).
Uwagi i odniesienia
- (en) Carlos Coronel, Steven Morris i Peter Rob Database Systems: Projektowanie, wdrażanie i zarządzanie , Cengage Learning - 2012, ( ISBN 9781111969608 )
- (en) SK Singh, Systemy baz danych: koncepcje, projekty i aplikacje , Pearson Education India - 2009, ( ISBN 9788177585674 )
- (en) Gavin Powell, Beginning Database Design , John Wiley & Sons - 2006, ( ISBN 9780764574900 )
- (en) Tapio Lahdenmaki i Mike Leach, Relational Database Index Design and the Optimizers , John Wiley & Sons - 2005, ( ISBN 9780471721369 )
- (w) Ken England, Gavin JT Powell, Podręcznik optymalizacji i strojenia wydajności Microsoft SQL Server 2005 , Digital Press - 2011 ( ISBN 9780080554082 )