Jaki jest algorytm wyszukiwania zapytań w bazie danych?

Question

Dzień dobry wszystkim, obecnie prowadzę badania nad optymalizacją algorytmów wyszukiwania.

Na razie szukam w bazie danych.

W bazie danych z obsługą SQL.

Potrafię napisać zapytanie do konkretnej tabeli.

1. Wybierz liczbę z tabeli 1, gdzie Nazwa = "Testuj";
2. Wybierz * z tabeli 1, gdzie Nazwa = "Testuj";

1 wyszukuje numer z Tabeli 1, z której Nazwa jest Testowana, a 2 szuka całej kolumny dla nazwy Test.

Rozumiem pojęcie funkcji, ale to, co mnie interesuje, aby dowiedzieć się, jakie jest podejście do wyszukiwania?

Czy jest to zwykłe liniowe wyszukiwanie, w którym od pierwszego indeksu do n-tego indeksu będzie pobierać tak długo, jak warunek jest prawdziwy, a zatem ma prędkość O (n) lub ma unikalny algorytm, który przyspiesza jego proces?

Answer 1

bardzo dobre pytanie, ale może mieć wiele odpowiedzi, w zależności od struktury tabeli i jak jest znormalizowana ...

Zazwyczaj do wykonywania Seacrh w SELECT zapytania DBMS sortuje tablicę (używa mergesort ponieważ ten algorytm jest dobry dla I/O na dysku, a nie na quicksorcie), to w zależności od indeksów (jeśli tabela ma) po prostu pasuje do liczb, ale jeśli struktura jest bardziej złożona, DBMS może wykonać wyszukiwanie w drzewie, ale to jest zbyt głęboka, pozwól, że ponownie przeanalizuję moje notatki, które zrobiłem.

Polecam aktywowanie planu wykonania kwerendy, here is an example, jak to zrobić w Sql Server 2008. Następnie wykonaj instrukcję SELECT z klauzulą ​​WHERE, a będziesz mógł zacząć rozumieć, co się dzieje w DBMS.

Answer 2

Jeśli nie ma indeksów, to tak, wykonywane jest wyszukiwanie liniowe.

Jednak bazy danych zazwyczaj używają indeksu B Tree podczas określania kolumny (kolumn) jako klucza. Są to specjalne formaty struktury danych, które są specjalnie dostrojone (wysokie współczynniki rozgałęzienia drzewa), aby dobrze działały na sprzęcie dysku magnetycznego, gdzie najważniejszym czynnikiem czasochłonnym jest operacja wyszukiwania (głowica magnetyczna musi przesunąć się do innej części pliku).

Możesz myśleć o indeksie jako posortowanej/uporządkowanej kopii wartości w kolumnie. Można go szybko określić, jeśli szukana wartość znajduje się w indeksie. Jeśli ją znajdzie, znajdzie również wskaźnik wskazujący właściwą lokalizację odpowiedniego wiersza w głównym pliku danych (aby mógł przejść do innych kolumn w wierszu). Czasami indeks zawierający wiele kolumn zawiera wszystkie dane wymagane przez zapytanie, a następnie nie musi przeskakiwać do głównego pliku, może po prostu odczytać, co znalazł, a następnie zrobić.

Istnieją inne typy indeksów, ale myślę, że wpadłeś na pomysł - duplikaty danych i uporządkowanie ich w szybki sposób wyszukiwania.

W dużej bazie danych indeksy sprawiają, że różnica między oczekiwaniem na ułamek sekundy, a prawdopodobnie dniami, aż złożone zapytanie zostanie wykonane.

btw- drzewa B nie są prostą i łatwą do zrozumienia strukturą danych, a algorytm przejścia jest również złożony. Ponadto przejście jest jeszcze brzydsze niż większość kodu, który można znaleźć, ponieważ w bazie danych stale ładują/rozładowują porcje danych z dysku i zarządzają nimi w pamięci, co w znacznym stopniu zakłóca kod. Ale jeśli znasz binary search trees, to myślę, że dobrze rozumiesz tę koncepcję.

Answer 3

Cóż, to zależy od sposobu przechowywania danych i tego, co próbujesz zrobić.

• Jak już wskazano, wspólną strukturą do przechowywania wpisów jest B+ tree. Drzewo jest dobrze zoptymalizowane dla dysku, ponieważ rzeczywiste dane są przechowywane tylko w liściach - a klucze są przechowywane w wewnętrznych węzłach. Zwykle pozwala na bardzo małą liczbę dostępów do dysków, ponieważ najwyższe poziomy drzewa mogą być przechowywane w pamięci RAM, a tylko kilka najniższych poziomów będzie przechowywanych na dysku i będzie wymagało odczytania dysku dla każdego z nich.
• Inną alternatywą jest hash table. Utrzymujesz w pamięci (RAM) tablicę "wskaźników" - te wskaźniki wskazują adres dysku, który zawiera wiadro zawierające wszystkie pozycje z odpowiednią wartością skrótu. Korzystając z tej metody, potrzebujesz tylko dostępu do dysku (który jest zwykle wąskim gardłem w przypadku baz danych), więc powinien być względnie szybki.
  Jednak tablica asocjacyjna nie pozwala na wydajne kwerendy zakresu (które można efektywnie wykonać w drzewie B +).

Wadą wszystkich powyższych jest to, że wymaga jednego klawisza - to znaczy jeśli tabela lub B + drzewo hash jest zbudowany zgodnie z pola „id” relacji, a potem szukaj według „klucza "- staje się bezużyteczna.
Jeśli chcesz zagwarantować szybkie wyszukiwanie wszystkich pól relacji - będziesz potrzebować kilku struktur, z których każda będzie odpowiadała innym kluczom - co nie jest zbyt wydajne pod względem pamięci.

Obecnie istnieje wiele optymalizacji, które należy rozważyć w zależności od konkretnego zastosowania. Jeśli na przykład liczba wyszukiwań ma być bardzo mała (np. Mniejszy loglogN z całości operacji), utrzymanie drzewka B + jest ogólnie mniej wydajne, niż przechowywanie elementów w postaci listy, a przy rzadkich okazjach wyszukiwania - po prostu wykonaj wyszukiwanie liniowe.