Hallo Habr! Ich präsentiere Ihnen die Übersetzung des Artikels
"Wie funktioniert eine relationale Datenbank?" .

Wenn es um relationale Datenbanken geht, kann ich nicht anders, als zu glauben, dass etwas fehlt. Sie werden überall verwendet. Es gibt viele verschiedene Datenbanken: von der kleinen und nützlichen SQLite bis zu den leistungsstarken Teradata. Es gibt jedoch nur wenige Artikel, in denen die Funktionsweise der Datenbank erläutert wird. Sie können nach "howdoesarelationaldatabasework" ("wie relationale Datenbanken funktionieren") suchen, um zu sehen, wie wenige Ergebnisse es gibt. Darüber hinaus sind diese Artikel kurz. Wenn Sie nach den neuesten Modetechnologien (BigData, NoSQL oder JavaScript) suchen, finden Sie ausführlichere Artikel, in denen die Funktionsweise erläutert wird.

Sind relationale Datenbanken zu alt und zu langweilig, um außerhalb von Universitätskursen, Forschungsarbeiten und Büchern erklärt zu werden?

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

?

, .

• Eine Hash-Tabelle kann teilweise in den Speicher geladen werden , und die verbleibenden Segmente können auf der Festplatte verbleiben.
• Bei einem Array müssen Sie zusammenhängenden Speicherplatz im Speicher verwenden. Wenn Sie einen großen Tisch laden, ist es sehr schwierig, genügend durchgehenden Platz zu finden .
• Für eine Hash-Tabelle können Sie den gewünschten Schlüssel auswählen (z. B. das Land und den Namen der Person).

Weitere Informationen finden Sie im Artikel zu Java HashMap , einer effizienten Implementierung einer Hash-Tabelle. Sie müssen Java nicht verstehen, um die in diesem Artikel vorgestellten Konzepte zu verstehen.