شجرة البحث (شجرة B) تجعل الفهرس سريعاً
تُخزَّن عقد أوراق الفهرس بترتيب عشوائي—فالموضع على القرص لا يقابل الموضع المنطقي وفق ترتيب الفهرس. إنه مثل دليل هاتف بصفحات مبعثرة. فإذا بحثت عن «Smith» لكنك فتحت الدليل أولاً عند «Robinson»، فليس مضموناً بأي حال أن يأتي Smith بعد Robinson. وتحتاج قاعدة البيانات إلى بنية ثانية للعثور على المدخل بين الصفحات المبعثرة بسرعة: شجرة بحث متوازنة (balanced search tree)—باختصار: شجرة B.
الشكل 1.2 بنية شجرة B
يعرض الشكل 1.2 مثالاً لفهرس فيه 30 مدخلاً. وتنشئ القائمة المترابطة المزدوجة الترتيب المنطقي بين عقد الأوراق. وتدعم العقدة الجذرية والعقد الفرعية (root and branch nodes) البحث السريع بين عقد الأوراق.
يبرز الشكل عقدة فرعية وعقد الأوراق التي تشير إليها. ويقابل كل مدخل في العقدة الفرعية أكبر قيمة في عقدة الورقة المعنية. خُذ أول عقدة ورقة مثلاً: أكبر قيمة في هذه العقدة هي 46، وهي المخزنة في مدخل العقدة الفرعية المقابل. وينطبق الأمر نفسه على عقد الأوراق الأخرى، بحيث تحمل العقدة الفرعية في النهاية القيم 46 و53 و57 و83. ووفق هذا المخطط، تُبنى طبقة فرعية حتى تُغطّى جميع عقد الأوراق بعقدة فرعية.
إن أعجبك هذا الموضوع، قد يعجبك أيضاً…
… أن تشترك في القوائم البريدية، وتحصل على ملصقات مجانية، وتشتري كتابي، أو تنضم إلى دورة تدريبية.
تُبنى الطبقة التالية بطريقة مشابهة، لكن فوق مستوى العقد الفرعية الأول. وتتكرر العملية حتى تتّسع كل المفاتيح في عقدة واحدة، هي العقدة الجذرية (root node). والبنية شجرة بحث متوازنة لأن عمق الشجرة متساوٍ في كل موضع؛ فالمسافة بين العقدة الجذرية وعقد الأوراق هي نفسها في كل مكان.
ملاحظة
شجرة B شجرة متوازنة—وليست شجرة ثنائية.
وبعد إنشائه، تحافظ قاعدة البيانات على الفهرس تلقائياً. فهي تطبّق كل عملية insert وdelete وupdate على الفهرس وتبقي الشجرة متوازنة، مما يسبب عبئاً صيانياً لعمليات الكتابة. ويشرح الفصل 8، «تعديل البيانات» ذلك بمزيد من التفصيل.
الشكل 1.3 اجتياز شجرة B
يعرض الشكل 1.3 جزءاً من فهرس لتوضيح البحث عن المفتاح «57». يبدأ اجتياز الشجرة عند العقدة الجذرية على الجانب الأيسر. وتُعالَج كل مدخلة بترتيب تصاعدي حتى تُوجد قيمة أكبر من أو تساوي (>=) مصطلح البحث (57). وفي الشكل يكون ذلك المدخل 83. فتتبع قاعدة البيانات الإشارة إلى العقدة الفرعية المقابلة وتكرر العملية حتى يصل اجتياز الشجرة إلى عقدة ورقة.
مهم
تُمكّن شجرة B قاعدة البيانات من العثور على عقدة ورقة بسرعة.
اجتياز الشجرة عملية فعّالة جداً—فعّالة لدرجة أنني أسميها القوة الأولى للفهرسة. وهي تعمل فوراً تقريباً—حتى على مجموعة بيانات ضخمة. ويعود ذلك أساساً إلى توازن الشجرة، الذي يتيح الوصول إلى جميع العناصر بالعدد نفسه من الخطوات، وثانياً إلى النمو اللوغاريتمي لعمق الشجرة. وهذا يعني أن عمق الشجرة ينمو ببطء شديد مقارنةً بعدد عقد الأوراق. فالفهارس في العالم الحقيقي التي تضم ملايين السجلات لها عمق شجرة أربعة أو خمسة. ونادراً ما يُرى عمق شجرة ستة. ويصف الصندوق «قابلية التوسع اللوغاريتمية» ذلك بمزيد من التفصيل.
قابلية التوسع اللوغاريتمية
في الرياضيات، لوغاريتم عدد بالنسبة إلى أساس معطى هو القوة أو الأس الذي يجب رفع الأساس إليه لإنتاج ذلك العدد ويكيبيديا.
في شجرة بحث، يقابل الأساس عدد المدخلات في كل عقدة فرعية، ويقابل الأس عمق الشجرة. والمثال في الشكل 1.2 يتسع لأربعة مدخلات في كل عقدة وعمقه ثلاثة. ويعني ذلك أن الفهرس يمكن أن يحمل حتى 64 (4³) مدخلاً. وإذا نما مستوى واحداً، يمكنه أن يحمل 256 مدخلاً (4⁴). وفي كل مرة يُضاف مستوى، يتضاعف الحد الأقصى لعدد مدخلات الفهرس أربع مرات. ويعكس اللوغاريتم هذه الدالة. لذا فإن عمق الشجرة هو log₄(عدد-مدخلات-الفهرس).
| عمق الشجرة | مدخلات الفهرس |
|---|---|
| 3 | 64 |
| 4 | 256 |
| 5 | 1,024 |
| 6 | 4,096 |
| 7 | 16,384 |
| 8 | 65,536 |
| 9 | 262,144 |
| 10 | 1,048,576 |
النمو اللوغاريتمي يمكّن الفهرس المثال من البحث في مليون سجل بعشرة مستويات شجرية، لكن الفهرس في العالم الحقيقي أكثر كفاءة. والعامل الرئيسي المؤثر في عمق الشجرة، وبالتالي في أداء البحث، هو عدد المدخلات في كل عقدة شجرية. وهذا العدد يقابل—رياضياً—أساس اللوغاريتم. وكلما ارتفع الأساس، قلّ عمق الشجرة، وأسرع الاجتياز.
تستغل قواعد البيانات هذا المفهوم إلى أقصى حد وتضع أكبر عدد ممكن من المدخلات في كل عقدة—غالباً مئات. ويعني ذلك أن كل مستوى جديد من الفهرس يدعم مئة ضعف من المدخلات.