مرحبا يا هابر! أقدم لكم ترجمة المقال
"كيف تعمل قاعدة البيانات العلائقية" .

عندما يتعلق الأمر بقواعد البيانات العلائقية ، لا يسعني إلا التفكير في شيء مفقود. يتم استخدامها في كل مكان. هناك العديد من قواعد البيانات المختلفة: من SQLite الصغيرة والمفيدة إلى Teradata القوية. ولكن لا يوجد سوى عدد قليل من المقالات التي تشرح كيفية عمل قاعدة البيانات. يمكنك البحث عن "howdoesarelationaldatabasework" ("كيفية عمل قواعد البيانات العلائقية") لمعرفة عدد النتائج القليلة الموجودة. علاوة على ذلك ، هذه المقالات قصيرة. إذا كنت تبحث عن أحدث التقنيات العصرية (BigData أو NoSQL أو JavaScript) ، فستجد المزيد من المقالات المتعمقة التي توضح كيفية عملها.

هل قواعد البيانات العلائقية قديمة جدًا ومملة جدًا بحيث لا يمكن شرحها خارج الدورات الجامعية والأبحاث والكتب؟

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

?

, .

• يمكن تحميل جدول التجزئة جزئياً في الذاكرة ، ويمكن أن تبقى الأجزاء المتبقية على القرص.
• باستخدام الصفيف ، يجب استخدام مساحة متجاورة في الذاكرة. إذا كنت تقوم بتحميل جدول كبير ، فمن الصعب جدًا العثور على مساحة مستمرة كافية .
• بالنسبة لجدول التجزئة ، يمكنك تحديد المفتاح المطلوب (على سبيل المثال ، البلد واسم الشخص).

لمزيد من المعلومات ، يمكنك قراءة المقال على Java HashMap ، وهو تطبيق فعال لجدول التجزئة ؛ لست بحاجة إلى فهم Java لفهم المفاهيم المقدمة في هذه المقالة.