شجرة ب في بنية البيانات: البحث والإدراج والحذف Operaمثال

قواعد شجرة B

فيما يلي قواعد مهمة لإنشاء B_Tree

• سيتم إنشاء جميع الأوراق على نفس المستوى.
• يتم تحديد B-Tree بعدد من الدرجات، وهو ما يسمى أيضًا “النظام” (يتم تحديده بواسطة فاعل خارجي، مثل المبرمج)، ويشار إليه باسم

  m

  فصاعدا. قيمة ال

  m

  يعتمد على حجم الكتلة الموجودة على القرص الذي توجد عليه البيانات بشكل أساسي.

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

  m – 1

  فمثلا:

  m = 4
  max keys: 4 – 1 = 3
  

• يجب أن تحتوي كل عقدة، باستثناء الجذر، على الحد الأدنى من المفاتيح

  [m/2]-1

  فمثلا:

  m = 4
  min keys: 4/2-1 = 1
  

• الحد الأقصى لعدد العقد الفرعية التي يمكن أن تحتوي عليها العقدة يساوي درجتها، وهي

  m

• الحد الأدنى للأطفال الذي يمكن أن تحتوي عليه العقدة هو نصف الترتيب، وهو m/2 (يتم أخذ قيمة السقف).
• يتم فرز جميع المفاتيح الموجودة في العقدة بترتيب متزايد.

لماذا نستخدم شجرة بي

فيما يلي أسباب استخدام B-Tree

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

تاريخ شجرة B

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

بحث Operaالإنتاج

عملية البحث هي أبسط عملية على شجرة B.

يتم تطبيق الخوارزمية التالية:

• دع المفتاح (القيمة) يتم البحث عنه بواسطة "k".
• ابدأ البحث من الجذر وانتقل إلى الأسفل بشكل متكرر.
• إذا كانت k أقل من قيمة الجذر، فابحث في الشجرة الفرعية اليسرى، وإذا كانت k أكبر من قيمة الجذر، فابحث في الشجرة الفرعية اليمنى.
• إذا كانت العقدة تحتوي على k الذي تم العثور عليه، فما عليك سوى إرجاع العقدة.
• إذا لم يتم العثور على k في العقدة، فانتقل إلى الطفل باستخدام مفتاح أكبر.
• إذا لم يتم العثور على k في الشجرة، فإننا نعيد NULL.

إدراج Operaالإنتاج

نظرًا لأن B Tree عبارة عن شجرة ذاتية التوازن، فلا يمكنك فرض إدخال مفتاح في أي عقدة فقط.

يتم تطبيق الخوارزمية التالية:

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

TIP	ما يلي ليس صحيحًا فيما يتعلق بخوارزمية الإدراج: نظرًا لأن العقدة ممتلئة، فسيتم تقسيمها، ومن ثم سيتم إدراج قيمة جديدة

في المثال أعلاه:

• ابحث في الموضع المناسب في العقدة عن المفتاح
• أدخل المفتاح في العقدة المستهدفة، وتحقق من القواعد
• بعد الإدراج، هل تحتوي العقدة على أكثر من الحد الأدنى لعدد المفاتيح، وهو 1؟ في هذه الحالة، نعم، يحدث ذلك. تحقق من القاعدة التالية.
• بعد الإدراج، هل تحتوي العقدة على أكثر من الحد الأقصى لعدد المفاتيح، وهو 3؟ في هذه الحالة، لا، لا يحدث ذلك. وهذا يعني أن الشجرة B لا تنتهك أي قواعد، وأن عملية الإدراج قد اكتملت.

في المثال أعلاه:

• وصلت العقدة إلى الحد الأقصى لعدد المفاتيح
• سيتم تقسيم العقدة، وسيصبح المفتاح الأوسط هو العقدة الجذرية للعقدتين المتبقيتين.
• في حالة وجود عدد زوجي من المفاتيح، سيتم اختيار العقدة الوسطى عن طريق الانحياز الأيسر أو الانحياز الأيمن.

في المثال أعلاه:

• تحتوي العقدة على أقل من الحد الأقصى للمفاتيح
• تم إدراج الرقم 1 بجوار الرقم 3، ولكن تم انتهاك قاعدة الترتيب التصاعدي
• من أجل إصلاح هذا، يتم فرز المفاتيح

وبالمثل، يمكن إدراج 13 و 2 بسهولة في العقدة لأنها تلبي قاعدة مفاتيح أقل من الحد الأقصى للعقد.

في المثال أعلاه:

• تحتوي العقدة على مفاتيح تساوي الحد الأقصى للمفاتيح.
• يتم إدخال المفتاح إلى العقدة المستهدفة، لكنه ينتهك قاعدة الحد الأقصى للمفاتيح.
• تم تقسيم العقدة المستهدفة، وأصبح المفتاح الأوسط بالانحياز الأيسر الآن هو الأصل للعقد الفرعية الجديدة.
• يتم ترتيب العقد الجديدة بترتيب تصاعدي.

وبالمثل، واستنادًا إلى القواعد والحالات المذكورة أعلاه، يمكن إدراج بقية القيم بسهولة في الشجرة B.

حذف Operaالإنتاج

تحتوي عملية الحذف على قواعد أكثر من عمليات الإدراج والبحث.

يتم تطبيق الخوارزمية التالية:

• قم بتشغيل عملية البحث وابحث عن المفتاح المستهدف في العقد
• يتم تطبيق ثلاثة شروط بناءً على موقع المفتاح المستهدف، كما هو موضح في الأقسام التالية

إذا كان المفتاح الهدف موجودًا في العقدة الطرفية

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

إذا كان المفتاح الهدف موجودًا في عقدة داخلية

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

إذا كان المفتاح الهدف موجودًا في العقدة الجذرية

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

الآن، دعونا نفهم عملية الحذف بمثال.

يعرض الرسم البياني أعلاه حالات مختلفة لعملية الحذف في شجرة B. هذه الشجرة من الدرجة 5، مما يعني أن الحد الأدنى لعدد العقد الفرعية التي يمكن لأي عقدة أن تمتلكها هو 3، والحد الأقصى لعدد العقد الفرعية التي يمكن لأي عقدة أن تمتلكها هو 5. في حين أن الحد الأدنى والحد الأقصى لعدد المفاتيح التي يمكن لأي عقدة أن تمتلكها هو 2 و4 على التوالي.

في المثال أعلاه:

• تحتوي العقدة المستهدفة على مفتاح الهدف المراد حذفه
• تحتوي العقدة المستهدفة على مفاتيح أكثر من الحد الأدنى من المفاتيح
• ببساطة قم بحذف المفتاح

في المثال أعلاه:

• تحتوي العقدة المستهدفة على مفاتيح تساوي الحد الأدنى من المفاتيح، لذا لا يمكن حذفها مباشرة لأنها ستخالف الشروط

الآن، يوضح الرسم التخطيطي التالي كيفية حذف هذا المفتاح:

• سوف تستعير العقدة المستهدفة مفتاحًا من الأخ المباشر، في هذه الحالة، السلف بالترتيب (الأخ الأيسر) لأنه لا يوجد لديه أي خليفة بالترتيب (الأخ الأيمن)
• سيتم نقل الحد الأقصى لقيمة الترتيب السابق إلى العقدة الأم، وسيقوم الأصل بنقل القيمة القصوى إلى العقدة المستهدفة (انظر الرسم البياني أدناه)

يوضح المثال التالي كيفية حذف مفتاح يحتاج إلى قيمة من خليفته بالترتيب.

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

في المثال أدناه، ليس للعقدة المستهدفة أي شقيق يمكنه إعطاء مفتاحها للعقدة المستهدفة. لذلك، الدمج مطلوب.

راجع إجراء حذف هذا المفتاح:

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

حذف Operaالكود الزائف

private int removeBiggestElement()
{
    if (root has no child)
        remove and return the last element
    else {
        answer = subset[childCount-1].removeBiggestElement()
        if (subset[childCount-1].dataCount < MINIMUM)
            fixShort (childCount-1)
        return answer
    }
}

الناتج:

يتم حذف العنصر الأكبر من B-Tree.

الملخص

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