Jak działa indeksowanie bazy danych? [Zamknięte]

Biorąc pod uwagę, że indeksowanie jest tak ważne, jak rozmiar zbioru danych rośnie, czy ktoś może wyjaśnić, jak indeksowanie działa na poziomie niezależnym od bazy danych?

Aby uzyskać informacje na temat zapytań dotyczących indeksowania pola, zobacz Jak zaindeksować kolumnę bazy danych .

Dlaczego jest to potrzebne?

Gdy dane są przechowywane na dyskowych urządzeniach magazynujących, są przechowywane jako bloki danych. Te bloki są dostępne w całości, co czyni je operacją dostępu do dysku atomowego. Bloki dyskowe mają strukturę podobną do list połączonych; oba zawierają sekcję danych, wskaźnik do lokalizacji następnego węzła (lub bloku) i oba nie muszą być przechowywane w sposób ciągły.

Z uwagi na fakt, że wiele rekordów można posortować tylko na jednym polu, możemy stwierdzić, że wyszukiwanie w polu, które nie jest posortowane, wymaga wyszukiwania liniowego, które wymaga N/2dostępu do bloków (średnio), gdzie Njest liczba bloków, które stół się rozciąga. Jeśli to pole jest polem niekluczowym (tzn. Nie zawiera unikatowych wpisów), należy przeszukać cały obszar tabel przy dostępie do Nbloku.

Natomiast z posortowanym polem można zastosować wyszukiwanie binarne, które ma log2 Ndostęp do bloków. Ponieważ dane są sortowane według pola niekluczowego, reszta tabeli nie musi być przeszukiwana pod kątem duplikatów, gdy tylko zostanie znaleziona wyższa wartość. Zatem wzrost wydajności jest znaczny.

Co to jest indeksowanie?

Indeksowanie to sposób sortowania wielu rekordów w wielu polach. Utworzenie indeksu dla pola w tabeli tworzy kolejną strukturę danych, która przechowuje wartość pola i wskaźnik do rekordu, którego dotyczy. Ta struktura indeksu jest następnie sortowana, umożliwiając na nim wyszukiwanie binarne.

Minusem indeksowania jest to, że indeksy te wymagają dodatkowego miejsca na dysku, ponieważ indeksy są przechowywane razem w tabeli za pomocą silnika MyISAM, plik ten może szybko osiągnąć limity rozmiaru bazowego systemu plików, jeśli wiele pól w tej samej tabeli jest indeksowanych .

Jak to działa?

Po pierwsze, nakreślmy przykładowy schemat tabeli bazy danych;

Nazwa pola Typ danych Rozmiar na dysku
id (klucz podstawowy) Unsigned INT 4 bajty
firstName Char (50) 50 bajtów
lastName Char (50) 50 bajtów
emailAddress Char (100) 100 bajtów

Uwaga : zamiast varchar zastosowano char, aby umożliwić dokładny rozmiar wartości dysku. Ta przykładowa baza danych zawiera pięć milionów wierszy i jest nieindeksowana. Wydajność kilku zapytań zostanie teraz przeanalizowana. Są to zapytania przy użyciu identyfikatora (posortowane pole klucza) i zapytania przy użyciu firstName (nieposortowane pole nieposortowane).

Przykład 1 - pola posortowane a nieposortowane

Biorąc pod uwagę naszą przykładową bazę danych r = 5,000,000rekordów o ustalonym rozmiarze, dających rekordową długość R = 204bajtów, i są one przechowywane w tabeli za pomocą silnika MyISAM, który używa domyślnej wielkości B = 1,024bajtów bloku . Czynnikiem blokującym tabelę byłyby bfr = (B/R) = 1024/204 = 5rekordy na blok dysku. Całkowita liczba bloków potrzebnych do utrzymania tabeli to N = (r/bfr) = 5000000/5 = 1,000,000bloki.

Liniowe wyszukiwanie w polu id wymagałoby średniego N/2 = 500,000dostępu do bloku, aby znaleźć wartość, biorąc pod uwagę, że pole id jest polem kluczowym. Ponieważ jednak pole id jest również posortowane, można przeprowadzić wyszukiwanie binarne wymagające średniego log2 1000000 = 19.93 = 20dostępu do bloku. Natychmiast widzimy, że jest to drastyczna poprawa.

Teraz pole firstName nie jest sortowane ani kluczowe, więc wyszukiwanie binarne jest niemożliwe, a wartości nie są unikalne, dlatego tabela będzie wymagała wyszukiwania do końca dokładnego N = 1,000,000dostępu do bloku. Jest to sytuacja, którą indeksowanie ma poprawić.

Biorąc pod uwagę, że rekord indeksu zawiera tylko indeksowane pole i wskaźnik do rekordu oryginalnego, jest oczywiste, że będzie mniejszy niż rekord wielu pól, na który wskazuje. Zatem sam indeks wymaga mniejszej liczby bloków dysku niż oryginalna tabela, co wymaga mniejszego dostępu do bloków w celu iteracji. Schemat indeksu w polu firstName przedstawiono poniżej;

Nazwa pola Typ danych Rozmiar na dysku
firstName Char (50) 50 bajtów
(wskaźnik zapisu) Specjalne 4 bajty

Uwaga : Wskaźniki w MySQL mają długość 2, 3, 4 lub 5 bajtów w zależności od wielkości tabeli.

Przykład 2 - indeksowanie

Biorąc pod uwagę naszą przykładową bazę danych r = 5,000,000rekordów z indeksem długości rekordu R = 54bajtów i przy użyciu domyślnego rozmiaru B = 1,024bajtów bloku . Czynnikiem blokującym indeks byłyby bfr = (B/R) = 1024/54 = 18rekordy na blok dysku. Całkowita liczba bloków wymaganych do przechowywania indeksu to N = (r/bfr) = 5000000/18 = 277,778bloki.

Teraz wyszukiwanie przy użyciu pola firstName może wykorzystać indeks do zwiększenia wydajności. Pozwala to na binarne wyszukiwanie indeksu ze średnią log2 277778 = 18.08 = 19dostępów blokowych. Aby znaleźć adres rzeczywistego rekordu, który wymaga dalszego dostępu do bloku w celu odczytu, przynosząc całkowitą liczbę 19 + 1 = 20dostępów do bloku, daleko od 1.000.000 dostępów do bloku wymaganych do znalezienia dopasowania FirstName w tabeli nieindeksowanej.

Kiedy należy go używać?

Biorąc pod uwagę, że utworzenie indeksu wymaga dodatkowego miejsca na dysku (277,778 dodatkowych bloków w stosunku do powyższego przykładu, wzrost o ~ 28%) oraz że zbyt wiele indeksów może powodować problemy wynikające z ograniczeń wielkości systemów plików, należy starannie rozważyć wybór właściwego pola do indeksowania.

Ponieważ indeksy są używane tylko do przyspieszenia wyszukiwania pasującego pola w rekordach, oczywiste jest, że pola indeksujące używane tylko do danych wyjściowych byłyby po prostu stratą miejsca na dysku i czasu przetwarzania podczas wykonywania operacji wstawiania lub usuwania, a zatem należy unikać. Biorąc pod uwagę charakter wyszukiwania binarnego, ważna jest liczność lub niepowtarzalność danych. Indeksowanie na polu o liczności 2 spowoduje podzielenie danych na pół, podczas gdy liczność na 1000 zwróci około 1000 rekordów. Przy tak niskiej liczności skuteczność zmniejsza się do sortowania liniowego, a optymalizator kwerendy uniknie użycia indeksu, jeśli liczność jest mniejsza niż 30% liczby rekordów, skutecznie czyniąc indeks stratą miejsca.

Klasyczny przykład „Indeks w książkach”

Rozważ „Książkę” złożoną z 1000 stron, podzieloną przez 10 rozdziałów, z których każda zawiera 100 stron.

Proste, co?

Teraz wyobraź sobie, że chcesz znaleźć konkretny rozdział, który zawiera słowo „ Alchemik ”. Bez strony indeksu nie ma innej opcji niż skanowanie całej książki / rozdziałów. tj. 1000 stron.

Ta analogia znana jest jako „Pełny skan tabeli” w świecie baz danych.

Ale dzięki stronie indeksu wiesz, gdzie iść! Co więcej, aby wyszukać konkretny rozdział, który ma znaczenie, wystarczy raz za razem przeglądać stronę indeksu. Po znalezieniu pasującego indeksu możesz skutecznie przejść do tego rozdziału, pomijając resztę.

Ale oprócz faktycznych 1000 stron potrzebujesz jeszcze ~ 10 stron, aby wyświetlić indeksy, czyli łącznie 1010 stron.

Tak więc indeks jest osobną sekcją, która przechowuje wartości zindeksowanej kolumny + wskaźnika do zindeksowanego wiersza w uporządkowanej kolejności w celu wydajnego wyszukiwania.

W szkołach rzeczy są proste, prawda? : P

Gdy pierwszy raz to przeczytałem, było to dla mnie bardzo pomocne. Dziękuję Ci.

Od tego czasu zyskałem pewien wgląd w wadę tworzenia indeksów: jeśli piszesz do tabeli ( UPDATElub INSERT) z jednym indeksem, w rzeczywistości masz dwie operacje zapisu w systemie plików. Jeden dla danych tabeli, a drugi dla danych indeksu (i uciekanie się do nich (i - jeśli jest klastrowany - uciekanie się danych tabeli)). Jeśli tabela i indeks znajdują się na tym samym dysku twardym, kosztuje to więcej czasu. Zatem tabela bez indeksu (sterty) pozwoliłaby na szybsze operacje zapisu. (gdybyś miał dwa indeksy, skończyłbyś się trzema operacjami zapisu i tak dalej)

Jednak zdefiniowanie dwóch różnych lokalizacji na dwóch różnych dyskach twardych dla danych indeksu i danych tabeli może zmniejszyć / wyeliminować problem zwiększonego kosztu czasu. Wymaga to zdefiniowania dodatkowych grup plików z odpowiednimi plikami na pożądanych dyskach twardych i zdefiniowania lokalizacji tabeli / indeksu według potrzeb.

Innym problemem związanym z indeksami jest ich fragmentacja w czasie w miarę wstawiania danych. REORGANIZEpomaga, musisz napisać procedury, aby to zrobić.

W niektórych scenariuszach sterta jest bardziej pomocna niż tabela z indeksami,

np .: - Jeśli masz dużo konkurencyjnych zapisów, ale tylko jedną noc czytaj poza godzinami pracy w celu zgłoszenia.

Również rozróżnienie między indeksami klastrowymi i nieklastrowanymi jest raczej ważne.

Pomógł mi: - Co tak naprawdę oznacza indeks klastrowany i nieklastrowany?

Indeks jest tylko strukturą danych, która przyspiesza wyszukiwanie określonej kolumny w bazie danych. Ta struktura to zwykle b-drzewo lub tablica skrótu, ale może to być dowolna inna struktura logiczna.

Teraz powiedzmy, że chcemy uruchomić zapytanie, aby znaleźć wszystkie dane wszystkich pracowników o nazwach „Abc”?

SELECT * FROM Employee 
WHERE Employee_Name = 'Abc'

Co by się stało bez indeksu?

Oprogramowanie bazy danych musiałoby dosłownie patrzeć na każdy wiersz w tabeli pracownika, aby sprawdzić, czy nazwa pracownika dla tego wiersza to „Abc”. A ponieważ chcemy, aby każdy wiersz o nazwie „Abc” był w środku, nie możemy przestać szukać, gdy znajdziemy tylko jeden wiersz o nazwie „Abc”, ponieważ mogą istnieć inne wiersze o nazwie Abc . Tak więc każdy wiersz do ostatniego wiersza musi zostać przeszukany - co oznacza, że ​​tysiące wierszy w tym scenariuszu będą musiały zostać zbadane przez bazę danych w celu znalezienia wierszy o nazwie „Abc”. Jest to tak zwane skanowanie pełnego stołu

Jak indeks bazy danych może poprawić wydajność

Cały sens posiadania indeksu polega na przyspieszeniu wyszukiwań poprzez zasadniczo zmniejszenie liczby rekordów / wierszy w tabeli, które należy zbadać. Indeks jest strukturą danych (najczęściej B-drzewem), która przechowuje wartości dla określonej kolumny w tabeli.

Jak działa indeks B-drzew?

Powodem, dla którego drzewa B są najbardziej popularną strukturą danych dla indeksów, jest fakt, że są one wydajne czasowo - ponieważ wyszukiwania, usuwania i wstawiania można dokonywać w czasie logarytmicznym. Innym ważnym powodem, dla którego drzewa B są częściej używane, jest to, że dane przechowywane w drzewie B można sortować. RDBMS zazwyczaj określa, która struktura danych jest faktycznie używana dla indeksu. Ale w niektórych scenariuszach z niektórymi RDBMS można faktycznie określić, jakiej struktury danych ma używać baza danych podczas tworzenia samego indeksu.

Jak działa indeks tabeli skrótów?

Powodem stosowania indeksów skrótu jest to, że tabele skrótów są niezwykle wydajne, jeśli chodzi o wyszukiwanie wartości. Tak więc zapytania, które porównują równość z łańcuchem, mogą bardzo szybko pobrać wartości, jeśli używają indeksu skrótu.

Na przykład zapytanie, które omówiliśmy wcześniej, może skorzystać z indeksu skrótu utworzonego w kolumnie Employee_Name. Sposób działania indeksu skrótu polega na tym, że wartość kolumny będzie kluczem do tabeli skrótów, a rzeczywista wartość odwzorowana na ten klucz będzie tylko wskaźnikiem do danych wiersza w tabeli. Ponieważ tablica skrótów jest w zasadzie tablicą asocjacyjną, typowy wpis wyglądałby mniej więcej tak: „Abc => 0x28939 ″, gdzie 0x28939 odnosi się do wiersza tabeli, w którym Abc jest przechowywany w pamięci. Wyszukiwanie wartości takiej jak „Abc” w indeksie tabeli skrótów i powrót do odniesienia do wiersza w pamięci jest oczywiście znacznie szybsze niż skanowanie tabeli w celu znalezienia wszystkich wierszy o wartości „Abc” w kolumnie nazwa_pracownika.

Wady indeksu mieszania

Tabele skrótów nie są posortowanymi strukturami danych i istnieje wiele rodzajów zapytań, w których indeksy skrótów nawet nie są w stanie pomóc. Załóżmy na przykład, że chcesz dowiedzieć się o wszystkich pracownikach, którzy nie ukończyli 40 lat. Jak możesz to zrobić za pomocą indeksu tabeli skrótów? Cóż, nie jest to możliwe, ponieważ tablica skrótów nadaje się tylko do wyszukiwania par kluczowych wartości - co oznacza zapytania sprawdzające równość

Co dokładnie znajduje się w indeksie bazy danych? Teraz już wiesz, że indeks bazy danych jest tworzony w kolumnie w tabeli i że indeks przechowuje wartości w tej konkretnej kolumnie. Należy jednak pamiętać, że indeks bazy danych nie przechowuje wartości w innych kolumnach tej samej tabeli. Na przykład, jeśli utworzymy indeks w kolumnie nazwa_pracownika, oznacza to, że wartości kolumny o_pracie i adresie o pracowniku również nie są przechowywane w indeksie. Gdybyśmy tylko zachowali wszystkie pozostałe kolumny w indeksie, byłoby to jak utworzenie kolejnej kopii całej tabeli - która zajmowałaby zbyt dużo miejsca i byłaby bardzo nieefektywna.

Skąd baza danych wie, kiedy używać indeksu? Po uruchomieniu zapytania typu „WYBIERZ * OD PRACOWNIKA GDZIE nazwa_pracy =„ Abc ”” baza danych sprawdzi, czy istnieje indeks zapytanych kolumn. Zakładając, że kolumna Employee_Name ma utworzony indeks, baza danych będzie musiała zdecydować, czy rzeczywiście warto użyć tego indeksu do znalezienia przeszukiwanych wartości - ponieważ istnieją scenariusze, w których użycie indeksu bazy danych jest mniej wydajne i bardziej wydajne po prostu zeskanować całą tabelę.

Jaki jest koszt posiadania indeksu bazy danych?

Zajmuje miejsce - a im większy stół, tym większy indeks. Innym spadkiem wydajności związanym z indeksami jest fakt, że za każdym razem, gdy dodajesz, usuwasz lub aktualizujesz wiersze w odpowiedniej tabeli, te same operacje będą musiały zostać wykonane w twoim indeksie. Pamiętaj, że indeks musi zawierać te same dane, nawet do najdrobniejszych, jak to, co znajduje się w kolumnach tabeli, które obejmuje indeks.

Zasadniczo indeks powinien być tworzony w tabeli tylko wtedy, gdy dane w indeksowanej kolumnie będą często wyszukiwane.

Zobacz też

1. Jakie kolumny generalnie tworzą dobre indeksy?
2. Jak działają indeksy baz danych

Prosty opis!

Indeks jest niczym innym jak strukturą danych, która przechowuje wartości dla konkretnej kolumny w tabeli. Indeks jest tworzony w kolumnie tabeli.

Przykład: Mamy tabeli bazy danych o nazwie Userz trzema kolumnami - Name, Agei Address. Załóżmy, że Usertabela ma tysiące wierszy.

Teraz powiedzmy, że chcemy uruchomić zapytanie, aby znaleźć wszystkie szczegóły użytkowników o nazwie „John”. Jeśli uruchomimy następujące zapytanie:

SELECT * FROM User 
WHERE Name = 'John'

Oprogramowanie bazy danych musiałoby dosłownie patrzeć na każdy wiersz w Usertabeli, aby sprawdzić, czy Namedla tego wiersza jest „John”. Zajmie to dużo czasu.

W tym indexpomaga nam: indeks służy do przyspieszenia zapytań, zasadniczo zmniejszając liczbę rekordów / wierszy w tabeli, którą należy zbadać .

Jak utworzyć indeks:

CREATE INDEX name_index
ON User (Name)

indexSkłada się z wartości kolumny (np Jan) z jednej tabeli , a wartości te są przechowywane w strukturze danych .

Tak więc baza danych użyje indeksu do znalezienia pracowników o nazwisku John, ponieważ indeks będzie prawdopodobnie sortowany alfabetycznie według nazwy użytkowników. A ponieważ jest posortowane, oznacza to, że wyszukiwanie nazwy jest znacznie szybsze, ponieważ wszystkie nazwy zaczynające się od „J” będą znajdować się obok siebie w indeksie!

Krótka sugestia. Ponieważ indeksowanie kosztuje dodatkowe zapisy i miejsce do przechowywania, więc jeśli aplikacja wymaga więcej operacji wstawiania / aktualizacji, możesz użyć tabel bez indeksów, ale jeśli wymaga to więcej operacji pobierania danych, powinieneś przejść do indeksowania stół.

Pomyśl o Bazie Danych jako Indeksie książki.

Jeśli masz książkę o psach i chcesz znaleźć informacje o powiedzmy, owczarkach niemieckich, możesz oczywiście przejrzeć wszystkie strony książki i znaleźć to, czego szukasz - ale to oczywiście jest czasochłonne i nie bardzo szybki.

Inną opcją jest to, że możesz po prostu przejść do sekcji Indeks książki, a następnie znaleźć to, czego szukasz, używając nazwy podmiotu, którego szukasz (w tym przypadku Owczarki niemieckie), a także patrząc na numer strony szybko znajdź to, czego szukasz.

W bazie danych numer strony jest określany jako wskaźnik, który kieruje bazę danych na adres na dysku, na którym znajduje się jednostka. Korzystając z tej samej analogii Owczarka Niemieckiego, możemy mieć coś takiego („Owczarek niemiecki”, 0x77129), gdzie0x77129 jest adres na dysku, na którym przechowywane są dane wiersza dla Owczarka niemieckiego.

Krótko mówiąc, indeks to struktura danych, która przechowuje wartości dla określonej kolumny w tabeli, aby przyspieszyć wyszukiwanie zapytań.