في البرنامج التعليمي التالي، سوف نتعرف على بنية بيانات B Tree ونفكر في تصورها.
اذا هيا بنا نبدأ.
ما هي الشجرة ب؟
ال شجرة ب هو نوع خاص من شجرة البحث متعددة الاتجاهات ، والمعروف باسم م-الطريق الشجرة التي توازن نفسها. بسبب بنيتها المتوازنة، تُستخدم هذه الأشجار بشكل شائع لتشغيل وإدارة قواعد البيانات الضخمة وتبسيط عمليات البحث. في شجرة B، يمكن أن تحتوي كل عقدة على عدد n من العقد الفرعية على الأكثر. تعد B Tree مثالاً على الفهرسة متعددة المستويات في نظام إدارة قواعد البيانات (DBMS). سيكون لكل من العقد الورقية والداخلية مراجع سجل. تُعرف الشجرة B بالشجرة المخزنة المتوازنة لأن جميع العقد الورقية تقع على نفس المستوى.
الرسم البياني التالي هو مثال على شجرة B:
شكل 1. شجرة A B مع الطلب 3
فهم قواعد الشجرة B
فيما يلي الخصائص المهمة للشجرة B:
- جميع العقد الورقية على نفس المستوى.
- يتم تعريف بنية بيانات الشجرة B بمصطلح الدرجة الدنيا 'd'. تعتمد قيمة 'd' على حجم كتلة القرص.
- يجب أن تتكون كل عقدة، باستثناء الجذر، من مفاتيح d-1 على الأقل. قد تتكون العقدة الجذرية من مفتاح واحد على الأقل.
- يمكن أن تتكون جميع العقد (بما في ذلك العقدة الجذرية) على الأكثر (2d-1) مفاتيح.
- عدد أبناء العقدة يساوي إضافة عدد المفاتيح الموجودة فيه و .
- يتم فرز جميع مفاتيح العقدة بترتيب تصاعدي. يتكون الطفل الموجود بين مفتاحين، k1 وk2، من جميع المفاتيح التي تتراوح بين k1 وk2، على التوالي.
- على عكس شجرة البحث الثنائية، تنمو بنية بيانات الشجرة B وتتقلص من الجذر. في حين أن شجرة البحث الثنائية تنمو للأسفل وتتقلص للأسفل.
- على غرار أشجار البحث الثنائية ذاتية التوازن الأخرى، فإن التعقيد الزمني لبنية بيانات شجرة B لعمليات مثل البحث والإدراج والحذف هو يا (سجل؟ ن) .
- يتم إدخال عقدة في الشجرة B فقط عند العقدة الورقية.
دعونا نفكر في المثال التالي لشجرة B ذات الحد الأدنى للطلب 5.
الشكل 2. أ ب شجرة الترتيب 5
ملحوظة: قيمة الحد الأدنى للطلب أكبر بكثير من 5 في شجرة B العملية.
في الرسم البياني أعلاه، يمكننا ملاحظة أن جميع العقد الورقية على نفس المستوى، وجميع العقد غير الورقية لا تحتوي على شجرة فرعية فارغة وتتكون من مفاتيح أقل من عدد أبنائها بمقدار واحد.
الصياغة المحددة لقواعد الشجرة B:
تعتمد كل شجرة B على عدد صحيح ثابت موجب يعرف باسم الحد الأدنى والتي يتم استخدامها لتحديد عدد عناصر البيانات التي يمكن الاحتفاظ بها في عقدة واحدة.
المادة 1: يمكن أن يحتوي الجذر على ما لا يقل عن عنصر بيانات واحد فقط (أو حتى لا يحتوي على عناصر بيانات إذا لم يكن لديه عناصر فرعية أيضًا)؛ كل عقدة أخرى لديها على الأقل الحد الأدنى عناصر البيانات.
القاعدة 2: الحد الأقصى لعدد عناصر البيانات المخزنة في العقدة هو ضعف قيمتها الحد الأدنى .
القاعدة 3: يتم تخزين عناصر البيانات لكل عقدة من شجرة B في مصفوفة مملوءة جزئيًا، مرتبة من أصغر عنصر بيانات (في الفهرس 0 ) إلى أكبر عنصر بيانات (في الموضع النهائي المستخدم للمصفوفة).
تحويل عدد صحيح إلى سلسلة جافا
القاعدة 4: دائمًا ما يكون إجمالي عدد الأشجار الفرعية الموجودة أسفل العقدة غير الورقية أكثر بواحد من عدد عناصر البيانات في تلك العقدة.
- الشجرة الفرعية 0، الشجرة الفرعية 1،...
القاعدة 5: فيما يتعلق بأي عقدة غير ورقية:
- عنصر البيانات في الفهرس أكبر من جميع عناصر البيانات في رقم الشجرة الفرعية أنا العقدة، و
- عنصر البيانات في الفهرس أقل من جميع عناصر البيانات في رقم الشجرة الفرعية أنا+1 العقدة.
القاعدة 6: كل ورقة في الشجرة B لها نفس العمق. وبالتالي، فهي تضمن أن الشجرة B تمنع مشكلة الشجرة غير المتوازنة.
العمليات على بنية بيانات الشجرة B
من أجل ضمان عدم انتهاك أي من خصائص بنية بيانات الشجرة B أثناء العمليات، قد يتم تقسيم شجرة B أو ضمها. فيما يلي بعض العمليات التي يمكننا تنفيذها على شجرة B:
- البحث عن عنصر بيانات في شجرة B
- إدراج عنصر بيانات في شجرة B
- حذف عنصر بيانات في B Tree
عملية البحث على شجرة B
البحث عن عنصر في شجرة B يشبه البحث في شجرة البحث الثنائية. ولكن بدلاً من اتخاذ قرار في اتجاهين (يسار أو يمين) مثل شجرة البحث الثنائية، تتخذ شجرة B قرارًا في اتجاه m عند كل عقدة حيث m هو عدد أبناء العقدة.
خطوات البحث عن عنصر بيانات في شجرة B:
الخطوة 1: يبدأ البحث من العقدة الجذرية. قارن عنصر البحث k بالجذر.
الخطوة 1.1: إذا كانت العقدة الجذرية تتكون من العنصر k، فسيتم إكمال البحث.
الخطوة 1.2: إذا كان العنصر k أقل من القيمة الأولى في الجذر، فسننتقل إلى أقصى اليسار ونبحث عن الطفل بشكل متكرر.
الخطوة 1.3.1: إذا كان الجذر يحتوي على طفلين فقط، فسننتقل إلى الطفل الموجود في أقصى اليمين ونبحث بشكل متكرر في العقد الفرعية.
الخطوة 1.3.2: إذا كان الجذر يحتوي على أكثر من مفتاحين، فسوف نبحث في الباقي.
الخطوة 2: إذا لم يتم العثور على العنصر k بعد اجتياز الشجرة بأكملها، فإن عنصر البحث غير موجود في الشجرة B.
دعونا نتصور الخطوات المذكورة أعلاه بمساعدة مثال. لنفترض أننا أردنا البحث عن المفتاح k=34 في شجرة B التالية:
الشكل 3.1. شجرة B معينة
- أولا، سوف نتحقق مما إذا كان المفتاح ك = 34 موجود في العقدة الجذرية. وبما أن المفتاح ليس في الجذر، فسوف ننتقل إلى العقد الفرعية الخاصة به. يمكننا أيضًا أن نلاحظ أن العقدة الجذرية لها طفلان؛ لذلك سنقوم بمقارنة القيمة المطلوبة بين المفتاحين.
الشكل 3.2. المفتاح k غير موجود في الجذر - الآن بعد أن لاحظنا أن المفتاح k أكبر من العقدة الجذرية، أي 30، سننتقل إلى الابن الأيمن للجذر.
الشكل 3.3. المفتاح k> 30، انتقل إلى الطفل الأيمن - سنقوم الآن بمقارنة المفتاح k بالقيم الموجودة على العقدة، أي 40 و50 على التوالي. نظرًا لأن المفتاح k أقل من المفتاح الأيسر، أي 40، فسوف ننتقل إلى الطفل الأيسر للعقدة.
الشكل 3.4. المفتاح ك<40, move to left child< li> - وبما أن القيمة الموجودة في الطفل الأيسر 40 هي 34، وهي القيمة المطلوبة، يمكننا أن نستنتج أنه تم العثور على المفتاح، واكتملت عملية البحث.
الشكل 3.4. المفتاح k = 34، الابن الأيسر لـ 40
قمنا بمقارنة المفتاح بأربع قيم مختلفة في المثال أعلاه حتى وجدناه. وبالتالي، فإن التعقيد الزمني المطلوب لعملية البحث في شجرة B هو يا (سجل؟ ن) .
إدراج العملية على شجرة B
أثناء إدراج عنصر بيانات في شجرة B، يجب علينا أولاً التحقق مما إذا كان هذا العنصر موجودًا بالفعل في الشجرة أم لا. إذا تم العثور على عنصر البيانات داخل الشجرة B، فلن تتم عملية الإدراج. ومع ذلك، إذا لم يكن الأمر كذلك، فسنواصل عملية الإدراج. هناك سيناريوهان يجب الاهتمام بهما أثناء إدراج عنصر في العقدة الطرفية:
خطوات إدراج عنصر بيانات في شجرة B:
الخطوة 1: سنبدأ بحساب الحد الأقصى لعدد المفاتيح في العقدة على أساس ترتيب الشجرة B.
الخطوة 2: إذا كانت الشجرة فارغة، فسيتم تخصيص عقدة جذر، وسنقوم بإدخال المفتاح الذي يعمل كعقدة جذر.
الخطوه 3: سنقوم الآن بالبحث في العقدة المناسبة للإدراج.
الخطوة 4: إذا كانت العقدة ممتلئة:
الخطوة 4.1: سنقوم بإدراج عناصر البيانات بترتيب تصاعدي.
الخطوة 4.2: إذا كانت عناصر البيانات أكبر من الحد الأقصى لعدد المفاتيح، فسنقوم بتقسيم العقدة الكاملة عند الوسيط.
الخطوة 4.3: سنقوم بدفع المفتاح المتوسط إلى أعلى وتقسيم المفتاحين الأيمن والأيسر إلى فرعين يسار ويمين.
الخطوة 5: إذا لم تكن العقدة ممتلئة، فسنقوم بإدراج العقدة بترتيب تصاعدي.
دورة حياة اس دي ال سي
دعونا نتصور الخطوات المذكورة أعلاه بمساعدة مثال. لنفترض أنه يتعين علينا إنشاء شجرة B من الترتيب 4. عناصر البيانات المطلوب إدراجها في الشجرة B هي 5،3،21،11،1،16،8،13،4، و9 .
- بما أن m يساوي 3، فإن الحد الأقصى لعدد المفاتيح للعقدة = م-1 = 3-1 = 2 .
- سنبدأ بالإدراج 5 في الشجرة الفارغة.
الشكل 4.1. الإدراج 5 - سنقوم الآن بإدراج 3 في الشجرة. وبما أن 3 أقل من 5، فسوف نقوم بإدخال 3 على يسار 5 في نفس العقدة.
الشكل 4.2. الإدراج 3 - سنقوم الآن بإدراج 21 في الشجرة، وبما أن 21 أكبر من 5، فسيتم إدراجه على يمين 5 في نفس العقدة. ومع ذلك، بما أننا نعلم أن الحد الأقصى لعدد المفاتيح في العقدة هو 2، فسيتم نقل أحد هذه المفاتيح إلى العقدة أعلاه لتقسيمها. وبالتالي، فإن 5، عنصر البيانات الأوسط، سوف يتحرك لأعلى، وسوف تصبح 3 و 21 العقدتين اليمنى واليسرى، على التوالي.
الشكل 4.3. إدراج 21 - الآن حان الوقت لإدراج عنصر البيانات التالي، أي 11، وهو أكبر من 5 ولكن أقل من 21. لذلك، سيتم إدراج 11 كمفتاح على يسار العقدة المكونة من 21 كمفتاح.
الشكل 4.4. الادراج 11 - وبالمثل، سوف نقوم بإدراج عنصر البيانات التالي 1 في الشجرة، وكما نلاحظ، 1 أقل من 3؛ لذلك سيتم إدراجه كمفتاح على يسار العقدة المكونة من 3 كمفتاح.
الشكل 4.5. الإدراج 1 - الآن، سوف نقوم بإدراج عنصر البيانات 16 في الشجرة، وهو أكبر من 11 ولكن أقل من 21. ومع ذلك، فإن عدد المفاتيح في تلك العقدة يتجاوز الحد الأقصى لعدد المفاتيح. لذلك، سيتم تقسيم العقدة، مما يؤدي إلى نقل المفتاح الأوسط إلى الجذر. وبالتالي، سيتم إدراج 16 على يمين الـ 5، وتقسيم 11 و 21 إلى عقدتين منفصلتين.
الشكل 4.6. إدراج 16 - سيتم إدراج عنصر البيانات 8 كمفتاح على يسار 11.
الشكل 4.7. الإدراج 8 - سوف نقوم بإدراج 13 في الشجرة، وهو أقل من 16 وأكبر من 11. لذلك، يجب إدراج عنصر البيانات 13 على يمين العقدة المكونة من 8 و11. ومع ذلك، نظرًا لأن الحد الأقصى لعدد المفاتيح في الشجرة يمكن إذا كان 2 فقط، فسيحدث انقسام، مما يؤدي إلى نقل عنصر البيانات الأوسط 11 إلى العقدة أعلاه و8 و13 إلى عقدتين منفصلتين. الآن، ستتكون العقدة أعلاه من 5 و11 و16، وهو ما يتجاوز الحد الأقصى لعدد المفاتيح مرة أخرى. لذلك، سيكون هناك تقسيم آخر، مما يجعل عنصر البيانات 11 هو العقدة الجذرية مع 5 و16 كأبناء له.
الشكل 4.8. الادراج 13 - نظرًا لأن عنصر البيانات 4 أقل من 5 ولكنه أكبر من 3، فسيتم إدراجه على يمين العقدة المكونة من 1 و3، مما سيتجاوز الحد الأقصى لعدد المفاتيح في العقدة مرة أخرى. لذلك، سيحدث التسرب مرة أخرى، مما يؤدي إلى نقل الرقم 3 إلى العقدة العلوية بجانب الرقم 5.
الشكل 4.9. الإدراج 4 - أخيرًا، سيتم إدراج عنصر البيانات 9، وهو أكبر من 8 ولكن أقل من 11، على يمين العقدة المكونة من 8 كمفتاح.
الشكل 4.10. الادراج 9
في المثال أعلاه، أجرينا مقارنات مختلفة. تم إدراج القيمة الأولى مباشرة في الشجرة؛ بعد ذلك، كان لا بد من مقارنة كل قيمة مع العقد المتوفرة في تلك الشجرة. يعتمد التعقيد الزمني لعملية الإدراج في شجرة B على عدد العقد و.
حذف العملية على شجرة B
يحتوي حذف عنصر بيانات على شجرة B على ثلاثة أحداث أساسية:
- البحث في العقدة التي يوجد بها المفتاح المراد حذفه،
- حذف المفتاح، و
- موازنة الشجرة إذا لزم الأمر.
أثناء حذف عنصر من الشجرة، قد تحدث حالة تعرف باسم Underflow. يحدث التجاوز عندما تتكون العقدة من أقل من الحد الأدنى لعدد المفاتيح؛ يجب أن تعقد.
فيما يلي بعض المصطلحات التي يجب فهمها قبل تصور عملية الحذف/الإزالة:
فيما يلي ثلاث حالات بارزة لعملية الحذف في الشجرة B:
الحالة 1: يقع حذف/إزالة المفتاح في العقدة الورقية - وتنقسم هذه القضية أيضًا إلى حالتين مختلفتين:
1. لا ينتهك حذف/إزالة المفتاح خاصية الحد الأدنى لعدد المفاتيح التي يجب أن تحتوي عليها العقدة.
دعونا نتصور هذه الحالة باستخدام مثال حيث سنقوم بحذف المفتاح 32 من شجرة B التالية.
الشكل 4.1: حذف مفتاح العقدة الطرفية (32) من الشجرة B
وكما نلاحظ فإن حذف 32 من هذه الشجرة لا يخالف الخاصية المذكورة أعلاه.
2. إن حذف/إزالة المفتاح ينتهك خاصية الحد الأدنى لعدد المفاتيح التي يجب أن تحتوي عليها العقدة. في هذه الحالة، يجب علينا استعارة المفتاح من العقدة الشقيقة القريبة منه بالترتيب من اليسار إلى اليمين.
أولاً، سنقوم بزيارة الأخ الأيسر القريب. إذا كانت العقدة الشقيقة اليسرى تحتوي على أكثر من الحد الأدنى لعدد المفاتيح، فسوف تستعير مفتاحًا من هذه العقدة.
بخلاف ذلك، سوف نتحقق من الاقتراض من عقدة الأخوة اليمنى القريبة.
دعونا الآن نتصور هذه الحالة بمساعدة مثال حيث سنقوم بحذف 31 من شجرة B المذكورة أعلاه. سوف نستعير مفتاحًا من العقدة الشقيقة اليسرى في هذه الحالة.
الشكل 4.2: حذف مفتاح العقدة الطرفية (31) من الشجرة B
إذا كانت العقدتان الشقيقتان القريبتان تتكونان بالفعل من الحد الأدنى من عدد المفاتيح، فسنقوم بدمج العقدة إما مع العقدة الشقيقة اليسرى أو العقدة اليمنى. تتم عملية الدمج هذه من خلال العقدة الأصلية.
دعونا نتصور مرة أخرى عن طريق حذف المفتاح 30 من شجرة B المذكورة أعلاه.
مقارنة بين الأسد والنمر
الشكل 4.3: حذف مفتاح العقدة الطرفية (30) من الشجرة B
الحالة 2: يقع حذف/إزالة المفتاح في العقدة غير الورقية - وتنقسم هذه الحالة أيضًا إلى حالات مختلفة:
1. يتم استبدال العقدة غير الورقية/الداخلية، التي تمت إزالتها، بعقدة سابقة بالترتيب إذا كانت العقدة الفرعية اليسرى تحتوي على أكثر من الحد الأدنى لعدد المفاتيح.
دعونا نتصور هذه الحالة باستخدام مثال حيث سنقوم بحذف المفتاح 33 من الشجرة B.
الشكل 4.4: حذف مفتاح العقدة الطرفية (33) من الشجرة B
2. يتم استبدال العقدة غير الورقية/الداخلية، التي تمت إزالتها، بعقدة لاحقة بالترتيب إذا كانت العقدة الفرعية اليمنى تحتوي على أكثر من الحد الأدنى لعدد المفاتيح.
إذا كان لدى أي من الطفلين الحد الأدنى من عدد المفاتيح، فسنقوم بدمج العقدتين الفرعيتين اليسرى واليمنى.
دعونا نتصور هذه الحالة عن طريق حذف المفتاح 30 من شجرة B.
الشكل 4.5: حذف مفتاح العقدة الطرفية (30) من الشجرة B
بعد الدمج، إذا كانت العقدة الأصلية تحتوي على أقل من الحد الأدنى لعدد المفاتيح، فيمكن للمرء البحث عن الأشقاء، كما في حالة 1 .
الحالة 3: في الحالة التالية، يتقلص ارتفاع الشجرة. إذا كان المفتاح الهدف موجودًا في عقدة داخلية، وأدت إزالة المفتاح إلى عدد أقل من المفاتيح في العقدة (وهو أقل من الحد الأدنى المطلوب)، فابحث عن المفتاح السابق بالترتيب والخلف بالترتيب. إذا كان لدى كلا الطفلين الحد الأدنى من عدد المفاتيح، فلا يمكن أن تتم عملية الاقتراض. وهذا يؤدي إلى الحالة 2(3) ، أي دمج العقد الفرعية.
سنبحث مرة أخرى عن الأخ لاستعارة المفتاح. ومع ذلك، إذا كان الأخ أيضًا يتكون من الحد الأدنى من عدد المفاتيح، فسنقوم بدمج العقدة مع الأخ مع العقدة الأصلية وترتيب العقد الفرعية وفقًا للمتطلبات (ترتيب تصاعدي).
دعونا نتصور هذه الحالة بمساعدة مثال حيث سنقوم بحذف عنصر البيانات 10 من شجرة B المحددة.
الشكل 4.6: حذف مفتاح العقدة الطرفية (10) من الشجرة B
يختلف التعقيد الزمني في الأمثلة المذكورة أعلاه اعتمادًا على الموقع الذي يجب حذف المفتاح منه. وبالتالي، فإن التعقيد الزمني لعملية الحذف في شجرة B هو يا (سجل؟ ن) .
الإستنتاج
في هذا البرنامج التعليمي، تعرفنا على الشجرة B وتصورنا عملياتها المختلفة بأمثلة مختلفة. لقد فهمنا أيضًا بعض الخصائص والقواعد الأساسية للشجرة B.