مقدمة
في علم الحاسوب، شجرة بي (B-tree) هي هيكل بيانات شجرة ذاتية الموازنة تحافظ على البيانات المصنفة وتسمح بالبحث المتسلسل والإضافات والحذف في وقت لوغاريتمي. تعتبر أشجار بي تعميمًا لأشجار البحث الثنائية، حيث يمكن أن يكون لكل عقدة أكثر من طفلين. على عكس أشجار البحث الثنائية ذاتية الموازنة، تم تصميم أشجار بي لأنظمة تخزين البيانات الموجهة نحو القرص. إنها مناسبة بشكل خاص لقراءة وكتابة كتل كبيرة من البيانات (تُعرف أيضًا باسم “الصفحات”)، وتستخدم بشكل شائع في قواعد البيانات وأنظمة الملفات.
خصائص أشجار بي
تتميز أشجار بي بعدة خصائص تجعلها فعالة للغاية في إدارة كميات كبيرة من البيانات. تشمل هذه الخصائص:
- الترتيب (Order): يحدد الحد الأقصى لعدد الأطفال الذين يمكن أن تمتلكهم العقدة. غالبًا ما يتم الإشارة إلى شجرة بي من الدرجة ‘m’ على أنها شجرة بي من الرتبة m+1.
- التوازن الذاتي: تحافظ أشجار بي على التوازن، مما يعني أن جميع أوراق الشجر تقع على نفس المستوى. هذا يضمن أداء لوغاريتمي للبحث والإدراج والحذف.
- مملوءة جزئيًا: يمكن أن تحتوي كل عقدة على عدد متغير من المفاتيح ضمن نطاق محدد. عادةً ما تكون العقدة ممتلئة جزئيًا، مما يساعد على تقليل عدد عمليات إدخال/إخراج القرص.
- البيانات المصنفة: يتم تخزين المفاتيح داخل كل عقدة بترتيب مصنف، مما يسهل عمليات البحث الفعالة.
عمليات أشجار بي الأساسية
تشمل العمليات الأساسية التي يمكن إجراؤها على أشجار بي ما يلي:
- البحث (Search): تبدأ عملية البحث من العقدة الجذر وتنزل الشجرة، وتقارن قيمة البحث بالمفاتيح في كل عقدة. إذا تم العثور على القيمة، يتم إرجاع العقدة والموقع. إذا كانت القيمة أصغر من المفتاح الأصغر في العقدة، أو أكبر من المفتاح الأكبر، فإن البحث يستمر في الطفل المناسب.
- الإدراج (Insertion): لإدراج مفتاح جديد، يتم البحث أولاً عن موضع الإدراج المناسب. إذا كانت العقدة المستهدفة ممتلئة، يتم تقسيمها إلى عقدتين، ويتم نقل المفتاح المتوسط إلى العقدة الأصل. قد تتسبب هذه العملية في تقسيمات متتالية وصولاً إلى الجذر.
- الحذف (Deletion): يتضمن الحذف العثور على المفتاح المراد حذفه. إذا كان المفتاح في عقدة داخلية، فإنه يتم استبداله بالسابق أو الخلف اللاحق (أصغر مفتاح في الشجرة الفرعية اليمنى أو أكبر مفتاح في الشجرة الفرعية اليسرى). إذا كانت العقدة التي تم حذف المفتاح منها أقل من الحد الأدنى لعدد المفاتيح، يتم دمجها مع عقدة مجاورة أو يتم إعادة توزيع المفاتيح.
خوارزميات الإدراج في أشجار بي
تتضمن عملية إدراج مفتاح جديد في شجرة بي سلسلة من الخطوات لضمان الحفاظ على خصائص الشجرة. إليك وصف تفصيلي للخوارزمية:
- البحث عن العقدة المناسبة: ابدأ من جذر الشجرة وانتقل لأسفل الشجرة، واختر الطفل الذي يوجهك نحو الموقع المحتمل للمفتاح الجديد. استمر في هذه العملية حتى تصل إلى عقدة ورقة.
- إدراج المفتاح: إذا كانت العقدة الورقية ليست ممتلئة، فأدخل المفتاح الجديد في العقدة مع الحفاظ على ترتيب المفاتيح.
- معالجة التدفق الزائد: إذا كانت العقدة الورقية ممتلئة (أي أنها تحتوي على الحد الأقصى المسموح به من المفاتيح)، فيجب تقسيمها. هذا يعني تقسيم العقدة إلى عقدتين جديدتين.
- تقسيم العقدة: لتقسيم العقدة، حدد المفتاح الأوسط في العقدة الممتلئة. يتم ترقية هذا المفتاح الأوسط إلى العقدة الأصل. يتم تقسيم المفاتيح الموجودة على يسار المفتاح الأوسط إلى عقدة جديدة، ويتم تقسيم المفاتيح الموجودة على يمين المفتاح الأوسط إلى عقدة جديدة أخرى.
- تحديث الأصل: بعد تقسيم العقدة، يجب تحديث العقدة الأصل للإشارة إلى العقدتين الجديدتين. هذا قد يعني إدراج مفتاح جديد في العقدة الأصل.
- التقسيم المتتالي: إذا كانت العقدة الأصل ممتلئة أيضًا بعد إدراج المفتاح الجديد، فيجب تقسيمها أيضًا. هذه العملية قد تستمر بشكل متتالي وصولاً إلى جذر الشجرة.
- تقسيم الجذر: إذا كان الجذر ممتلئًا، فسيتم تقسيمه، مما يؤدي إلى زيادة ارتفاع الشجرة بمقدار واحد.
خوارزميات الحذف في أشجار بي
تعتبر عملية حذف مفتاح من شجرة بي أكثر تعقيدًا من الإدراج، حيث يجب ضمان عدم انتهاك خصائص الشجرة بعد الحذف. إليك وصف تفصيلي لخوارزمية الحذف:
- البحث عن المفتاح: ابدأ من جذر الشجرة وابحث عن المفتاح المراد حذفه.
- الحذف من عقدة ورقة: إذا كان المفتاح موجودًا في عقدة ورقة، فقم بحذفه ببساطة من العقدة.
- الحذف من عقدة داخلية: إذا كان المفتاح موجودًا في عقدة داخلية، فابحث عن السابق أو الخلف اللاحق (أصغر مفتاح في الشجرة الفرعية اليمنى أو أكبر مفتاح في الشجرة الفرعية اليسرى). استبدل المفتاح المراد حذفه بالسابق أو الخلف اللاحق، ثم احذف السابق أو الخلف اللاحق من عقدة الورقة المقابلة.
- معالجة النقص: بعد الحذف، إذا كانت العقدة تحتوي على عدد أقل من الحد الأدنى المسموح به من المفاتيح، فإنها تعتبر ناقصة. يجب معالجة النقص لضمان الحفاظ على خصائص الشجرة.
- إعادة التوزيع أو الدمج: لمعالجة النقص، حاول أولاً إعادة توزيع المفاتيح من عقدة مجاورة. إذا كانت العقدة المجاورة تحتوي على أكثر من الحد الأدنى من المفاتيح، فيمكن نقل مفتاح واحد منها إلى العقدة الناقصة. إذا كانت العقدة المجاورة تحتوي فقط على الحد الأدنى من المفاتيح، فيجب دمج العقدة الناقصة مع العقدة المجاورة.
- تحديث الأصل: بعد إعادة التوزيع أو الدمج، يجب تحديث العقدة الأصل لتعكس التغييرات.
- النقص المتتالي: إذا كانت العقدة الأصل أصبحت ناقصة أيضًا بعد التحديث، فيجب معالجة النقص فيها أيضًا. هذه العملية قد تستمر بشكل متتالي وصولاً إلى جذر الشجرة.
- حذف الجذر: إذا أصبح الجذر فارغًا (أي أنه لم يعد يحتوي على أي مفاتيح)، يتم حذف الجذر، ويصبح الطفل الوحيد الجديد هو الجذر.
تطبيقات أشجار بي
تستخدم أشجار بي على نطاق واسع في مختلف التطبيقات، بما في ذلك:
- قواعد البيانات: تُستخدم أشجار بي لإنشاء الفهارس في أنظمة إدارة قواعد البيانات (DBMS). تسمح الفهارس بالبحث السريع عن الصفوف بناءً على قيم أعمدة معينة.
- أنظمة الملفات: تستخدم العديد من أنظمة الملفات، مثل نظام ملفات exFAT ، أشجار بي لتنظيم بيانات الدليل. يسمح ذلك بالوصول الفعال إلى الملفات والدلائل.
- محركات البحث: يمكن استخدام أشجار بي لفهرسة صفحات الويب، مما يسمح لمحركات البحث بالعثور بسرعة على الصفحات ذات الصلة باستعلام بحث معين.
مزايا وعيوب أشجار بي
المزايا:
- أداء فعال: توفر أشجار بي أداءً لوغاريتميًا لعمليات البحث والإدراج والحذف، مما يجعلها مناسبة لإدارة كميات كبيرة من البيانات.
- الوصول المتسلسل: تدعم أشجار بي الوصول المتسلسل إلى البيانات المصنفة، مما يجعلها مفيدة للتطبيقات التي تحتاج إلى معالجة البيانات بترتيب معين.
- كفاءة إدخال/إخراج القرص: تم تصميم أشجار بي لتقليل عدد عمليات إدخال/إخراج القرص، مما يجعلها مناسبة لأنظمة تخزين البيانات الموجهة نحو القرص.
العيوب:
- التعقيد: يمكن أن تكون أشجار بي معقدة التنفيذ والصيانة.
- استهلاك الذاكرة: يمكن أن تستهلك أشجار بي قدرًا كبيرًا من الذاكرة، خاصة إذا كانت العقد كبيرة.
أشجار بي+
شجرة بي+ (B+ tree) هي شكل من أشكال شجرة بي التي تخزن سجلات البيانات فقط في عقد الأوراق؛ عقد داخلية تعمل كدليل. القيم داخل العقد الداخلية تفصل الشجرة، وتوفر بحثًا سريعًا عن السجلات في الأوراق. إنها هيكل بيانات شائع الاستخدام لتنفيذ الفهارس في قواعد البيانات العلائقية وأنظمة الملفات.
الاختلافات الرئيسية بين أشجار بي وأشجار بي+:
- في شجرة بي، يمكن تخزين كل من المفاتيح وسجلات البيانات في العقد الداخلية والأوراق. في شجرة بي+، يتم تخزين المفاتيح فقط في العقد الداخلية، ويتم تخزين سجلات البيانات في الأوراق.
- تحتوي أوراق شجرة بي+ على مؤشر إلى الورقة التالية في التسلسل، مما يسمح بالوصول المتسلسل الفعال إلى البيانات. لا تحتوي أشجار بي عادةً على هذا المؤشر.
خاتمة
شجرة بي (B-tree) هي هيكل بيانات شجرة ذاتية الموازنة فعالة للغاية تستخدم على نطاق واسع في قواعد البيانات وأنظمة الملفات ومحركات البحث. توفر أداءً لوغاريتميًا لعمليات البحث والإدراج والحذف، وتدعم الوصول المتسلسل إلى البيانات المصنفة، وتقلل من عدد عمليات إدخال/إخراج القرص. على الرغم من أنها معقدة التنفيذ والصيانة، إلا أن مزاياها تجعلها خيارًا شائعًا للعديد من التطبيقات.