قبل الفهم شجرة ب و شجرة ب+ الاختلافات، يجب أن نعرف الشجرة B والشجرة B+ بشكل منفصل.

ما هي الشجرة ب؟

شجرة ب هي شجرة ذاتية التوازن، وهي شجرة ذات اتجاه م حيث تحدد م ترتيب الشجرة. بتري هو تعميم لل شجرة البحث الثنائية حيث يمكن أن تحتوي العقدة على أكثر من مفتاح واحد وأكثر من طفلين اعتمادًا على قيمة م . في الشجرة B، يتم تحديد البيانات بترتيب فرز يحتوي على قيم أقل على الشجرة الفرعية اليسرى وقيم أعلى في الشجرة الفرعية اليمنى.

حدد ك

خصائص شجرة B

فيما يلي خصائص الشجرة B:

• في الشجرة B، يجب أن تكون جميع العقد الورقية على نفس المستوى، بينما في حالة الشجرة الثنائية، يمكن أن تكون العقد الورقية على مستويات مختلفة.

دعونا نفهم هذه الخاصية من خلال مثال.

في الشجرة أعلاه، جميع العقد الورقية ليست على نفس المستوى، ولكن لديها طفلين أقصى. لذلك يمكننا القول أن الشجرة المذكورة أعلاه هي أ شجرة ثنائية ولكن ليس شجرة B.

• إذا كان ترتيب Btree هو m، فيمكن أن يكون لكل عقدة حد أقصى قدره م في حالة الحد الأدنى من الأطفال، فإن العقد الورقية ليس لها أطفال، والعقدة الجذرية لها طفلان، والعقد الداخلية لها سقف م/2.
• يمكن أن تحتوي كل عقدة على مفاتيح بحد أقصى (m-1). على سبيل المثال، إذا كانت قيمة m هي 5، فإن الحد الأقصى لقيمة المفاتيح هو 4.
• تحتوي العقدة الجذرية على مفتاح واحد على الأقل، في حين أن جميع العقد الأخرى باستثناء العقدة الجذرية لديها (سقف م/2 ناقص - 1) الحد الأدنى من المفاتيح.
• إذا قمنا بالإدراج في الشجرة B، فسيتم دائمًا إدراج العقدة في العقدة الورقية.

لنفترض أننا نريد إنشاء شجرة B من الرتبة 3 عن طريق إدراج القيم من 1 إلى 10.

الخطوة 1: أولاً، نقوم بإنشاء عقدة بقيمة واحدة كما هو موضح أدناه:

الخطوة 2: العنصر التالي هو 2، والذي يأتي بعد 1 كما هو موضح أدناه:

الخطوه 3: العنصر التالي هو 3، ويتم إدراجه بعد 2 كما هو موضح أدناه:

كما نعلم أن كل عقدة يمكن أن تحتوي على مفتاحين كحد أقصى، لذلك سنقوم بتقسيم هذه العقدة إلى العنصر الأوسط. العنصر الأوسط هو 2، لذلك ينتقل إلى الأصل. لا تحتوي العقدة 2 على أي عقدة أصل، لذا ستصبح العقدة الجذرية كما هو موضح أدناه:

الخطوة 4: العنصر التالي هو 4. وبما أن 4 أكبر من 2 و3، فسيتم إضافته بعد 3 كما هو موضح أدناه:

الخطوة 5: العنصر التالي هو 5. وبما أن 5 أكبر من 2 و3 و4، فسيتم إضافته بعد 4 كما هو موضح أدناه:

كما نعلم أن كل عقدة يمكن أن تحتوي على مفتاحين كحد أقصى، لذلك سنقوم بتقسيم هذه العقدة إلى العنصر الأوسط. العنصر الأوسط هو 4، لذلك ينتقل إلى الأصل. الأصل هو العقدة 2؛ لذلك سيتم إضافة 4 بعد 2 كما هو موضح أدناه:

الخطوة 6: العنصر التالي هو 6. وبما أن 6 أكبر من 2 و4 و5، فإن 6 سيأتي بعد 5 كما هو موضح أدناه:

الخطوة 7: العنصر التالي هو 7. وبما أن 7 أكبر من 2 و4 و5 و6، فإن 7 سيأتي بعد 6 كما هو موضح أدناه:

كما نعلم أن كل عقدة يمكن أن تحتوي على مفتاحين كحد أقصى، لذلك سنقوم بتقسيم هذه العقدة إلى العنصر الأوسط. العنصر الأوسط هو 6، لذلك ينتقل إلى العنصر الأصلي كما هو موضح أدناه:

لكن لا يمكن إضافة 6 بعد 4 لأن العقدة يمكن أن تحتوي على مفتاحين كحد أقصى، لذلك سنقوم بتقسيم هذه العقدة إلى العنصر الأوسط. العنصر الأوسط هو 4، لذلك ينتقل إلى الأصل. نظرًا لأن العقدة 4 لا تحتوي على أي عقدة أصل، فستصبح العقدة 4 عقدة جذر كما هو موضح أدناه:

ما هي شجرة B+؟

ال شجرة ب+ تُعرف أيضًا باسم شجرة التوازن الذاتي المتقدمة لأن كل مسار من جذر الشجرة إلى ورقة الشجرة له نفس الطول. هنا، يعني نفس الطول أن جميع العقد الورقية تحدث على نفس المستوى. لن يحدث أن بعض العقد الورقية تحدث في المستوى الثالث وبعضها في المستوى الثاني.

يعتبر فهرس شجرة B+ فهرسًا متعدد المستويات، لكن بنية شجرة B+ لا تشبه الملفات التسلسلية للفهرس متعدد المستويات.

لماذا يتم استخدام شجرة B+؟

يتم استخدام شجرة B+ لتخزين السجلات بكفاءة عالية عن طريق تخزين السجلات بطريقة مفهرسة باستخدام البنية المفهرسة لشجرة B+. وبفضل الفهرسة متعددة المستويات، يصبح الوصول إلى البيانات أسرع وأسهل.

هيكل عقدة الشجرة B+

تحتوي بنية العقدة لشجرة B+ على مؤشرات وقيم أساسية موضحة في الشكل أدناه:

كما يمكننا أن نلاحظ في بنية عقدة شجرة B+ أعلاه أنها تحتوي على قيم مفاتيح n-1 (k₁إلى ك_ن-1) ومؤشرات n (ص₁قمة_ن).

يتم الاحتفاظ بقيم مفتاح البحث الموضوعة في العقدة بترتيب فرزها. وهكذا، إذا أناأناي.

القيود على أنواع مختلفة من العقد

دع 'b' يكون ترتيب شجرة B+.

العقدة غير الورقية

لنفترض أن 'm' يمثل عدد الأطفال للعقدة، فيمكن تمثيل العلاقة بين ترتيب الشجرة وعدد الأطفال على النحو التالي:

دع k يمثل قيم مفتاح البحث. يمكن تمثيل العلاقة بين ترتيب الشجرة ومفتاح البحث على النحو التالي:

وكما نعلم أن عدد المؤشرات يساوي قيم مفتاح البحث زائد 1، لذلك يمكن كتابتها رياضياً على النحو التالي:

عدد المؤشرات (أو الأطفال) = عدد مفاتيح البحث + 1

لذلك، سيكون الحد الأقصى لعدد المؤشرات هو 'b'، وسيكون الحد الأدنى لعدد المؤشرات هو دالة السقف b/2.

عقدة ورقة

العقدة الطرفية هي عقدة تحدث في المستوى الأخير من شجرة B+، وتستخدم كل عقدة طرفية مؤشرًا واحدًا فقط للاتصال مع بعضها البعض لتوفير الوصول المتسلسل على المستوى الطرفي.

في العقدة الورقية، الحد الأقصى لعدد الأطفال هو:

الحد الأقصى لعدد مفاتيح البحث هو:

لين السلسلة في جافا

عقدة الجذر

الحد الأقصى لعدد الأطفال في حالة العقدة الجذرية هو: ب

الحد الأدنى لعدد الأطفال هو: 2

حالات خاصة في شجرة B+

حالة 1: إذا كانت العقدة الجذرية هي العقدة الوحيدة في الشجرة. في هذه الحالة، تصبح العقدة الجذرية هي العقدة الورقية.

في هذه الحالة، الحد الأقصى لعدد الأطفال هو 1، أي العقدة الجذرية نفسها، في حين أن الحد الأدنى لعدد الأطفال هو b-1، وهو نفس عدد العقد الورقية.

تمثيل العقدة الورقية في شجرة B+

في الشكل أعلاه، '.' يمثل المؤشر، في حين أن 10 و 20 و 30 هي القيم الأساسية. يحتوي المؤشر على العنوان الذي تم تخزين قيمة المفتاح فيه، كما هو موضح في الشكل أعلاه.

مثال على شجرة B+

في الشكل أعلاه، تحتوي العقدة على ثلاث قيم رئيسية، أي 9 و16 و25. يحتوي المؤشر الذي يظهر قبل 9 على القيم الأساسية الأقل من 9 الممثلة بـ k_أنا. يحتوي المؤشر الذي يظهر قبل الرقم 16 على القيم الأساسية الأكبر من أو تساوي 9 ولكن أقل من 16 الممثلة بـ kj. المؤشر الذي يظهر قبل 25، يحتوي على القيم الأساسية الأكبر من أو تساوي 16 ولكن أقل من 25 ممثلة بـ k_ن.

الاختلافات بين الشجرة B والشجرة B+

فيما يلي الاختلافات بين الشجرة B والشجرة B+: