شجرة B في بنية البيانات: البحث، الإدراج، الحذف

ما هي الشجرة ب؟

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

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

قواعد شجرة B

فيما يلي قواعد مهمة لإنشاء شجرة B:

• سيتم إنشاء جميع الأوراق على نفس المستوى.
• يتم تحديد شجرة B بواسطة عدد من الدرجات، والتي تسمى أيضًا "الترتيب" (يتم تحديدها بواسطة جهة خارجية، مثل المبرمج)، ويشار إليها باسم 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:

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

تاريخ شجرة B

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

البحث Operaالإنتاج

تُعد عملية البحث أبسط عملية على شجرة B. ويتم تطبيق الخوارزمية التالية:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

حذف Operaالإنتاج

تتضمن عملية الحذف قواعد أكثر من عمليتي الإضافة والبحث. يتم تطبيق الخوارزمية التالية:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

حذف Operation Pseudo Code

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.

الأسئلة الشائعة