Olá Habr! Apresento a você a tradução do artigo
"Como funciona um banco de dados relacional" .

Quando se trata de bancos de dados relacionais, não posso deixar de pensar que algo está faltando. Eles são usados ​​em todos os lugares. Existem muitos bancos de dados diferentes: do pequeno e útil SQLite ao poderoso Teradata. Mas existem apenas alguns artigos que explicam como o banco de dados funciona. Você pode procurar por "como executar tarefas de banco de dados relacionais" ("como os bancos de dados relacionais funcionam") para ver quantos resultados existem. Além disso, esses artigos são curtos. Se você estiver procurando pelas mais recentes tecnologias da moda (BigData, NoSQL ou JavaScript), encontrará artigos mais detalhados explicando como eles funcionam.

Os bancos de dados relacionais são muito antigos e muito chatos para serem explicados fora dos cursos, documentos de pesquisa e livros da universidade?

, . 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 -

?

, .

• Uma tabela de hash pode ser parcialmente carregada na memória e os segmentos restantes podem permanecer no disco.
• Com uma matriz, você deve usar espaço contíguo na memória. Se você estiver carregando uma tabela grande, é muito difícil encontrar espaço contínuo suficiente .
• Para uma tabela de hash, você pode selecionar a chave desejada (por exemplo, o país e o nome da pessoa).

Para obter mais informações, você pode ler o artigo sobre Java HashMap , que é uma implementação eficiente de uma tabela de hash; Você não precisa entender Java para entender os conceitos apresentados neste artigo.