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

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

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

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

بالرغم من أن عنوان هذا المقال واضح، الغرض من هذه المقالة ليس فهم كيفية استخدام قاعدة البيانات. لذلك يجب أن تعرف بالفعل كيفية كتابة طلب اتصال بسيط واستعلامات أساسية الخام; وإلا فقد لا تفهم هذه المقالة. هذا هو الشيء الوحيد الذي تحتاج إلى معرفته، وسأشرح الباقي.

سأبدأ ببعض أساسيات علوم الكمبيوتر، مثل التعقيد الزمني للخوارزميات (BigO). أعلم أن بعضكم يكره هذا المفهوم، لكن بدونه لن تتمكنوا من فهم التعقيدات الموجودة داخل قاعدة البيانات. وبما أن هذا الموضوع ضخم سأركز على ما أعتقد أنه مهم: كيف تعالج قاعدة البيانات SQL تحقيق. سأقدم فقط مفاهيم قاعدة البيانات الأساسيةبحيث تكون لديك في نهاية المقالة فكرة عما يحدث تحت الغطاء.

بما أن هذه مقالة طويلة وتقنية تتضمن الكثير من الخوارزميات وهياكل البيانات، خذ وقتك في قراءتها. قد يكون من الصعب فهم بعض المفاهيم؛ يمكنك تخطيها والاستمرار في الحصول على الفكرة العامة.

ولمزيد المعرفة منكم، هذه المقالة مقسمة إلى 3 أجزاء:

نظرة عامة على مكونات قاعدة البيانات ذات المستوى المنخفض والعالي
نظرة عامة على عملية تحسين الاستعلام
نظرة عامة على المعاملات وإدارة المجمع الاحتياطي

الرجوع إلى الأساسيات

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

وفي هذا الجزء سأذكرك ببعض هذه المفاهيم لأنها ضرورية لفهم قاعدة البيانات. وسوف أعرض هذا المفهوم أيضا فهرس قاعدة البيانات.

يا (1) مقابل يا (ن2)

في الوقت الحاضر، لا يهتم العديد من المطورين بالتعقيد الزمني للخوارزميات... وهم على حق!

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

مفهوم

التعقيد الزمني للخوارزمية يُستخدم لمعرفة المدة التي ستستغرقها الخوارزمية لإكمال كمية معينة من البيانات. لوصف هذا التعقيد، نستخدم الترميز الرياضي الكبير O. يتم استخدام هذا الترميز مع دالة تصف عدد العمليات التي تحتاجها الخوارزمية لعدد معين من المدخلات.

على سبيل المثال، عندما أقول "هذه الخوارزمية لها تعقيد O(some_function())"، فهذا يعني أن الخوارزمية تتطلب عمليات some_function(a_certain_amount_of_data) لمعالجة كمية معينة من البيانات.

في هذه الحالة، ليست كمية البيانات هي التي تهم**، خلاف ذلك ** كيف يزداد عدد العمليات مع زيادة حجم البيانات. لا يوفر تعقيد الوقت عددًا محددًا من العمليات، ولكنه طريقة جيدة لتقدير وقت التنفيذ.

في هذا الرسم البياني يمكنك رؤية عدد العمليات مقابل كمية البيانات المدخلة لأنواع مختلفة من التعقيدات الزمنية للخوارزمية. لقد استخدمت مقياسًا لوغاريتميًا لعرضها. بمعنى آخر، تزداد كمية البيانات بسرعة من 1 إلى 1 مليار، ويمكننا أن نرى ما يلي:

O(1) أو التعقيد الثابت يظل ثابتًا (وإلا فلن يسمى التعقيد الثابت).
O(سجل(n)) يظل منخفضًا حتى مع وجود مليارات البيانات.
أصعب صعوبة - O(n2)، حيث يتزايد عدد العمليات بسرعة.
وتزداد المضاعفات الأخرى بنفس السرعة.

أمثلة

مع وجود كمية صغيرة من البيانات، فإن الفرق بين O(1) وO(n2) لا يكاد يذكر. على سبيل المثال، لنفترض أن لديك خوارزمية تحتاج إلى معالجة 2000 عنصر.

ستكلفك خوارزمية O(1) عملية واحدة
ستكلفك خوارزمية O(log(n)) 7 عمليات
ستكلفك خوارزمية O(n) 2 عملية
ستكلفك خوارزمية O(n*log(n)) 14 عملية
ستكلفك خوارزمية O(n2) 4 عملية

يبدو الفرق بين O(1) وO(n2) كبيرًا (4 ملايين عملية) ولكنك ستفقد 2 مللي ثانية كحد أقصى، وهو الوقت المناسب لترمش عينيك. في الواقع، يمكن للمعالجات الحديثة معالجة مئات الملايين من العمليات في الثانية الواحدة. ولهذا السبب لا يمثل الأداء والتحسين مشكلة في العديد من مشاريع تكنولوجيا المعلومات.

وكما قلت، لا يزال من المهم معرفة هذا المفهوم عند التعامل مع كميات هائلة من البيانات. إذا كان على الخوارزمية هذه المرة معالجة 1 عنصر (وهذا ليس كثيرًا بالنسبة لقاعدة البيانات):

ستكلفك خوارزمية O(1) عملية واحدة
ستكلفك خوارزمية O(log(n)) 14 عمليات
ستكلفك خوارزمية O(n) 1 عملية
ستكلفك خوارزمية O(n*log(n)) 14 عملية
ستكلفك خوارزمية O(n2) 1 عملية

لم أقم بإجراء العمليات الحسابية، ولكن أود أن أقول أنه باستخدام خوارزمية O(n2) لديك الوقت لشرب القهوة (حتى اثنين!). إذا قمت بإضافة 0 آخر إلى حجم البيانات، سيكون لديك الوقت لأخذ قيلولة.

دعونا نذهب أعمق

لمعلوماتك:

يؤدي البحث الجيد في جدول التجزئة إلى العثور على عنصر في O(1).
يؤدي البحث عن شجرة متوازنة بشكل جيد إلى الحصول على نتائج في O(log(n)).
البحث في مصفوفة ينتج عنه نتائج في O(n).
أفضل خوارزميات الفرز لها تعقيد O(n*log(n)).
خوارزمية الفرز السيئة لها تعقيد O(n2).

ملاحظة: في الأجزاء التالية سنرى هذه الخوارزميات وهياكل البيانات.

هناك عدة أنواع من التعقيد الزمني للخوارزمية:

سيناريو الحالة المتوسطة
أفضل سيناريو
والسيناريو الأسوأ

غالبًا ما يكون التعقيد الزمني هو السيناريو الأسوأ.

كنت أتحدث فقط عن التعقيد الزمني للخوارزمية، ولكن التعقيد ينطبق أيضًا على:

استهلاك الذاكرة للخوارزمية
خوارزمية استهلاك الإدخال/الإخراج للقرص

وبطبيعة الحال، هناك مضاعفات أسوأ من n2، على سبيل المثال:

n4: هذا فظيع! بعض الخوارزميات المذكورة لديها هذا التعقيد.
3ن: وهذا أسوأ! إحدى الخوارزميات التي سنراها في منتصف هذه المقالة لديها هذا التعقيد (وهي مستخدمة بالفعل في العديد من قواعد البيانات).
المضروب n: لن تحصل أبدًا على نتائجك حتى مع وجود كمية صغيرة من البيانات.
ن: إذا واجهت هذا التعقيد، عليك أن تسأل نفسك إذا كان هذا هو مجال نشاطك بالفعل...

ملحوظة: لم أعطيك التعريف الفعلي للتسمية الكبيرة، مجرد فكرة. يمكنك قراءة هذا المقال على ويكيبيديا للتعريف الحقيقي (المقارب).

ترتيب الدمج

ماذا تفعل عندما تحتاج إلى فرز مجموعة؟ ماذا؟ يمكنك استدعاء وظيفة النوع ()... حسنًا، إجابة جيدة... ولكن بالنسبة لقاعدة البيانات، يجب أن تفهم كيف تعمل وظيفة الفرز () هذه.

هناك العديد من خوارزميات الفرز الجيدة، لذا سأركز على أهمها: دمج النوع. قد لا تفهم سبب أهمية فرز البيانات في الوقت الحالي، ولكن يجب عليك ذلك بعد جزء تحسين الاستعلام. علاوة على ذلك، فإن فهم نوع الدمج سيساعدنا لاحقًا على فهم عملية الانضمام إلى قاعدة البيانات المشتركة التي تسمى دمج الانضمام (جمعية الاندماج).

دمج

مثل العديد من الخوارزميات المفيدة، يعتمد فرز الدمج على خدعة: دمج مصفوفتين مفروزتين بحجم N/2 في مصفوفة مفروزة بعنصر N يكلف N عمليات فقط. هذه العملية تسمى الدمج.

دعونا نرى ما يعنيه هذا بمثال بسيط:

يوضح هذا الشكل أنه لبناء المصفوفة النهائية المكونة من 8 عناصر، ما عليك سوى التكرار مرة واحدة على المصفوفتين المكونتين من 2 عناصر. نظرًا لأن المصفوفتين المكونتين من 4 عناصر قد تم فرزهما بالفعل:

1) تقوم بمقارنة العناصر الحالية في صفيفين (في البداية الحالية = الأول)
2) ثم خذ الأصغر لوضعه في مصفوفة مكونة من 8 عناصر
3) وانتقل إلى العنصر التالي في المصفوفة حيث أخذت العنصر الأصغر
وكرر 1,2,3،XNUMX،XNUMX حتى تصل إلى العنصر الأخير في إحدى المصفوفات.
ثم تأخذ العناصر المتبقية من المصفوفة الأخرى لوضعها في مصفوفة مكونة من 8 عناصر.

يعمل هذا لأنه تم فرز المصفوفتين المكونتين من 4 عناصر وبالتالي لا يتعين عليك "الرجوع" في تلك المصفوفات.

الآن بعد أن فهمنا الخدعة، إليك الكود الزائف الخاص بي للدمج:

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;

يقوم فرز الدمج بتقسيم المشكلة إلى مشكلات أصغر ثم العثور على نتائج المشكلات الأصغر للحصول على نتيجة المشكلة الأصلية (ملاحظة: هذا النوع من الخوارزميات يسمى فرق تسد). إذا كنت لا تفهم هذه الخوارزمية، فلا تقلق؛ لم أفهم ذلك في المرة الأولى التي رأيتها فيها. إذا كان بإمكانها مساعدتك، فأنا أرى هذه الخوارزمية كخوارزمية ذات مرحلتين:

مرحلة التقسيم، حيث يتم تقسيم المصفوفة إلى مصفوفات أصغر
مرحلة الفرز هي حيث يتم دمج المصفوفات الصغيرة (باستخدام الاتحاد) لتشكيل مصفوفة أكبر.

مرحلة التقسيم

في مرحلة التقسيم، يتم تقسيم المصفوفة إلى مصفوفات أحادية في 3 خطوات. العدد الرسمي للخطوات هو log(N) (بما أن N=8، log(N) = 3).

كيف لى أن أعرف ذلك؟

أنا عبقرى! في كلمة واحدة - الرياضيات. الفكرة هي أن كل خطوة تقسم حجم المصفوفة الأصلية على 2. عدد الخطوات هو عدد المرات التي يمكنك فيها تقسيم المصفوفة الأصلية إلى قسمين. هذا هو التعريف الدقيق للوغاريتم (الأساس 2).

مرحلة الفرز

في مرحلة الفرز، تبدأ بالمصفوفات الوحدوية (أحادية العنصر). خلال كل خطوة تقوم بتطبيق عمليات دمج متعددة وتكون التكلفة الإجمالية N = 8 عمليات:

في المرحلة الأولى لديك 4 عمليات دمج تكلف كل منها عمليتين
في الخطوة الثانية لديك عمليتي دمج تكلف كل منهما 2 عمليات
في الخطوة الثالثة لديك عملية دمج واحدة تكلف 1 عمليات

نظرًا لوجود خطوات السجل (N) ، التكلفة الإجمالية ن * عمليات السجل (N)..

مزايا فرز الدمج

لماذا هذه الخوارزمية قوية جدًا؟

لأن:

يمكنك تغييره لتقليل مساحة الذاكرة بحيث لا تقوم بإنشاء مصفوفات جديدة ولكن تقوم بتعديل مصفوفة الإدخال مباشرة.

ملاحظة: يسمى هذا النوع من الخوارزمية in-مكان (الفرز بدون ذاكرة إضافية).

يمكنك تغييره لاستخدام مساحة القرص وكمية صغيرة من الذاكرة في نفس الوقت دون تكبد حمل كبير للإدخال/الإخراج على القرص. تتمثل الفكرة في تحميل الأجزاء التي تتم معالجتها حاليًا في الذاكرة فقط. يعد هذا أمرًا مهمًا عندما تحتاج إلى فرز جدول متعدد الجيجابايت باستخدام مخزن مؤقت للذاكرة يبلغ سعته 100 ميجابايت فقط.

ملاحظة: يسمى هذا النوع من الخوارزمية فرز خارجي.

يمكنك تغييره ليتم تشغيله على عمليات/خيوط/خوادم متعددة.

على سبيل المثال، يعد فرز الدمج الموزع أحد المكونات الرئيسية Hadoop (وهو هيكل في البيانات الضخمة).

يمكن لهذه الخوارزمية تحويل الرصاص إلى ذهب (حقًا!).

يتم استخدام خوارزمية الفرز هذه في معظم قواعد البيانات (إن لم يكن كلها)، ولكنها ليست الوحيدة. إذا كنت تريد معرفة المزيد، يمكنك قراءة هذا عمل بحثي، والذي يناقش إيجابيات وسلبيات خوارزميات فرز قاعدة البيانات الشائعة.

المصفوفة والشجرة وجدول التجزئة

الآن بعد أن فهمنا فكرة التعقيد الزمني والفرز، يجب أن أخبركم عن 3 هياكل للبيانات. وهذا مهم لأنهم هي أساس قواعد البيانات الحديثة. وسوف أعرض هذا المفهوم أيضا فهرس قاعدة البيانات.

مجموعة

المصفوفة ثنائية الأبعاد هي أبسط بنية بيانات. يمكن اعتبار الجدول كمصفوفة. على سبيل المثال:

هذا المصفوفة ثنائية الأبعاد عبارة عن جدول يحتوي على صفوف وأعمدة:

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

يعد هذا مناسبًا لتخزين البيانات وتصورها، ومع ذلك، عندما تحتاج إلى العثور على قيمة معينة، فهذا غير مناسب.

على سبيل المثال، إذا كنت تريد العثور على جميع الأشخاص الذين يعملون في المملكة المتحدة، فستحتاج إلى إلقاء نظرة على كل صف لتحديد ما إذا كان هذا الصف ينتمي إلى المملكة المتحدة. سوف يكلفك N المعاملاتحيث N - عدد الخطوط، وهذا ليس سيئا، ولكن هل يمكن أن تكون هناك طريقة أسرع؟ الآن حان الوقت للتعرف على الأشجار.

ملاحظة: توفر معظم قواعد البيانات الحديثة صفائف موسعة لتخزين الجداول بكفاءة: الجداول المنظمة بالكومة والجداول المنظمة بالفهرس. لكن هذا لا يغير مشكلة العثور بسرعة على حالة معينة في مجموعة من الأعمدة.

شجرة قاعدة البيانات والفهرس

شجرة البحث الثنائية هي شجرة ثنائية ذات خاصية خاصة، ويجب أن يكون المفتاح في كل عقدة هو:

أكبر من كافة المفاتيح المخزنة في الشجرة الفرعية اليسرى
أقل من كافة المفاتيح المخزنة في الشجرة الفرعية اليمنى

دعونا نرى ما يعنيه هذا بصريا

فكرة

تحتوي هذه الشجرة على 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، العقدة موجودة. أقوم باسترداد معرف الصف داخل العقدة (غير موضح في الصورة) وأبحث في الجدول عن معرف الصف المحدد.
تتيح لي معرفة معرف الصف معرفة مكان وجود البيانات في الجدول بالضبط، حتى أتمكن من استردادها على الفور.

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

دعونا نعود إلى مشكلتنا

ولكن هذا مجرد للغاية، لذلك دعونا نعود إلى مشكلتنا. بدلاً من عدد صحيح بسيط، تخيل سلسلة تمثل بلد شخص ما في الجدول السابق. لنفترض أن لديك شجرة تحتوي على حقل "البلد" (العمود 3) من الجدول:

إذا كنت تريد أن تعرف من يعمل في المملكة المتحدة
تنظر إلى الشجرة لتحصل على العقدة التي تمثل بريطانيا العظمى
ستجد داخل "UKnode" موقع سجلات العمال في المملكة المتحدة.

سيكلف هذا البحث عمليات السجل (N) بدلاً من العمليات N إذا كنت تستخدم المصفوفة مباشرة. ما قدمته للتو كان فهرس قاعدة البيانات.

يمكنك إنشاء شجرة فهرس لأي مجموعة من الحقول (سلسلة، رقم، سطرين، رقم وسلسلة، تاريخ...) طالما أن لديك وظيفة لمقارنة المفاتيح (أي مجموعات الحقول) حتى تتمكن من ضبطها الترتيب بين المفاتيح (وهذا هو الحال بالنسبة لأي أنواع أساسية في قاعدة البيانات).

B+TreeIndex

في حين أن هذه الشجرة تعمل بشكل جيد للحصول على قيمة محددة، إلا أن هناك مشكلة كبيرة عندما تحتاج إليها الحصول على عناصر متعددة بين قيمتين. سيكلف هذا O(N) لأنه سيتعين عليك إلقاء نظرة على كل عقدة في الشجرة والتحقق مما إذا كانت بين هاتين القيمتين (على سبيل المثال، مع اجتياز الشجرة المرتب). علاوة على ذلك، فإن هذه العملية ليست مناسبة للإدخال/الإخراج على القرص حيث يتعين عليك قراءة الشجرة بأكملها. نحن بحاجة إلى إيجاد طريقة للتنفيذ بكفاءة طلب النطاق. لحل هذه المشكلة، تستخدم قواعد البيانات الحديثة نسخة معدلة من الشجرة السابقة تسمى B+Tree. في شجرة B+Tree:

فقط العقد الأدنى (الأوراق) معلومات المتجر (موقع الصفوف في الجدول ذي الصلة)
بقية العقد هنا للتوجيه إلى العقدة الصحيحة أثناء البحث.

كما ترون، هناك المزيد من العقد هنا (مرتين). في الواقع، لديك عقد إضافية، "عقد القرار"، التي ستساعدك في العثور على العقدة الصحيحة (التي تخزن موقع الصفوف في الجدول المرتبط). لكن تعقيد البحث لا يزال O(log(N)) (لا يوجد سوى مستوى واحد آخر). الفرق الكبير هو ذلك ترتبط العقد في المستوى الأدنى بخلفائها.

مع B+Tree، إذا كنت تبحث عن قيم بين 40 و100:

كل ما عليك فعله هو البحث عن 40 (أو أقرب قيمة بعد 40 إذا لم يكن 40 موجودًا) كما فعلت مع الشجرة السابقة.
ثم اجمع 40 ورثة باستخدام روابط الورثة المباشرة حتى تصل إلى 100.

لنفترض أنك عثرت على خلفاء M وأن الشجرة بها عقد N. العثور على سجل تكاليف عقدة معينة (N) مثل الشجرة السابقة. ولكن بمجرد حصولك على هذه العقدة، سوف تحصل على خلفاء M في عمليات M مع الإشارة إلى خلفائهم. لا يكلف هذا البحث سوى M+log(N) العمليات مقارنة بعمليات N على الشجرة السابقة. علاوة على ذلك، ليس عليك قراءة الشجرة الكاملة (عقد M+log(N) فقط)، مما يعني استخدامًا أقل للقرص. إذا كانت M صغيرة (على سبيل المثال 200 صف) وN كبيرة (1 صف)، فسيكون هناك فرق كبير.

ولكن هناك مشاكل جديدة هنا (مرة أخرى!). إذا قمت بإضافة أو حذف صف في قاعدة البيانات (وبالتالي في فهرس B+Tree المرتبط):

يجب عليك الحفاظ على الترتيب بين العقد داخل شجرة B+، وإلا فلن تتمكن من العثور على العقد داخل شجرة غير مصنفة.
يجب عليك الاحتفاظ بأقل عدد ممكن من المستويات في B+Tree، وإلا فإن التعقيد الزمني O(log(N)) يصبح O(N).

بمعنى آخر، يجب أن تكون B+Tree ذاتية الترتيب ومتوازنة. لحسن الحظ، هذا ممكن من خلال عمليات الحذف والإدراج الذكية. ولكن هذا يأتي بتكلفة: تكلفة عمليات الإدراج والحذف في شجرة B+ هي O(log(N)). ولهذا السبب سمع البعض منكم ذلك إن استخدام عدد كبير جدًا من الفهارس ليس فكرة جيدة. حقًا، أنت تبطئ عملية الإدراج/التحديث/الحذف السريع لصف في الجدوللأن قاعدة البيانات تحتاج إلى تحديث فهارس الجدول باستخدام عملية O(log(N)) باهظة الثمن لكل فهرس. علاوة على ذلك، فإن إضافة الفهارس يعني المزيد من عبء العمل مدير المعاملات (سيتم وصفه في نهاية المقال).

لمزيد من التفاصيل، يمكنك الاطلاع على مقالة ويكيبيديا على B+شجرة. إذا كنت تريد مثالاً لتطبيق B+Tree في قاعدة بيانات، فألق نظرة هذا المقال и هذا المقال من أحد مطوري MySQL الرائدين. يركز كلاهما على كيفية تعامل InnoDB (محرك MySQL) مع الفهارس.

ملحوظة: أخبرني أحد القراء أنه بسبب التحسينات ذات المستوى المنخفض، يجب أن تكون شجرة B+ متوازنة تمامًا.

جدول التجزئة

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

جدول التجزئة عبارة عن بنية بيانات تعثر بسرعة على العنصر من خلال مفتاحه. لبناء جدول التجزئة تحتاج إلى تحديد:

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

مثال بسيط

ولنأخذ مثالا واضحا:

يحتوي جدول التجزئة هذا على 10 قطاعات. لأنني كسول، تصورت 5 أجزاء فقط، لكنني أعلم أنك ذكي، لذا سأدعك تتخيل الخمسة الآخرين بنفسك. لقد استخدمت وظيفة التجزئة modulo 5 من المفتاح. بمعنى آخر، أقوم بتخزين الرقم الأخير فقط من مفتاح العنصر للعثور على الجزء الخاص به:

إذا كان الرقم الأخير هو 0، يقع العنصر في الجزء 0،
إذا كان الرقم الأخير هو 1، يقع العنصر في الجزء 1،
إذا كان الرقم الأخير هو 2، يقع العنصر في المنطقة 2،
...

وظيفة المقارنة التي استخدمتها هي ببساطة المساواة بين عددين صحيحين.

لنفترض أنك تريد الحصول على العنصر 78:

يحسب جدول التجزئة رمز التجزئة لـ 78، وهو 8.
ينظر جدول التجزئة إلى الجزء 8، والعنصر الأول الذي يجده هو 78.
إنها تعيد البند 78 إليك
البحث يكلف عمليتين فقط (واحد لحساب قيمة التجزئة والآخر للبحث عن العنصر داخل المقطع).

لنفترض الآن أنك تريد الحصول على العنصر 59:

يحسب جدول التجزئة رمز التجزئة لـ 59، وهو 9.
يبحث جدول التجزئة في الجزء 9، العنصر الأول الذي تم العثور عليه هو 99. بما أن 99!=59، فإن العنصر 99 ليس عنصرًا صالحًا.
وبنفس المنطق يتم أخذ العنصر الثاني (9) والثالث (79) ... والأخير (29).
لم يتم العثور على العنصر.
تكلفة البحث 7 عمليات.

وظيفة تجزئة جيدة

كما ترون، اعتمادًا على القيمة التي تبحث عنها، فإن التكلفة ليست هي نفسها!

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

في المثال الخاص بي، من السهل العثور على دالة تجزئة جيدة. ولكن هذا مثال بسيط، العثور على دالة تجزئة جيدة يكون أكثر صعوبة عندما يكون المفتاح هو:

سلسلة (على سبيل المثال - الاسم الأخير)
سطرين (على سبيل المثال - الاسم الأخير والاسم الأول)
سطرين وتاريخ (على سبيل المثال - الاسم الأخير والاسم الأول وتاريخ الميلاد)
...

باستخدام دالة تجزئة جيدة، تكلف عمليات البحث في جدول التجزئة O(1).

صفيف مقابل جدول التجزئة

لماذا لا تستخدم مصفوفة؟

حسنًا، سؤال جيد.

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

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

المصدر: www.habr.com

كيف تعمل قواعد البيانات العلائقية (الجزء الأول)