المحتوى

• رسم بياني للمقارنة
• تعريف شجرة ب
• خصائص B- شجرة من أجل M
• تعريف الشجرة الثنائية
• تقنيات السفر
• خاتمة

B- شجرة وشجرة ثنائية هي أنواع بنية البيانات غير الخطية. على الرغم من أن الشروط تبدو متشابهة ولكنها مختلفة في جميع الجوانب. يتم استخدام شجرة ثنائية عند تخزين السجلات أو البيانات في RAM بدلاً من القرص لأن سرعة الوصول إلى RAM أعلى بكثير من القرص. من ناحية أخرى ، يتم استخدام B-tree عندما يتم تخزين البيانات في القرص مما يقلل من وقت الوصول عن طريق تقليل ارتفاع الشجرة وزيادة الفروع في العقدة.

هناك اختلاف آخر بين الشجرة B والشجرة الثنائية وهو أن B-tree يجب أن تحتوي كل العقد الفرعية على نفس المستوى في حين أن الشجرة الثنائية ليس لديها مثل هذا القيد. يمكن أن تحتوي الشجرة الثنائية على 2 أشجار فرعية أو عقد بحد أقصى بينما يمكن في الشجرة B أن تحتوي على M no من الأشجار الفرعية أو العقد حيث M هو ترتيب الشجرة B.

1. رسم بياني للمقارنة
2. تعريف
3. الاختلافات الرئيسية
4. خاتمة

رسم بياني للمقارنة

أساس للمقارنة	B-شجرة	شجرة ثنائية
القيد الأساسي	يمكن أن تحتوي العقدة على أقصى عدد من العقد الفرعية (حيث M هي ترتيب الشجرة).	يمكن أن تحتوي العقدة على عدد 2 من الأشجار الفرعية بحد أقصى.
مستخدم	يتم استخدامه عند تخزين البيانات على القرص.	يتم استخدامه عندما يتم تخزين السجلات والبيانات في ذاكرة الوصول العشوائي.
ارتفاع الشجرة	سجلM N (حيث m هو ترتيب شجرة M-way)	سجل2 N
تطبيق	بنية بيانات الفهرسة في العديد من قواعد البيانات.	تحسين الكود ، ترميز هوفمان ، إلخ.

تعريف شجرة ب

شجرة B هي شجرة M-way المتوازنة والمعروفة أيضًا باسم شجرة الفرز المتوازنة. يشبه شجرة البحث الثنائية حيث يتم تنظيم العقد على أساس اجتياز inorder. تعقيد الفضاء لشجرة ب هو O (ن). تعقيد وقت الإدراج والحذف هو O (log n).

هناك بعض الشروط التي يجب أن تكون صحيحة لشجرة B:

• يجب أن يكون ارتفاع الشجرة كحد أدنى قدر الإمكان.
• فوق أوراق الشجرة ، يجب ألا يكون هناك أي شجرات فرعية فارغة.
• أوراق الشجرة يجب أن تأتي في نفس المستوى.
• يجب أن تحتوي جميع العقد على أقل عدد من الأطفال باستثناء عقد الإجازة.

خصائص B- شجرة من أجل M

• يمكن أن تحتوي كل عقدة على عدد M أقصى من الأطفال والحد الأدنى لعدد M / 2 من الأطفال أو أي عدد من 2 إلى الحد الأقصى.
• تحتوي كل عقدة على مفتاح واحد أقل من الأطفال الذين لديهم مفاتيح M-1 كحد أقصى.
• ترتيب المفاتيح بترتيب معين داخل العقد. جميع المفاتيح الموجودة في الشجرة الفرعية الموجودة على يسار المفتاح هي أسلاف المفتاح ، وتسمى تلك الموجودة في يمين المفتاح بالوراثة.
• في وقت إدخال عقدة كاملة ، تنقسم الشجرة إلى قسمين ، ويتم إدراج المفتاح ذي القيمة المتوسطة في العقدة الأصل.
• عملية الدمج تحدث عندما يتم حذف العقد.

تعريف الشجرة الثنائية

الشجرة الثنائية عبارة عن بنية شجرة يمكن أن تحتوي على أكثر من مؤشرين لعقدها الفرعية. وهذا يعني أن أعلى درجة يمكن أن تكون العقدة هي 2 وقد يكون هناك عقدة صفرية أو درجة واحدة أيضًا.

هناك بعض المتغيرات لشجرة ثنائية مثل الشجرة الثنائية بدقة ، الشجرة الثنائية الكاملة ، الشجرة الثنائية الممتدة ، إلخ.

• الشجرة الثنائية بدقة هي شجرة حيث يجب أن يكون لكل عقدة غير طرفية الشجرة الفرعية وشجرة الشجرة اليمنى.
• تسمى الشجرة بالشجرة الثنائية الكاملة عندما تلبي حالة وجود 2 ^أنا العقد في كل مستوى حيث أنا هو المستوى.
• الثنائي المترابط عبارة عن شجرة ثنائية تتكون إما من 0 عدد العقد أو عدد 2 من العقد.

تقنيات السفر

يعد اجتياز الشجرة أحد أكثر العمليات شيوعًا التي يتم إجراؤها على بنية بيانات الشجرة التي زارتها كل عقدة مرة واحدة فقط بطريقة منتظمة.

• Inorder- في هذا العرض التقديمي للشجرة ، تتم زيارة الشجرة الفرعية اليسرى بشكل متكرر ثم تتم زيارة عقدة الجذر وفي آخر زيارة للشجرة الفرعية اليمنى.
• Preorer- في هذا المقطع الشجري ، تتم زيارة العقدة الجذرية في البداية ثم الشجرة اليسرى وفي الشجرة اليمنى الأخيرة.
• Postorder - هذه التقنية تزور الشجرة اليسرى ثم الشجرة اليمنى وفي عقدة الجذر الأخيرة.

1. في B-tree ، يكون الحد الأقصى لعدد العقد الفرعية التي يمكن أن تمتلكها العقدة غير الطرفية هو M حيث M هو ترتيب الشجرة B. من ناحية أخرى ، يمكن أن تحتوي الشجرة الثنائية على أكثر من شريحتين فرعيتين أو عقد فرعية.
2. يتم استخدام B-tree عندما يتم تخزين البيانات في القرص بينما يتم استخدام الشجرة الثنائية عندما يتم تخزين البيانات في ذاكرة سريعة مثل ذاكرة الوصول العشوائي.
3. مجال آخر لتطبيق B-tree هو بنية بيانات فهرسة الكود في DBMS ، في المقابل ، يتم استخدام Binary tree في تحسين الكود ، ترميز huffman ، إلخ.
4. أقصى ارتفاع لشجرة ب هو السجل_MN (M هو ترتيب الشجرة). على عكس ، أقصى شجرة ثنائية هو سجل₂N (N هو عدد العقد والقاعدة 2 لأنها ثنائية).

خاتمة

يتم استخدام شجرة B على شجرة البحث الثنائية وثنائية السبب الرئيسي وراء ذلك هو التسلسل الهرمي للذاكرة حيث يتم توصيل وحدة المعالجة المركزية إلى ذاكرة التخزين المؤقت مع قنوات النطاق الترددي العالي بينما يتم توصيل وحدة المعالجة المركزية إلى القرص من خلال قناة عرض النطاق الترددي المنخفض. يتم استخدام شجرة ثنائية عندما يتم تخزين السجلات في ذاكرة الوصول العشوائي (صغيرة وسريعة) ويتم استخدام شجرة ب عندما يتم تخزين السجلات في القرص (كبير وبطيء). لذلك ، فإن استخدام شجرة B بدلاً من شجرة ثنائية يقلل بشكل كبير من وقت الوصول بسبب عامل التفريع العالي وانخفاض ارتفاع الشجرة.