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 .
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 na INDEX. Czy to jest naprawdę O(1)? Z indeksem B-drzewa brzmi to bardzo podobnie O(log2(N)). Czy mam rację?
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 :)