Indeksy baz danych i ich notacja Big-O

Question

Próbuję zrozumieć wydajność indeksów baz danych w zakresie notacji Big-O. Nie wiedząc wiele o tym, domyślam się, że:

• Zapytanie na klucz podstawowy lub unikalny indeks daje czas wyszukiwania O (1).
• Kwerenda na nieunikalnym indeksie również da czas O (1), aczkolwiek być może "1" jest wolniejszy niż dla unikalnego indeksu (?)
• Zapytanie o kolumnę bez indeksu da O (N) czas wyszukiwania (pełne skanowanie tabeli).

Czy to na ogół jest poprawne? Czy wysłanie zapytania o klucz podstawowy kiedykolwiek przyniesie gorszą wydajność niż O (1)? Moja szczególna troska dotyczy SQLite, ale chciałbym wiedzieć, w jakim stopniu różni się to również w różnych bazach danych.

Answer 1

Większość relacyjnych baz danych indeksuje strukturę jako B-drzewa.

Jeśli tabela ma indeks klastrowy, strony danych są przechowywane jako węzły liści drzewa B-tree. Zasadniczo indeks klastrowania staje się tabelą.

W przypadku tabel bez indeksu klastrowania strony danych tabeli są przechowywane w stercie. Wszelkie nieklastrowane indeksy to B-drzewa, w których węzeł liścia drzewa B identyfikuje określoną stronę w stercie.

Najgorsze wysokość przypadek B-drzewa jest O (log n), a ponieważ wyszukiwanie jest uzależniona od wysokości wyszukiwań B-tree uruchomić w coś (średnio)

O (log _t n)

gdzie t jest czynnikiem minimalizacji (każdy węzeł musi zawierać co najmniej t -1 klucze i co najwyżej 2 * T * -1 kluczy (na przykład, 2 * t * dzieci).

Tak rozumiem.

Oczywiście różne systemy baz danych mogą również wykorzystywać różne struktury danych pod maską.

A jeśli zapytanie nie korzysta z indeksu, oczywiście, to wyszukiwanie jest iteracją na stercie lub drzewie B zawierającym strony danych.

Wyszukiwanie jest trochę tańsze, jeśli użyty indeks może spełnić zapytanie; w przeciwnym razie wymagane jest pole do pobrania odpowiedniego datapage w pamięci.

Answer 2

Zapytania indeksowane (unikalne lub nie) są bardziej typowo O (log n). Bardzo upraszczając, możesz myśleć o tym, że jest podobny do wyszukiwania binarnego w posortowanej tablicy. Dokładniej, zależy to od typu indeksu. Ale na przykład wyszukiwanie w drzewie B to nadal O (log n).

Jeśli nie ma indeksu, to tak, to O (N).

Answer 3

Jeśli wybierzesz te same kolumny szukać następnie

• Primary lub unqiue będzie O (log N): jest to wyszukiwarka B-drzewo
• nieunikatowa indeks jest także O (log n) + trochę: to wyszukiwarka b-drzewo
• no index = O (N)

Jeśli potrzebujesz informacji od innego "źródła" (wskaźnik skrzyżowanie, zakładka/klucz wyszukiwania itp), ponieważ indeks jest niekrywając, możesz mieć O (n + log n) lub O (log n + log n + log n) z powodu wielu trafień indeksowych + sortowanie pośrednie.

Jeśli statystyki wskazują, że wymagają wysokiego% rzędów (wskaźnik np mało selektywne), to wskaźnik może być ignorowane się skanowanie = O (n)

Answer 4

odbierze dają dobry punkt wyjścia; ale chciałbym tylko dodać, że aby uzyskać O (1), sam indeks podstawowy musiałby być oparty na haszymowaniu (który zazwyczaj nie jest domyślnym wyborem); więc częściej jest to logarytmiczny (B-drzewo).

Masz rację, że indeksy wtórne mają zazwyczaj taką samą złożoność, ale gorszą wydajność rzeczywistą - ponieważ indeks i dane nie są skupione, więc stała (liczba żądań dysku) jest większa.

Answer 5

To zależy od tego, jakie jest Twoje zapytanie.

• Warunkiem postaci Column = Value umożliwia stosowanie wskaźnika mieszającego, który wykazuje O (1) czas wyszukiwania. Jednak many databases, including SQLite, do not support them.
• Warunek korzystający z operatorów relacyjnych (<, >, , >=) może korzystać z uporządkowanego indeksu, zwykle zaimplementowanego z drzewem binarnym, który ma czas wyszukiwania O (log n).
• Bardziej skomplikowane wyrażenia, które nie mogą korzystać z indeksu, wymagają czasu O (n).

Ponieważ interesuje Cię głównie SQLite, możesz przeczytać jego Query Optimizer Overview, który wyjaśnia bardziej szczegółowo, w jaki sposób wybrane są indeksy.