B-Tree vs Hash Table

W MySQL typ indeksu to b-drzewo, a dostęp do elementu w b-drzewie odbywa się w logarytmicznym amortyzowanym czasie O(log(n)).

Z drugiej strony dostęp do elementu w tablicy skrótów znajduje się w O(1).

Dlaczego zamiast b-drzewa nie używa się tablicy skrótów w celu uzyskania dostępu do danych w bazie danych?

Możesz uzyskać dostęp do elementów tylko za pomocą ich klucza głównego w tablicy hashy. Jest to szybsze niż w przypadku algorytmu drzewiastego ( O(1)zamiastlog(n) ), ale nie można wybierać zakresów ( wszystko pomiędzy xiy ). Obsługują to algorytmy drzewiaste, Log(n)podczas gdy indeksy skrótów mogą skutkować pełnym skanowaniem tabeli O(n). Również stały narzut indeksów hash jest zwykle większy ( co nie jest czynnikiem w notacji theta, ale nadal istnieje ). Również algorytmy drzewiaste są zwykle łatwiejsze w utrzymaniu, rosną wraz z danymi, skalą itp.

Indeksy haszujące działają z predefiniowanymi rozmiarami skrótów, więc otrzymujesz kilka „zasobników”, w których przechowywane są obiekty. Te obiekty są ponownie zapętlane, aby naprawdę znaleźć właściwy w tej partycji.

Więc jeśli masz małe rozmiary, masz dużo narzutu na małe elementy, duże rozmiary powodują dalsze skanowanie.

Dzisiejsze algorytmy tablic skrótów zwykle skalują się, ale skalowanie może być nieefektywne.

Rzeczywiście istnieją skalowalne algorytmy haszujące. Nie pytaj mnie, jak to działa - dla mnie też to tajemnica. AFAIK, ewoluowali ze skalowalnej replikacji, w której ponowne haszowanie nie jest łatwe.

Nazywa POŚPIECH - R eplication U RSR S calable H spopielania, a te tak zwane są algorytmy algorytmy szczytu.

Może się jednak zdarzyć, że indeks przekroczy dopuszczalny rozmiar w porównaniu z rozmiarami skrótów i cały indeks będzie wymagał ponownego zbudowania. Zwykle nie stanowi to problemu, ale w przypadku ogromnych, ogromnych, ogromnych baz danych może to zająć kilka dni.

Kompromis dla algorytmów drzewiastych jest niewielki i są one odpowiednie dla prawie każdego przypadku użycia, a zatem są domyślne.

Jeśli jednak masz bardzo precyzyjny przypadek użycia i wiesz dokładnie, co i tylko co będzie potrzebne, możesz skorzystać z indeksów haszujących.

Właściwie wygląda na to, że MySQL używa obu rodzajów indeksów albo tabeli skrótów, albo b-drzewa, zgodnie z poniższym linkiem .

Różnica między używaniem b-drzewa a tablicą skrótów polega na tym, że pierwsza z nich umożliwia porównywanie kolumn w wyrażeniach, które używają operatorów =,>,> =, <, <= lub BETWEEN, podczas gdy druga jest używana tylko do porównania równości, które używają operatorów = lub <=>.

Złożoność czasowa tabel skrótów jest stała tylko w przypadku tabel o wystarczającej wielkości (musi być wystarczająco dużo zasobników do przechowywania danych). Rozmiar tabeli bazy danych nie jest znany z góry, dlatego tabela musi być od czasu do czasu ponownie haszowana, aby uzyskać optymalną wydajność z tablicy haszującej. Ponowne haszowanie jest również drogie.

Myślę, że Hashmapy nie skalują się również i mogą być drogie, gdy cała mapa wymaga ponownego skompresowania.

Pick DB / OS był oparty na haszowaniu i działał dobrze. Przy większej ilości pamięci w dzisiejszych czasach do obsługi wydajnych rzadkich tablic mieszających i nadmiarowego mieszania do obsługi zapytań o skromny zakres, powiedziałbym, że hashowanie może jeszcze mieć swoje miejsce (niektórzy woleliby mieć inne formy dopasowywania podobieństw niezwiązanych z zakresem, takie jak symbole wieloznaczne i wyrażenia regularne ). Zalecamy również kopiowanie, aby zachować ciągłość łańcuchów kolizji, gdy hierarchie pamięci mają duże różnice szybkości.