B+ TREE: بحث وإدراج وحذف Operaمثال

ما هي شجرة B+؟

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

قواعد شجرة B+

فيما يلي القواعد الأساسية لـ B+ Tree.

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

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

فيما يلي أسباب استخدام B+ Tree:

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

شجرة B+ مقابل شجرة B

فيما يلي الاختلافات الرئيسية بين B+ Tree وB Tree

ب + شجرة	شجرة ب
يمكن تكرار مفاتيح البحث.	لا يمكن أن تكون مفاتيح البحث زائدة عن الحاجة.
يتم حفظ البيانات فقط على العقد الورقية.	يمكن لكل من العقد الورقية والعقد الداخلية تخزين البيانات
البيانات المخزنة على العقدة الطرفية تجعل البحث أكثر دقة وأسرع.	يعد البحث بطيئًا بسبب البيانات المخزنة على العقد الورقية والداخلية.
الحذف ليس بالأمر الصعب حيث تتم إزالة العنصر فقط من العقدة الطرفية.	يعد حذف العناصر عملية معقدة وتستغرق وقتًا طويلاً.
العقد الورقية المرتبطة تجعل البحث فعالاً وسريعًا.	لا يمكنك ربط العقد الورقية.

بحث Operaالإنتاج

يعد البحث في B+ Tree من أسهل الإجراءات التي يتم تنفيذها والحصول على نتائج سريعة ودقيقة منه.

يتم تطبيق خوارزمية البحث التالية:

• للعثور على السجل المطلوب، تحتاج إلى تنفيذ بحث ثنائي على السجلات المتوفرة في الشجرة.
• في حالة وجود تطابق تام مع مفتاح البحث، يتم إرجاع السجل المقابل للمستخدم.
• في حالة عدم العثور على المفتاح الدقيق عن طريق البحث في العقدة الأصلية أو الحالية أو العقدة الورقية، فسيتم عرض رسالة "لم يتم العثور عليه" للمستخدم.
• ويمكن إعادة تشغيل عملية البحث للحصول على نتائج أفضل وأكثر دقة.

بحث Operaخوارزمية نشوئها

 1. Call the binary search method on the records in the B+ Tree.
 2. If the search parameters match the exact key
            The accurate result is returned and displayed to the user
          Else, if the node being searched is the current and the exact key is not found by the algorithm
            Display the statement "Recordset cannot be found."

الناتج:

يتم عرض مجموعة السجلات المطابقة للمفتاح الدقيق للمستخدم؛ وإلا، يتم عرض محاولة فاشلة للمستخدم.

إدراج Operaالإنتاج

يتم تطبيق الخوارزمية التالية لعملية الإدراج:

• يتم نقل 50 بالمائة من العناصر الموجودة في العقد إلى ورقة جديدة للتخزين.
• يتم ربط أصل الورقة الجديدة بدقة مع الحد الأدنى من قيمة المفتاح والموقع الجديد في الشجرة.
• قم بتقسيم العقدة الأصلية إلى المزيد من المواقع في حالة استخدامها بالكامل.
• الآن، للحصول على نتائج أفضل، يرتبط المفتاح الأوسط بعقدة المستوى الأعلى لتلك الورقة.
• حتى لا يتم العثور على عقدة المستوى الأعلى، استمر في تكرار العملية الموضحة في الخطوات المذكورة أعلاه.

إدراج Operaخوارزمية نشوئها

1.	Even inserting at-least 1 entry into the leaf container does not make it full then add the record  
     2. Else, divide the node into more locations to fit more records.
      a. Assign a new leaf and transfer 50 percent of the node elements to a new placement in the tree
      b. The minimum key of the binary tree leaf and its new key address are associated with the top-level node.
      c. Divide the top-level node if it gets full of keys and addresses.
          i. Similarly,  insert a key in the center of the top-level node in the hierarchy of the Tree.
     d. Continue to execute the above steps until a top-level node is found that does not need to be divided anymore. 

3) Build a new top-level root node of 1 Key and 2 indicators.  

الناتج:

ستحدد الخوارزمية العنصر وتدرجه بنجاح في العقدة الطرفية المطلوبة.

تم شرح مثال نموذج B+ Tree أعلاه في الخطوات التالية:

• أولاً، لدينا 3 عقد، ويتم إضافة العناصر الثلاثة الأولى، وهي 3 و1 و4، في المواقع المناسبة في العقد.
• القيمة التالية في سلسلة البيانات هي 12 والتي يجب أن تكون جزءًا من الشجرة.
• لتحقيق ذلك، قم بتقسيم العقدة وإضافة 6 كعنصر مؤشر.
• الآن، يتم إنشاء التسلسل الهرمي الأيمن للشجرة، ويتم تعديل قيم البيانات المتبقية وفقًا لذلك من خلال مراعاة القواعد المطبقة التي تساوي أو تزيد عن القيم مقابل عقد القيمة الرئيسية على اليمين.

حذف Operaالإنتاج

إن تعقيد عملية الحذف في شجرة B+ يتجاوز تعقيد وظيفة الإدراج والبحث.

يمكن تطبيق الخوارزمية التالية أثناء حذف عنصر من شجرة B+:

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

يوضح المثال أعلاه الإجراء الخاص بإزالة عنصر من شجرة B+ بترتيب معين.

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

• في المثال أعلاه، علينا حذف 31 من الشجرة.
• نحن بحاجة إلى تحديد مثيلات 31 في الفهرس والأوراق.
• يمكننا أن نرى أن 31 متاح في كل من مستوى العقدة الفهرسية والورقية. ولذلك نحذفه من الحالتين.
• لكن علينا ملء الفهرس الذي يشير إلى 42. سننظر الآن إلى الطفل المناسب الذي يقل عمره عن 25 عامًا ونأخذ القيمة الدنيا ونضعها كمؤشر. لذلك، 42 هي القيمة الوحيدة الموجودة، وسوف تصبح الفهرس.

حذف Operaخوارزمية نشوئها

1) Start at the root and go up to leaf node containing the key K
2) Find the node n on the path from the root to the leaf node containing K
    A. If n is root, remove K
         a. if root has more than one key, done
         b. if root has only K
            i) if any of its child nodes can lend a node
               Borrow key from the child and adjust child links
            ii) Otherwise merge the children nodes. It will be a new root
         c. If n is an internal node, remove K
            i) If n has at least ceil(m/2) keys, done!
            ii) If n has less than ceil(m/2) keys,
                If a sibling can lend a key,
                Borrow key from the sibling and adjust keys in n and the parent node
                    Adjust child links
                Else
                    Merge n with its sibling
                    Adjust child links
         d. If n is a leaf node, remove K
            i) If n has at least ceil(M/2) elements, done!
                In case the smallest key is deleted, push up the next key
            ii) If n has less than ceil(m/2) elements
            If the sibling can lend a key
                Borrow key from a sibling and adjust keys in n and its parent node
            Else
                Merge n and its sibling
                Adjust keys in the parent node

الناتج:

يتم حذف المفتاح "K"، ويتم استعارة المفاتيح من الأشقاء لضبط القيم في n والعقد الأصلية إذا لزم الأمر.

الملخص

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