🙆🏼 ✍🏾 🐇 Fonctionnement des bases de données relationnelles (partie 1) 🚘 👨🏿‍💻 ♂️

Bonjour, Habr! Je vous présente la traduction de l'article
"Comment fonctionne une base de données relationnelle" .

En ce qui concerne les bases de données relationnelles, je ne peux m'empêcher de penser qu'il manque quelque chose. Ils sont utilisés partout. Il existe de nombreuses bases de données différentes: du petit SQLite utile au puissant Teradata. Mais il n'y a que quelques articles qui expliquent comment fonctionne la base de données. Vous pouvez rechercher «howdoesarelationaldatabasework» («comment fonctionnent les bases de données relationnelles») pour voir le peu de résultats. De plus, ces articles sont courts. Si vous recherchez les dernières technologies à la mode (BigData, NoSQL ou JavaScript), vous trouverez des articles plus approfondis expliquant leur fonctionnement.

Les bases de données relationnelles sont-elles trop anciennes et trop ennuyeuses pour être expliquées en dehors des cours universitaires, des articles de recherche et des livres?

, . 40 , . , - , . , . , , .

, , , . , , CRUD; . , , .

, (BigO). , , . , , : SQL . , , .

, , , . ; .

, 3 :

( , ...), , . , .

, . .

O(1) vs O(n²)

… !

( ) , . , ! , . (cost based optimization).

, . , . , , .

, " O (some_function() )", , some_function(a_certain_amount_of_data) .

**, , ** . , .

. , . , 1 1 . , :

O(1) ( ).
O(log(n)) .
— O(n²), .
.

O(1) O(n²) . , , , 2000 .

O (1) 1
O (log (n)) 7
O (n) 2 000
O (n * log (n)) 14 000
O (n²) 4 000 000

O(1) O(n²) (4 ) 2 , . , . -.

, - . 1 000 000 ( ):

O (1) 1
O (log (n)) 14
O (n) 1 000 000
O (n * log (n)) 14 000 000
O (n2) 1 000 000 000 000

, , O (n2) ( !). 0 , , .

- O (1).
O (log (n)).
O (n).
O (n * log (n)).
O (n²).

: .

, :

, , n², :

n⁴: ! .
3ⁿ: ! , , ( ).
n: .
nⁿ: , , ...

: « », . () .

MergeSort ( )

, ? ? sort ()… , … , sort ().

, : . , , , , . , join , merge join ( ).

Merge ()

, : 2 N / 2 N- N . .

, :

, 8 2 4- . 4- :

1) ( = )
2) , 8
3) ,
1,2,3, .
, 8 .

, 4- , «» .

, , merge:

array mergeSort(array a)
   if(length(a)==1)
      return a[0];
   end if

   //recursive calls
   [left_array right_array] := split_into_2_equally_sized_arrays(a);
   array new_left_array := mergeSort(left_array);
   array new_right_array := mergeSort(right_array);

   //merging the 2 small ordered arrays into a big one
   array result := merge(new_left_array,new_right_array);
   return result;

, , (: ). , ; , . , :

,
, ( ), .

Division phase ( )

3 . — log(N) ( N=8, log(N) = 3).

! — . , 2. — , . ( 2).

Sorting phase ( )

() . , N = 8 :

4 , 2
2 , 4
1 , 8

log (N) , N * log(N) .

merge sort

, , , , .

: in -place ( ).

/. , , . , 100 .

: .

/ / .

, Hadoop ( ).

(!).

( ) , . , , .

, -

, , 3 . , . .

— . . :

2- :

, .
(integer, string, date …).

, , .

, , , , , . N , N — , , ? .

: : heap-organizedtables index-organizedtables. .

— , :

N = 15 . , 208:

, 136. 136<208, 136.
398>208, , 398
250>208, , 250
200<208, , 200. 200 , ( , , 200).

, , 40

, 136. 136 > 40, 136.
80 > 40, , 80
40= 40, . ( ) .
, , , .

. , , log (N) . , log(N), !

, . integer, , - . , , "country" (column 3) :

,
, ,
"UKnode" .

log(N) N . , — .

(, , 2 , , …) , (.. ) ( ).

B+TreeIndex

, , . O(N) , (, ). , -, . . B+Tree. B+Tree :

() ( )
.

, ( ). , , « », ( ). O(log(N)) ( ). , .

B+Tree, 40 100:

40 ( 40, 40 ), .
40, , 100.

, M , N . log(N) . , , M M . M+log(N) N . , ( M + log (N) ), . (, 200 ) N (1 000 000 ), .

(!). (, , B+Tree):

B+Tree, .
B+Tree, O (log (N)) O (N).

, B+Tree . , . : B+ O (log (N)). , . , / / , O (log (N)) . , ( ).

, B +Tree. B+Tree , MySQL. , InnoDB ( MySQL) .

: , - B+ .

Hashtable (-)

— -. , . , - , - ( hash join). (, , ).

- — , . - :

- . ( ).
. , , , .

- 10 . , 5 , , , 5 . - 10 . , , :

0, 0,
1, 1,
2, 2,
…

, , .

, 78:

- - 78, 8.
- 8, , , 78.
78
2 ( -, ).

, , 59:

- - 59, 9.
- 9 , — 99. 99!=59, 99 .
, (9), (79), …, (29).
.
7 .

-

, , , !

- 1 000 000 ( , 6 ), 1 , 000059 . — -, , .

- . , - , :

( — )
2 ( — )
2 ( — , )
…

- - O(1).

vs -

, .

Une table de hachage peut être partiellement chargée en mémoire et les segments restants peuvent rester sur le disque.
Avec un tableau, vous devez utiliser un espace contigu en mémoire. Si vous chargez une grande table, il est très difficile de trouver suffisamment d'espace continu .
Pour une table de hachage, vous pouvez sélectionner la clé souhaitée (par exemple, le pays et le nom de la personne).

Pour plus d'informations, vous pouvez lire l'article sur Java HashMap , qui est une implémentation efficace d'une table de hachage; Vous n'avez pas besoin de comprendre Java pour comprendre les concepts présentés dans cet article.

Fonctionnement des bases de données relationnelles (partie 1)

O(1) vs O(n2)