ما هو B+ tree؟ شرح مبسّط لهيكل البيانات الذي تعتمد عليه قواعد البيانات
شجرة B+ tree (تُنطق «بي بلَس تري») هي هيكل بيانات شجري متوازن يُستخدم أساسًا لفهرسة كميات ضخمة من البيانات المخزّنة على القرص، مثل الفهارس في قواعد البيانات وأنظمة الملفات. فكرتها الجوهرية بسيطة: احتفظ بكل البيانات الحقيقية في المستوى الأخير من الشجرة (الأوراق)، واجعل المستويات العليا مجرد «دليل بحث» يقودك بسرعة إلى الورقة الصحيحة. هذا التصميم هو ما يجعل استعلامًا مثل SELECT ... WHERE id = 5000000 يعود بنتيجة في أجزاء من الثانية رغم وجود ملايين الصفوف.
قبل الدخول في التفاصيل، انتبه إلى نقطة يخلط فيها الكثيرون: B+ tree ليست شجرة بحث ثنائية. الشجرة الثنائية لكل عقدة فيها ابنان على الأكثر، بينما عقدة واحدة في B+ tree قد تحتوي على مئات المفاتيح ومئات الأبناء. هذا الفارق هو سبب وجودها أصلًا.
لماذا لا تكفي شجرة البحث الثنائية؟
المشكلة ليست في الحسابات بل في القرص الصلب. قراءة البيانات من القرص أبطأ بآلاف المرات من قراءتها من الذاكرة، والقرص يقرأ دائمًا على شكل «كتل» (blocks) بحجم ثابت. في شجرة ثنائية توازن مثالي على مليون عنصر، قد تحتاج نحو 20 قفزة، وكل قفزة قد تعني قراءة قرص منفصلة.
الحل في B+ tree هو تقليل ارتفاع الشجرة عبر حشو كل عقدة بأكبر عدد ممكن من المفاتيح بحيث تملأ كتلة قرص كاملة. عندما تحمل العقدة الواحدة مئات المؤشرات، تصبح شجرة على ملايين العناصر بارتفاع 3 أو 4 مستويات فقط. أي أن البحث يكلّف 3 أو 4 قراءات قرص بدلًا من عشرين.
بنية الشجرة: عقد داخلية وأوراق
تتكوّن الشجرة من نوعين من العقد لكلٍّ منهما دور مختلف تمامًا:
- العقد الداخلية (Internal / index nodes): لا تخزّن بيانات فعلية، بل مفاتيح «فاصلة» ومؤشرات إلى الأبناء. المفتاح هنا يعمل كعلامة طريق: «القيم الأصغر من 50 على اليسار، والأكبر أو تساوي 50 على اليمين».
- العقد الورقية (Leaf nodes): هنا تقيم البيانات الحقيقية أو مؤشرات الصفوف الفعلية. كل القيم موجودة في هذا المستوى، وكل الأوراق على العمق نفسه بالضبط، ولهذا تُوصف الشجرة بأنها متوازنة.
الميزة الأهم والأكثر تميّزًا: الأوراق مرتبطة ببعضها في قائمة مترابطة مرتّبة تصاعديًا. هذا الرابط الأفقي هو ما يجعل استعلامات النطاق فعّالة للغاية، مثل «أعطني كل الطلبات بين تاريخين». فبمجرد الوصول إلى بداية النطاق، تمشي الشجرة على الأوراق المتتالية دون العودة إلى الأعلى.
العمليات الأساسية
- البحث: ابدأ من الجذر، وفي كل عقدة قارن المفتاح المطلوب بالمفاتيح الفاصلة لتحديد الابن التالي، إلى أن تصل إلى ورقة. التكلفة تتناسب مع ارتفاع الشجرة، أي O(log n) لكن بأساس لوغاريتمي كبير جدًا.
- الإدراج: ابحث عن الورقة المناسبة وأضف المفتاح مرتّبًا. إذا امتلأت الورقة، تُقسَم (split) إلى ورقتين ويُرفَع مفتاح فاصل إلى العقدة الأب، وقد يتسلسل الانقسام حتى الجذر.
- الحذف: أزل المفتاح من الورقة، وإذا نقص محتواها عن الحد الأدنى، تُعيد الشجرة التوازن عبر الاستعارة من عقدة مجاورة أو الدمج معها.
B+ tree أم B-tree؟
الاسمان متقاربان لكن الفرق جوهري، وهو أكثر ما يُسأل عنه في الامتحانات والمقابلات:
| المعيار | B-tree | B+ tree |
|---|---|---|
| موقع البيانات | في العقد الداخلية والأوراق معًا | في الأوراق فقط |
| العقد الداخلية | تخزّن مفاتيح وبيانات | تخزّن مفاتيح فاصلة فقط |
| ربط الأوراق | غير مترابطة عادةً | مترابطة في قائمة مرتّبة |
| استعلامات النطاق | أبطأ نسبيًا | سريعة جدًا |
| عدد الأبناء لكل عقدة | أقل (لأن العقدة تحمل بيانات) | أعلى (مفاتيح فقط ⇐ شجرة أقصر) |
الخلاصة: لأن العقدة الداخلية في B+ tree لا تُهدر مساحة على البيانات، فإنها تسع مفاتيح أكثر، فتصبح الشجرة أقصر والبحث أسرع، مع أفضلية واضحة في مسح النطاقات. لهذا تعتمد معظم قواعد البيانات على B+ tree لفهارسها.
أين تُستخدم عمليًا؟
هذا ليس هيكلًا أكاديميًا فحسب، بل يشغّل أدوات تستعملها يوميًا: محرّك InnoDB في MySQL يبني فهارسه على B+ tree، وكذلك فهارس PostgreSQL الافتراضية، وأنظمة ملفات مثل NTFS وext4 وBtrfs تعتمد أشكالًا منها لتنظيم الملفات والدلائل.
نصيحة عملية من التطبيق الحقيقي: عندما تنشئ فهرسًا على عمود في قاعدة بيانات، فأنت فعليًا تبني B+ tree على ذلك العمود. لهذا يفيد الفهرس استعلامات المساواة والنطاق والترتيب ORDER BY، بينما لا ينفع مع بحث مثل LIKE '%كلمة%' الذي يبدأ بمحرف بدل، لأن الشجرة تعتمد على الترتيب من اليسار ولا تعرف من أين تبدأ.
الأسئلة الشائعة
هل B+ tree أسرع دائمًا من B-tree؟ ليس في كل حالة. للبحث عن قيمة مفردة موجودة قرب الجذر قد تصل إليها B-tree أسرع بقليل. لكن في مسح النطاقات وفي كامل أعباء قواعد البيانات النموذجية، تتفوّق B+ tree، ولهذا صارت الخيار السائد.
ما معنى «رتبة» (order) الشجرة؟ هي الحد الأقصى لعدد الأبناء الذي تحمله العقدة الواحدة. كلما زادت الرتبة، ازداد تفرّع الشجرة وقلّ ارتفاعها، وتُختار عادةً لتملأ العقدة كتلة قرص كاملة.
هل أحتاج إلى برمجتها بنفسي؟ غالبًا لا. قواعد البيانات وأنظمة الملفات تديرها داخليًا. تنفيذها يدويًا مفيد للتعلّم وفهم ما يجري خلف الكواليس، لكن في الإنتاج ستعتمد على المحرّك الجاهز.
ما الفرق بينها وبين الجدول التجزيئي (Hash index)؟ الجدول التجزيئي أسرع لبحث المساواة الدقيقة فقط، لكنه لا يدعم النطاقات ولا الترتيب لأنه لا يحافظ على ترتيب المفاتيح. B+ tree يدعم الاثنين معًا، وهذا سبب شيوعه كفهرس افتراضي.