Spróbuję wyjaśnić na przykładzie, co to oznacza. Indeksy oparte na B-drzewo nie są czymś konkretnym. W przeciwieństwie do tego jest to dość powszechna koncepcja.
Więc kiedy tworzysz indeks - pokazujesz bazie danych łatwiejszy sposób na znalezienie czegoś. Ale ten indeks jest przechowywany gdzieś ze wskaźnikiem wskazującym na lokalizację oryginalnego dokumentu. Ta informacja jest uporządkowana i możesz spojrzeć na nią jako na drzewo binarne, które ma naprawdę fajną właściwość:wyszukiwanie jest skrócone z O(n) (skanowanie liniowe) do O(log(n)) . Co jest znacznie szybsze, ponieważ za każdym razem zmniejszamy naszą przestrzeń o połowę (potencjalnie możemy skrócić czas z 10^6 do 20 wyszukiwań). Na przykład mamy dużą kolekcję z polem {a : some int, b: 'some other things'} a jeśli zindeksujemy go przez a, otrzymamy inną strukturę danych, która jest posortowana według a . Wygląda to tak (nie mam na myśli, że jest to kolejna kolekcja, to tylko dla demonstracji):
{a : 1, pointer: to the field with a = 1}, // if a is the smallest number in the starting collection
...
{a : 999, pointer: to the field with a = 990} // assuming that 999 is the biggest field
Więc teraz szukamy pola a =18. Zamiast przechodzić jeden po drugim przez wszystkie elementy, bierzemy coś pośrodku i jeśli jest większe niż 18, to dzielimy dolną część na pół i sprawdzamy tam element . Kontynuujemy, aż znajdziemy a =18. Następnie patrzymy na wskaźnik i wiedząc o tym, wyodrębniamy oryginalne pole.
Podobnie ma się sytuacja z indeksem złożonym (zamiast porządkowania według jednego elementu zamawiamy według wielu). Na przykład masz kolekcję:
{ "item": 5, "location": 1, "stock": 3, 'a lot of other fields' } // was stored at position 5 on the disk
{ "item": 1, "location": 3, "stock": 1, 'a lot of other fields' } // position 1 on the disk
{ "item": 2, "location": 5, "stock": 7, 'a lot of other fields' } // position 3 on the disk
... huge amount of other data
{ "item": 1, "location": 1, "stock": 1, 'a lot of other fields' } // position 9 on the disk
{ "item": 1, "location": 1, "stock": 2, 'a lot of other fields' } // position 7 on the disk
i chcesz indeks { "item":1, "location":1, "stock":1 }. Tabela przeglądowa wyglądałaby tak (jeszcze raz - to nie jest kolejna kolekcja, to tylko demonstracja):
{ "item": 1, "location": 1, "stock": 1, pointer = 9 }
{ "item": 1, "location": 1, "stock": 2, pointer = 7 }
{ "item": 1, "location": 3, "stock": 1, pointer = 1 }
{ "item": 2, "location": 5, "stock": 7, pointer = 3 }
.. huge amount of other data (but not necessarily here. If item would be one it would be somewhere next to items 1)
{ "item": 5, "location": 1, "stock": 3, pointer = 5 }
Zobacz, że tutaj wszystko jest posortowane w zasadzie według pozycji, następnie według lokalizacji, a następnie według wskaźnika. Tak samo jak w przypadku pojedynczego indeksu nie musimy skanować wszystkiego. Jeśli mamy zapytanie, które szuka item = 2, location = 5 and stock = 7 możemy szybko zidentyfikować, gdzie dokumenty z item = 2 są, a następnie w ten sam sposób, szybko identyfikują, gdzie wśród tych elementów element z location 5 i tak dalej.
A teraz interesująca część . Stworzyliśmy też tylko jeden indeks (chociaż jest to indeks złożony, to wciąż jest to jeden) możemy go użyć do szybkiego odnalezienia elementu
- tylko przez
item. Tak naprawdę wszystko, co musimy zrobić, to tylko pierwszy krok. Nie ma więc sensu tworzyć kolejnego indeksu {location :1}, ponieważ jest on już objęty indeksem złożonym. - również możemy szybko znaleźć tylko według
item and by location(wystarczy nam tylko 2 kroki).
Fajny indeks 1, ale pomaga nam na trzy różne sposoby. Ale poczekaj chwilę:co jeśli chcemy znaleźć według item and stock . Och, wygląda na to, że możemy również przyspieszyć to zapytanie. Możemy w log(n) znaleźć wszystkie elementy z konkretnym przedmiotem i ... tutaj musimy się zatrzymać - magia się skończyła. Musimy przejść przez wszystkie z nich. Ale nadal całkiem nieźle.
Ale niech nam pomoże z innymi pytaniami. Spójrzmy na zapytanie według location który wygląda jak był już zamówiony. Ale jeśli na to spojrzysz - zobaczysz, że to bałagan. Jeden na początku, drugi na końcu. To nie może ci w ogóle pomóc.
Mam nadzieję, że to wyjaśnia kilka rzeczy:
- dlaczego indeksy są dobre (skróć czas z O(n) do potencjalnie O(log(n))
- dlaczego indeksy złożone mogą pomóc w przypadku niektórych zapytań, niemniej jednak nie utworzyliśmy indeksu dla tego konkretnego pola i nie pomagamy w przypadku niektórych innych zapytań.
- jakie indeksy obejmuje indeks złożony
- dlaczego indeksy mogą szkodzić (tworzą dodatkową strukturę danych, którą należy utrzymywać)
A to powinno powiedzieć kolejną ważną rzecz:indeks nie jest srebrną kulą . Nie możesz przyspieszyć wszystkich zapytań, więc głupio wydaje się myśleć, że tworząc indeksy na wszystkich polach WSZYSTKO byłoby super szybkie.
