هناك اختلاف آخر بين شجرة B والشجرة الثنائية هو أن B-tree يجب أن تحتوي على جميع العقد التابعة لها على نفس المستوى بينما لا تملك الشجرة الثنائية مثل هذا القيد. يمكن أن تحتوي الشجرة الثنائية على مجموعتين فرعيتين أو عقدتين كحد أقصى ، بينما في B-tree يمكن أن يكون M no من الأشجار الفرعية أو العقد حيث M هو ترتيب B-tree.
رسم بياني للمقارنة
| أساس للمقارنة | B-شجرة | شجرة ثنائية |
|---|---|---|
| القيد الأساسي | يمكن أن تكون العقدة بحد أقصى لعدد M من عقد الطفل (حيث M هي ترتيب الشجرة). | يمكن أن تحتوي العقدة على عدد 2 من الأشجار الفرعية كحد أقصى. |
| مستخدم | يتم استخدامه عند تخزين البيانات على القرص. | يتم استخدامه عندما يتم تخزين السجلات والبيانات في ذاكرة الوصول العشوائي. |
| ارتفاع الشجرة | log M N (حيث m هو ترتيب شجرة M-way) | سجل 2 ن |
| الوضعية | كود بيانات فهرسة هيكل في العديد من نظم إدارة قواعد البيانات. | تحسين الكود ، ترميز هوفمان ، إلخ. |
تعريف شجرة B
شجرة B هي شجرة M-way المتوازنة وتُعرف أيضًا باسم شجرة الفرز المتوازنة. وهو مماثل لشجرة البحث الثنائية حيث يتم تنظيم العقد على أساس اجتياز فرعي. تعقيد الفضاء لـ B-tree هو O (n). زمن تعقيد الإدراج والحذف هو O (log n).
هناك بعض الشروط التي يجب أن تكون صحيحة لشجرة B:
- يجب أن يكون ارتفاع الشجرة عند أدنى حد ممكن.
- فوق أوراق الشجرة ، لا ينبغي أن يكون هناك أي أشجار فرعية فارغة.
- يجب أن تأتي أوراق الشجرة على نفس المستوى.
- يجب أن تحتوي جميع العقد على أقل عدد من الأطفال باستثناء نقاط الإجازة.
خصائص شجرة B من ترتيب M
- يمكن أن تحتوي كل عقدة على الحد الأقصى لعدد الأطفال M والحد الأدنى لعدد M / 2 من الأطفال أو أي رقم من 2 إلى الحد الأقصى.
- لكل عقدة مفتاح واحد أقل من الأطفال الذين لديهم مفاتيح M-1 القصوى.
- ترتيب المفاتيح في بعض ترتيب معين داخل العقد. جميع المفاتيح الموجودة في الشجرة الفرعية الموجودة في يسار المفتاح هي أسلاف المفتاح ، وتُدعي الموجودة في يمين المفتاح بـ "الورثة".
- في وقت إدخال عقدة كاملة ، يتم تقسيم الشجرة إلى جزئين ، ويتم إدخال المفتاح ذي القيمة المتوسطة في العقدة الرئيسية.
- تتم عملية الدمج عندما يتم حذف العقد.
تعريف الشجرة الثنائية
الشجرة الثنائية هي بنية شجرية يمكن أن تحتوي على أكثر من مؤشرين لعقد الطفل. وهذا يعني أن أعلى درجة يمكن أن تحتويها العقدة هي 2 ويمكن أن تكون هناك عقدة صفرية أو درجة واحدة أيضًا.
هناك أنواع معينة من شجرة ثنائية مثل شجرة ثنائية صارمة ، شجرة ثنائية كاملة ، شجرة ثنائية ممتدة ، إلخ.
- إن الشجرة الثنائية هي شجرة حيث يجب أن تكون كل عقدة غير طرفية قد تركت الشجرة الفرعية والشجرة الصحيحة.
- يطلق على الشجرة شجرة ثنائية كاملة عندما تفي بشرط وجود عقدتين على كل مستوى حيث i هو المستوى.
- الثنائي الثنائي عبارة عن شجرة ثنائية تتكون إما من 0 لا للعقد أو رقمين من العقد.
تقنيات العبور
يعتبر اجتياز الأشجار أحد أكثر العمليات التي يتم إجراؤها بشكل متكرر على بنية البيانات الشجرية التي تزورها كل عقدة مرة واحدة بطريقة منهجية.
- Inorder- في هذه الشجرة traversal ، تتم زيارة الشجرة الفرعية بشكل متكرر ثم يتم زيارة العقدة الجذرية وفي آخر زيارة للشجرة الفرعية الصحيحة.
- Preorer- في هذه الشجرة traversal يتم زيارة العقدة الجذرية في الشجرة الفرعية ثم اليسار ثم في الشجرة الفرعية الأيمن الأخير.
- Postorder - هذه التقنية زيارة الشجرة الفرعية اليسار ثم الشجرة الفرعية الصحيحة وفي العقدة الجذرية الأخيرة.
الاختلافات الأساسية بين B شجرة و شجرة ثنائية
- في B-tree ، الحد الأقصى لعدد العقد التابعة التي يمكن أن تحتويها عقدة غير طرفية هو M حيث M هو ترتيب B-tree. من ناحية أخرى ، يمكن أن تحتوي الشجرة الثنائية على أكثر شرتين فرعيتين أو عقدتي أطفال.
- يتم استخدام B-tree عند تخزين البيانات في القرص بينما يتم استخدام الشجرة الثنائية عند تخزين البيانات في ذاكرة سريعة مثل RAM.
- مجال آخر للتطبيق لـ B-tree هو بنية بيانات فهرسة الشفرة في DBMS ، في المقابل ، يتم استخدام Binary tree في تحسين الكود ، وترميز Huffman ، إلخ.
- الحد الأقصى لارتفاع شجرة B هو السجل M N (M هو ترتيب الشجرة). مقابل ، الحد الأقصى لارتفاع الشجرة الثنائية هو log 2 N (N هو عدد العقد والقاعدة 2 لأنها خاصة بـ binary).
استنتاج
يتم استخدام B-tree على شجرة البحث الثنائية والثنائية ، والسبب الرئيسي وراء ذلك هو التسلسل الهرمي للذاكرة حيث يتم توصيل وحدة المعالجة المركزية بالتخزين المؤقت مع قنوات النطاق الترددي العالي أثناء توصيل وحدة المعالجة المركزية بالقرص عبر قناة ذات نطاق ترددي منخفض. يتم استخدام الشجرة الثنائية عند تخزين السجلات في ذاكرة الوصول العشوائي (صغيرة وسريعة) ويتم استخدام B-tree عند تخزين السجلات في القرص (كبير وبطيء). لذا ، فإن استخدام B-tree بدلاً من الشجرة الثنائية يقلل بشكل كبير من وقت الوصول بسبب عامل التفرع العالي وانخفاض ارتفاع الشجرة.
