Jak działają indeksy MySQL?

Naprawdę interesuje mnie, jak działają indeksy MySQL, a dokładniej, w jaki sposób mogą zwrócić żądane dane bez skanowania całej tabeli?

Wiem, że to nie na temat, ale jeśli jest ktoś, kto mógłby mi to szczegółowo wyjaśnić, byłbym bardzo, bardzo wdzięczny.

Zasadniczo indeks w tabeli działa jak indeks w książce (stąd pochodzi nazwa):

Załóżmy, że masz książkę o bazach danych i chcesz znaleźć informacje o, powiedzmy, pamięci. Bez indeksu (zakładając, że nie ma innej pomocy, takiej jak spis treści), będziesz musiał przeglądać strony jeden po drugim, aż znajdziesz temat (to jest a full table scan). Z drugiej strony indeks ma listę słów kluczowych, więc zapoznaj się z indeksem i zobacz, że storagejest on wymieniony na stronach 113-120,231 i 354. Następnie możesz przejść do tych stron bezpośrednio, bez wyszukiwania (jest to wyszukiwanie z indeks, nieco szybciej).

Oczywiście, jak przydatny będzie indeks, zależy od wielu rzeczy - kilku przykładów, wykorzystujących powyższe porównanie:

• jeśli miałeś książkę o bazach danych i zaindeksowałeś słowo „baza danych”, zobaczysz, że jest ono wymienione na stronach 1-59,61-290 i od 292 do 400. W takim przypadku indeks nie jest zbyt pomocny i może szybciej przeglądaj strony jeden po drugim (w bazie danych jest to „słaba selektywność”).
• W przypadku 10-stronicowej książki nie ma sensu tworzyć indeksu, ponieważ może to oznaczać, że 10-stronicowa książka poprzedzona jest 5-stronicowym indeksem, co jest po prostu głupie - wystarczy zeskanować 10 stron i gotowe .
• Indeks także musi być przydatny - na ogół nie ma sensu indeksować, np. Częstotliwość litery „L” na stronie.

Pierwszą rzeczą, którą musisz wiedzieć, jest to, że indeksy są sposobem na uniknięcie skanowania pełnej tabeli w celu uzyskania oczekiwanego wyniku.

Istnieją różne rodzaje indeksów i są one zaimplementowane w warstwie pamięci, więc nie ma między nimi żadnego standardu, a także zależą od używanego silnika pamięci.

InnoDB i indeks drzewa B +

W przypadku InnoDB najczęstszym typem indeksu jest indeks oparty na drzewie B +, który przechowuje elementy w posortowanej kolejności. Ponadto nie musisz uzyskiwać dostępu do prawdziwej tabeli, aby uzyskać zindeksowane wartości, co znacznie przyspiesza zapytanie.

„Problem” związany z tym typem indeksu polega na tym, że musisz użyć wartości skrajnie lewej, aby użyć indeksu. Jeśli więc indeks ma dwie kolumny, np. Nazwisko i imię, kolejność zapytań w tych polach ma duże znaczenie .

Biorąc pod uwagę następującą tabelę:

CREATE TABLE person (
    last_name VARCHAR(50) NOT NULL,
    first_name VARCHAR(50) NOT NULL,
    INDEX (last_name, first_name)
);

To zapytanie wykorzysta indeks:

SELECT last_name, first_name FROM person
WHERE last_name = "John" AND first_name LIKE "J%"

Ale następny nie

SELECT last_name, first_name FROM person WHERE first_name = "Constantine"

Ponieważ najpierw przeszukujesz first_namekolumnę i nie jest to kolumna skrajnie lewa w indeksie.

Ten ostatni przykład jest jeszcze gorszy:

SELECT last_name, first_name FROM person WHERE first_name LIKE "%Constantine"

Ponieważ teraz porównujesz prawą część pola znajdującego się po prawej stronie w indeksie.

Indeks mieszania

Jest to inny typ indeksu, który niestety obsługuje tylko backend pamięci. Jest to szybki jak błyskawica, ale przydatne tylko dla pełnych wyszukiwań, co oznacza, że nie można go używać na podobne operacje >, <albo LIKE.

Ponieważ działa tylko w przypadku backendu pamięci, prawdopodobnie nie będziesz go używać zbyt często. Główną sprawą, o której mogę teraz pomyśleć, jest ta, w której utworzysz tymczasową tabelę w pamięci z zestawem wyników z innego wyboru i wykonasz wiele innych wyborów w tej tabeli tymczasowej za pomocą indeksów skrótów.

Jeśli masz duże VARCHARpole, możesz „naśladować” użycie indeksu skrótu podczas korzystania z B-drzewa, tworząc kolejną kolumnę i zapisując na niej skrót o dużej wartości. Załóżmy, że przechowujesz adres URL w polu, a wartości są dość duże. Możesz także utworzyć pole o nazwie integer url_hashi użyć funkcji skrótu, takiej jak CRC32lub dowolnej innej funkcji skrótu, aby mieszać adres URL podczas wstawiania. A potem, gdy musisz zapytać o tę wartość, możesz zrobić coś takiego:

SELECT url FROM url_table WHERE url_hash=CRC32("http://gnu.org");

Problem z powyższym przykładem polega na tym, że ponieważ CRC32funkcja generuje dość niewielką wartość skrótu, powstanie wiele kolizji w wartościach mieszanych. Jeśli potrzebujesz dokładnych wartości, możesz rozwiązać ten problem, wykonując następujące czynności:

SELECT url FROM url_table 
WHERE url_hash=CRC32("http://gnu.org") AND url="http://gnu.org";

Nadal warto mieszać rzeczy, nawet jeśli liczba kolizji jest wysoka, ponieważ wykonasz tylko drugie porównanie (łańcuchowe) z powtarzającymi się skrótami.

Niestety, używając tej techniki, wciąż musisz trafić w stół, aby porównać urlpole.

Zakończyć

Kilka faktów, które możesz wziąć pod uwagę za każdym razem, gdy chcesz porozmawiać o optymalizacji:

1. Porównanie liczb całkowitych jest znacznie szybsze niż porównywanie ciągów. Można to zilustrować przykładem emulacji indeksu skrótu w InnoDB.

2. Być może dodanie dodatkowych kroków w procesie sprawia, że ​​jest to szybsze, a nie wolniejsze. Można to zilustrować faktem, że można zoptymalizować a SELECT, dzieląc go na dwa etapy, dzięki czemu pierwszy z nich przechowuje wartości w nowo utworzonej tabeli w pamięci, a następnie wykonuje trudniejsze zapytania na drugiej tabeli.

MySQL ma również inne indeksy, ale myślę, że drzewko B + jest najczęściej używane w historii, a hash warto wiedzieć, ale inne można znaleźć w dokumentacji MySQL .

Gorąco polecam przeczytanie książki „High Performance MySQL”, powyższa odpowiedź była zdecydowanie oparta na jej rozdziale o indeksach.

Zasadniczo indeks to mapa wszystkich kluczy posortowana w kolejności. Z listą w kolejności, zamiast sprawdzać każdy klucz, może zrobić coś takiego:

1: Przejdź na środek listy - jest wyższy lub niższy niż to, czego szukam?

2: Jeśli jest wyższy, przejdź do połowy drogi między środkiem a dołem, jeśli jest niższy, środkowy i górny

3: Czy jest wyższy czy niższy? Przejdź ponownie do punktu środkowego itp.

Korzystając z tej logiki, możesz znaleźć element na posortowanej liście w około 7 krokach, zamiast sprawdzania każdego elementu.

Oczywiście są złożone, ale to daje podstawową ideę.

Spójrz na ten link: http://dev.mysql.com/doc/refman/5.0/en/mysql-indexes.html

Sposób ich działania jest zbyt obszerny, aby można go było opisać w jednym poście SO.

Oto jedno z najlepszych wyjaśnień indeksów, jakie widziałem. Niestety dotyczy to SQL Server, a nie MySQL. Nie jestem pewien, jak podobne są te dwa ...

Take w tym filmy o więcej szczegółów na temat indeksowania

Proste indeksowanie Możesz stworzyć unikalny indeks na stole. Unikalny indeks oznacza, że ​​dwa wiersze nie mogą mieć tej samej wartości indeksu. Oto składnia umożliwiająca utworzenie indeksu w tabeli

CREATE UNIQUE INDEX index_name
ON table_name ( column1, column2,...);

Możesz użyć jednej lub więcej kolumn, aby utworzyć indeks. Na przykład możemy utworzyć indeks przy tutorials_tblużyciu tutorial_author.

CREATE UNIQUE INDEX AUTHOR_INDEX
ON tutorials_tbl (tutorial_author)

Możesz utworzyć prosty indeks na stole. Wystarczy pominąć zapytanie UNIQUE w zapytaniu, aby utworzyć prosty indeks. Prosty indeks pozwala na duplikowanie wartości w tabeli.

Jeśli chcesz indeksować wartości w kolumnie w porządku malejącym, możesz dodać słowo DESC po nazwie kolumny.

mysql> CREATE UNIQUE INDEX AUTHOR_INDEX
ON tutorials_tbl (tutorial_author DESC)

Chcę dodać moje 2 centy. Nie jestem ekspertem od baz danych, ale ostatnio przeczytałem trochę na ten temat; wystarczy, żebym spróbował dać ELI5. Oto wyjaśnienie laika.

Rozumiem to jako takie, że indeks jest jak mini-lustro twojego stołu, prawie jak tablica asocjacyjna. Jeśli podasz odpowiedni klucz, możesz po prostu przeskoczyć do tego wiersza jednym „poleceniem”.

Ale jeśli nie masz tego indeksu / tablicy, interpreter zapytań musi użyć pętli for, aby przejść przez wszystkie wiersze i sprawdzić zgodność (skanowanie całej tabeli).

Posiadanie indeksu ma „wadę” dodatkowej pamięci (dla tego mini-lustra) w zamian za „plus” szybszego wyszukiwania treści.

Zauważ, że (w zależności od silnika db) tworzenie kluczy podstawowych, obcych lub unikalnych automatycznie ustawia również odpowiedni indeks. Ta sama zasada jest w zasadzie dlaczego i jak działają te klucze.

Dodanie wizualnej reprezentacji do listy odpowiedzi.

MySQL korzysta z dodatkowej warstwy pośredniej: rekordy indeksu wtórnego wskazują rekordy indeksu podstawowego, a sam indeks główny przechowuje położenia wierszy na dysku. Jeśli zmienia się przesunięcie wiersza, należy zaktualizować tylko indeks główny.

Uwaga: struktura danych dysku wygląda płasko na schemacie, ale tak naprawdę jest drzewem B +.

Źródło: link

W MySQL InnoDB istnieją dwa typy indeksów.

1. Klucz podstawowy zwany indeksem klastrowym. Słowa kluczowe indeksu są przechowywane z rzeczywistymi danymi rekordu w węźle liści drzewa B +.

2. Drugi klucz, który jest indeksem nieklastrowanym. Indeksy te przechowują tylko słowa kluczowe klucza podstawowego wraz z własnymi słowami kluczowymi indeksu w węźle liścia drzewa B +. Podczas wyszukiwania z indeksu wtórnego najpierw znajdzie słowa kluczowe indeksu klucza podstawowego i zeskanuje drzewo B + klucza podstawowego, aby znaleźć rzeczywiste rekordy danych. Spowoduje to spowolnienie indeksu wtórnego w porównaniu z wyszukiwaniem indeksu podstawowego. Jeśli jednak wszystkie selectkolumny znajdują się w indeksie wtórnym, nie trzeba ponownie szukać indeksu podstawowego B + Drzewo. Nazywa się to indeksem kryjącym.