B+ Tree هو امتداد لـ B Tree الذي يسمح بعمليات الإدراج والحذف والبحث الفعالة.
في B Tree، يمكن تخزين المفاتيح والسجلات في العقد الداخلية وكذلك في العقد الطرفية. حيث أنه في شجرة B+، لا يمكن تخزين السجلات (البيانات) إلا على العقد الطرفية بينما يمكن للعقد الداخلية تخزين القيم الأساسية فقط.
جافا إذا بيان آخر
يتم ربط العقد الورقية لشجرة B+ معًا في شكل قوائم مرتبطة بشكل فردي لجعل استعلامات البحث أكثر كفاءة.
تُستخدم شجرة B+ لتخزين كمية كبيرة من البيانات التي لا يمكن تخزينها في الذاكرة الرئيسية. نظرًا لحقيقة أن حجم الذاكرة الرئيسية يكون دائمًا محدودًا، يتم تخزين العقد الداخلية (مفاتيح الوصول إلى السجلات) لشجرة B+ في الذاكرة الرئيسية بينما يتم تخزين العقد الورقية في الذاكرة الثانوية.
غالبًا ما تسمى العقد الداخلية لشجرة B+ بعقد الفهرس. تظهر في الشكل التالي شجرة B+ من الرتبة 3.
مزايا شجرة B+
- يمكن جلب السجلات بعدد متساو من مرات الوصول إلى القرص.
- يبقى ارتفاع الشجرة متوازنا وأقل مقارنة بالشجرة B.
- يمكننا الوصول إلى البيانات المخزنة في شجرة B+ بشكل تسلسلي ومباشر.
- يتم استخدام المفاتيح للفهرسة.
- استعلامات بحث أسرع حيث يتم تخزين البيانات فقط على العقد الطرفية.
شجرة B مقابل شجرة B +
| SN | شجرة ب | ب + شجرة |
|---|---|---|
| 1 | لا يمكن تخزين مفاتيح البحث بشكل متكرر. | يمكن أن تكون مفاتيح البحث الزائدة موجودة. |
| 2 | يمكن تخزين البيانات في العقد الورقية وكذلك العقد الداخلية | لا يمكن تخزين البيانات إلا على العقد الورقية. |
| 3 | يعد البحث عن بعض البيانات عملية أبطأ حيث يمكن العثور على البيانات على العقد الداخلية وكذلك على العقد الطرفية. | يعد البحث أسرع نسبيًا حيث لا يمكن العثور على البيانات إلا في العقد الطرفية. |
| 4 | يعد حذف العقد الداخلية أمرًا معقدًا للغاية ويستغرق وقتًا طويلاً. | لن يكون الحذف عملية معقدة أبدًا حيث سيتم دائمًا حذف العنصر من العقد الطرفية. |
| 5 | لا يمكن ربط العقد الورقية معًا. | ترتبط العقد الورقية معًا لجعل عمليات البحث أكثر كفاءة. |
الإدراج في شجرة B+
الخطوة 1: أدخل العقدة الجديدة كعقدة طرفية
الخطوة 2: إذا لم تكن الورقة تحتوي على المساحة المطلوبة، فقم بتقسيم العقدة ونسخ العقدة الوسطى إلى عقدة الفهرس التالية.
الخطوه 3: إذا لم تكن عقدة الفهرس تحتوي على المساحة المطلوبة، فقم بتقسيم العقدة ونسخ العنصر الأوسط إلى صفحة الفهرس التالية.
مثال :
أدخل القيمة 195 في شجرة B+ من الرتبة 5 الموضحة في الشكل التالي.
سيتم إدراج 195 في الشجرة الفرعية اليمنى 120 بعد 190. أدخلها في الموضع المطلوب.
تحتوي العقدة على أكبر من الحد الأقصى لعدد العناصر، أي 4، لذلك قم بتقسيمها ووضع العقدة المتوسطة حتى الأصل.
تحميل شبيبة
الآن، تحتوي عقدة الفهرس على 6 أبناء و5 مفاتيح مما ينتهك خصائص شجرة B+، لذلك نحتاج إلى تقسيمها، كما هو موضح كما يلي.
الحذف في شجرة B+
الخطوة 1: احذف المفتاح والبيانات من الأوراق.
الخطوة 2: إذا كانت العقدة الطرفية تحتوي على أقل من الحد الأدنى لعدد العناصر، فقم بدمج العقدة مع العقدة الشقيقة لها وحذف المفتاح الموجود بينهما.
الخطوه 3: إذا كانت عقدة الفهرس تحتوي على أقل من الحد الأدنى لعدد العناصر، فقم بدمج العقدة مع العقدة الشقيقة وحرك المفتاح بينهما لأسفل.
مثال
احذف المفتاح 200 من شجرة B+ الموضحة في الشكل التالي.
200 موجود في الشجرة الفرعية اليمنى 190، بعد 195. احذفه.
دمج العقدتين باستخدام 195، 190، 154 و 129.
الآن، العنصر 120 هو العنصر الوحيد الموجود في العقدة والذي ينتهك خصائص شجرة B+. ولذلك، نحن بحاجة إلى دمجها باستخدام 60، 78، 108 و 120.
الآن، سيتم تقليل ارتفاع الشجرة B+ بمقدار 1.
