Moja wiedza na temat baz danych i SQL opiera się w większości na klasach uniwersyteckich. W każdym razie spędziłem kilka miesięcy (prawie rok) w firmie, w której pracowałem z bazami danych.
Przeczytałem kilka książek i brałem udział w kilku szkoleniach na temat baz danych, takich jak MySQL, PostgreSQL, SQLite, Oraclea także kilka nonSQL dbs takie nam MongoDB, Redis, ElasticSearchetc.
Tak jak powiedziałem, jestem początkujący, z dużą ilością braków wiedzy, ale dziś ktoś coś powiedział, co jest całkowicie sprzeczne z wiedzą mojego początkującego.
Pozwól mi wyjaśnić. Weźmy bazę danych SQL i stwórzmy prostą tabelę Personz kilkoma rekordami w środku:
id | name | age
-----------------
1 | Alex | 24
2 | Brad | 34
3 | Chris | 29
4 | David | 28
5 | Eric | 18
6 | Fred | 42
7 | Greg | 65
8 | Hubert | 53
9 | Irvin | 17
10 | John | 19
11 | Karl | 23Teraz jest to część, na której chciałbym się skupić - idjest INDEX.
Do tej pory myślałem, że działa w ten sposób: kiedy tworzony jest stół, jest INDEXon pusty. Kiedy INDEXdodam nowy rekord do mojej tabeli, jest on ponownie obliczany na podstawie niektórych alghortimów. Na przykład:
Grupowanie jeden po drugim:
1 ... N
N+1 ... 2N
...
XN+1 ... (X+1)Nwięc na przykład z size = 11 elementsi N = 3będzie tak:
id | name | age
-----------------
1 | Alex | 24 // group0
2 | Brad | 34 // group0
3 | Chris | 29 // group0
4 | David | 28 // group1
5 | Eric | 18 // group1
6 | Fred | 42 // group1
7 | Greg | 65 // group2
8 | Hubert | 53 // group2
9 | Irvin | 17 // group2
10 | John | 19 // group3
11 | Karl | 23 // group3Tak więc, gdy używam zapytania SELECT * FROM Person WHERE id = 8, wykona on proste obliczenia 8 / 3 = 2, więc musimy poszukać tego obiektu, group2a następnie ten wiersz zostanie zwrócony:
8 | Hubert | 53
To podejście działa w czasie O(k)gdzie k << size. Oczywiście algorytm porządkowania wierszy w grupach jest z pewnością znacznie bardziej skomplikowany, ale myślę, że ten prosty przykład pokazuje mój punkt widzenia.
Chciałbym teraz przedstawić inne podejście, które zostało mi dzisiaj pokazane.
Weźmy jeszcze raz tę tabelę:
id | name | age
-----------------
1 | Alex | 24
2 | Brad | 34
3 | Chris | 29
4 | David | 28
5 | Eric | 18
6 | Fred | 42
7 | Greg | 65
8 | Hubert | 53
9 | Irvin | 17
10 | John | 19
11 | Karl | 23Teraz tworzymy coś podobnego do Hashmap(w rzeczywistości dosłownie jest to Hash Map), która jest odwzorowana idna addresswiersz o tym identyfikatorze. Powiedzmy:
id | addr
---------
1 | @0001
2 | @0010
3 | @0011
4 | @0100
5 | @0101
6 | @0110
7 | @0111
8 | @1000
9 | @1001
10 | @1010
11 | @1011Więc teraz, kiedy uruchamiam moje zapytanie: SELECT * FROM Person WHERE id = 8
zamapuje bezpośrednio id = 8na adres w pamięci i wiersz zostanie zwrócony. Oczywiście jest to skomplikowane O(1).
Mam teraz kilka pytań.
1. Jakie są zalety i wady obu rozwiązań?
2. Który z nich jest bardziej popularny w obecnych implementacjach baz danych? Może różne dbs używają różnych podejść?
3. Czy istnieje w dbs nonSQL?
Z góry dziękuję
PORÓWNANIE
| B-tree | Hash Table
----------------------------------------------------
---------------- one element -------------------
----------------------------------------------------
SEARCHING | O(log(N)) | O(1) -> O(N)
DELETING | O(log(N)) | O(1) -> O(N)
INSERTING | O(log(N)) | O(1) -> O(N)
SPACE | O(N) | O(N)
----------------------------------------------------
---------------- k elements -------------------
----------------------------------------------------
SEARCHING | k + O(log(N)) | k * O(1) -> k * O(N)
DELETING | k + O(log(N)) | k * O(1) -> k * O(N)
INSERTING | k + O(log(N)) | k * O(1) -> k * O(N)
SPACE | O(N) | O(N)N - liczba rekordów
Czy mam rację? Co z kosztem odbudowy B-drzewa i tabeli mieszania po każdym wstawieniu / usunięciu ? W przypadku B-drzewa musimy zmienić niektóre wskaźniki, ale w przypadku zbalansowanego B-drzewa wymaga więcej wysiłku. Również w przypadku tabeli Hash musimy wykonać niewiele operacji, zwłaszcza jeśli nasza operacja generuje konflikty .
O(1)tobie ma rację! Po pierwsze, wygląda na to, że opisujesz indeks B-drzewa, ale masz trochę nieporozumień. Nie ma obliczeń (podział przez 3 lub cokolwiek innego), jest bardziej złożony, ponieważ drzewo ma więcej poziomów (jest drzewem, ma duże, małe, mniejsze gałęzie, ..., a następnie odchodzi :)Of course, an alghoritm to organise rows in groups is for sure much more complicated but I think this simple example shows my point of view.Oczywiście wiem, że jest to o wiele bardziej skomplikowane. Wreszcie, kiedy mówię w moim kodzie,INDEXktóre z moich rozwiązań ( 1. lub 2. ) jest bliższe temu rzeczywistemu? A co z czasem potrzebnym do uzyskania dostępu do rekordu opartego naINDEX. Czy to jest naprawdęO(1)? Z indeksem B-drzewa brzmi to bardzo podobnieO(log2(N)). Czy mam rację?Odpowiedzi:
Zasadniczo opisujesz indeks B-drzewa i indeks mieszania. Obaj mają swoje miejsce, ale oba najlepiej nadają się do różnych prac.
Zalety i wady
Indeksy drzewa B (i drzewa B +) są zwykle zrównoważone. Oznacza to, że szukanie wartości zawsze zajmie tyle samo czasu, bez względu na to, gdzie w drzewie spadnie (O (log n)). Zasadniczo liczba poziomów w drzewie jest ograniczona, więc ma tendencję do „szerszego”, a nie „głębszego”. Jednak w przypadku małych zestawów danych koszt utrzymania i korzystania z drzewa B może być czymś więcej niż tylko odczytaniem wszystkich wierszy. Indeksy B-drzewa są dobre dla dużych zestawów danych, zestawów danych o niskiej selektywności lub zestawów danych, w których zamierzasz wybrać zakres obiektów, a nie tylko jeden obiekt.
Tabele skrótów są idealne dla małych zestawów danych. Indeksy mieszania mają z góry określoną liczbę segmentów mieszania, w zależności od zastosowanego algorytmu mieszania. Wynika to z faktu, że dany algorytm skrótu może wygenerować tyle unikatowych skrótów, że staje się on „głębszy”, a nie „szerszy”. Gdy silnik bazy danych znajdzie odpowiedni segment, następnie przechodzi przez wszystkie obiekty w tym segmencie, aby znaleźć ten, który chcesz. Przy małych, wysoce selektywnych zestawach danych, każdy segment zawiera bardzo małą liczbę obiektów i jest rozwiązywany dość szybko. Przy większych zestawach danych wiadra stają się znacznie bardziej zatłoczone. Tak więc, jeśli potrzebny obiekt znajduje się w małym wiadrze lub znajduje się na początku wiadra, zwraca dość szybko. Jeśli znajduje się na końcu dużego wiadra, zajmuje więcej czasu. Indeks nie jest zrównoważony, więc wydajność wynosi od 0 (1) do O (n).
Popularność
Ogólnie rzecz biorąc, najczęściej spotykam B-drzewa. Indeksy bitmapowe są również inną opcją dla wartości o niskiej liczności (pomyśl booleany lub może płeć). Będzie się to różnić w zależności od silnika bazy danych, co do dostępnych typów indeksów.
NoSQL
Bazy danych NoSQL zdecydowanie obsługują indeksy. Większość obsługuje B-drzewa lub odmianę B-drzewa. Większość wydaje się również obsługiwać indeksy skrótów.
źródło
Jakie są zalety i wady obu rozwiązań? Drugie rozwiązanie nie może wykonać skanowania zasięgu. Doskonale nadaje się do wybierania jednego identyfikatora. Ale co jeśli chcesz identyfikatory od 3 do 8? Musi zebrać wszystkie rekordy osobno, które w prawdziwym świecie to nie tylko O (1) * 6 rekordów do odzyskania. W dużej produkcyjnej bazie danych z indeksem HashMap można uzyskać rekordy na różnych stronach, co wymaga naciśnięcia dysku i odczytania sześciu różnych stron do pamięci.
W strukturze B-drzewa, na przykład w jaki sposób twoja pierwsza sytuacja byłaby faktycznie zaimplementowana, identyfikatory byłyby sekwencyjne na dysku, a pojedyncza strona prawdopodobnie przechowywałaby identyfikatory 3-8, zwiększając szybkość skanowania zasięgu, umożliwiając indywidualny dostęp O (log n) .
Który z nich jest bardziej popularny w obecnych implementacjach baz danych? Może różne dbs używają różnych podejść? Nie mam dużego doświadczenia w wielu różnych bazach danych. Wiem, że Sql Server korzysta głównie z B-Drzewa, ale SQl 2014 ma kilka nowych indeksów Hash, których można używać w niektórych tabelach. Słyszę, że wiele baz danych Sql i baz danych buforujących opartych na pobieraniu pojedynczych rekordów również korzysta z indeksów skrótów. Ma to sens dla pamięci podręcznych, ponieważ chcesz rekord dla użytkownika A i nie potrzebujesz skanowania zasięgu.
Czy istnieje w dbs nonSQL? Tak. Rzucając okiem na dokumentację tworzenia indeksu dla postgressql, widzę, że obsługuje ona zarówno indeksy Hash i B-Tree, jak i kilka innych.
źródło