تلعب شجرة B (B-tree) دوراً جوهرياً في العديد من البرمجيات، ولا سيما أنظمة إدارة قواعد البيانات (DBMS). إذ تعتمد أنظمة مثل MySQL وPostgres وMongoDB وDynamo وغيرها الكثير على أشجار B لإجراء عمليات بحث فعالة عن البيانات باستخدام الفهارس (indexes). وبحلول نهاية هذا المقال، ستكون قد تعرفت على آلية عمل أشجار B وأشجار +B، وسبب استخدام قواعد البيانات لها في بناء الفهارس، ولماذا قد يكون استخدام مُعرِّف فريد عالمياً (UUID) كمفتاح أساسي (primary key) فكرةً غير موفقة. كما ستتاح لك فرصة التفاعل مع رسوم متحركة توضيحية لهياكل البيانات التي نناقشها؛ لذا استعد لاستخدام الأزرار والتفاعل معها.
يوفر علم الحاسوب مجموعة واسعة من هياكل البيانات التي يمكن الاختيار من بينها لتخزين البيانات والبحث فيها وإدارتها على الحاسوب. وتُعد شجرة B إحدى هذه الهياكل، وهي شائعة الاستخدام في تطبيقات قواعد البيانات. تقوم أشجار B بتخزين أزواج من البيانات -تُعرف باسم "المفاتيح" و"القيم"- فيما يسميه المبرمجون "هيكلاً شجرياً"؛ ورغم هذه التسمية، فإن الشكل الفعلي لهذا الهيكل يشبه إلى حد كبير نظام الجذور النباتية.
ستجد أدناه العنصر التفاعلي الأول في هذه التدوينة؛ حيث يتيح لك هذا العنصر تصور هيكلية شجرة B ومراقبة ما يحدث عند إضافة أزواج من المفاتيح والقيم، أو عند تغيير عدد هذه الأزواج في كل عقدة (node). جرب ذلك بنفسك من خلال النقر على زر "إضافة" (Add) أو "إضافة عشوائية" (Add random) بضع مرات، وحاول تكوين فهم بديهي لآلية عملها قبل أن ننتقل إلى التفاصيل.
تتكون شجرة B (B-tree) من عُقد (تُمثَّل بالمستطيلات) ومؤشرات للأبناء (الخطوط التي تربط بين العُقد). نُطلق على العقدة الموجودة في أعلى الشجرة اسم "العقدة الجذرية" (root node)، وعلى العقد الموجودة في المستوى الأدنى اسم "العقد الورقية" (leaf nodes)، بينما تُسمى بقية العقد "العقد الداخلية" (internal nodes). قد يختلف التعريف الدقيق لشجرة B باختلاف المصدر، ولكن التعريف التالي يُعد تعريفاً نموذجياً وشائعاً:
شجرة B من الرتبة K هي بنية شجرية تتمتع بالخصائص التالية:
تُخزّن كل عقدة في الشجرة N من أزواج "المفتاح/القيمة"، حيث تكون قيمة N أكبر من 1 وأقل من أو تساوي K.
تحتوي كل عقدة داخلية على N/2 على الأقل من أزواج "المفتاح/القيمة" (والعقدة الداخلية هي العقدة التي لا تُعد ورقة ولا جذراً).
يكون لكل عقدة N+1 من العُقد الأبناء.
تحتوي العقدة الجذرية على قيمة واحدة على الأقل وعقدتين ابنتين، ما لم تكن هي العقدة الوحيدة في الشجرة.
تقع جميع العُقد الورقية في المستوى نفسه.
ليست هناك تعليقات:
إرسال تعليق