شجرة B+: البحث والإدراج والحذف Operaستعقد
سارة تشين
⚡ ملخص ذكي
شجرة B+ هي فهرس ديناميكي متعدد المستويات يخزن مؤشرات البيانات فقط عند العقد الطرفية المرتبطة، مما يجعل عمليات البحث دقيقة وسريعة. يتناول هذا الشرح قواعد شجرة B+، وكيف تختلف عن شجرة B، وعمليات البحث والإضافة والحذف.
ما هي شجرة B+؟
A ب + شجرة تُستخدم شجرة B+ بشكل أساسي لتنفيذ الفهرسة الديناميكية على مستويات متعددة. وبالمقارنة مع شجرة B-، فإن شجرة B+ تخزن مؤشرات البيانات فقط عند العقد الطرفية للشجرة، مما يجعل عملية البحث أكثر دقة وسرعة.
قواعد شجرة B+
إليكم القواعد الأساسية لشجرة B+.
- تستخدم الأوراق لتخزين سجلات البيانات.
- يتم تخزين السجلات في العقد الداخلية للشجرة.
- إذا كانت قيمة المفتاح المستهدف أقل من قيمة العقدة الداخلية، فسيتم اتباع المؤشر الموجود على يسارها مباشرة.
- إذا كانت قيمة المفتاح المستهدف أكبر من أو تساوي قيمة العقدة الداخلية، فسيتم اتباع المؤشر الموجود على يمينها مباشرة.
- يحتوي الجذر على طفلين على الأقل.
لماذا نستخدم شجرة B+؟
فيما يلي أسباب استخدام شجرة B+:
- تُستخدم المفاتيح بشكل أساسي للمساعدة في البحث من خلال توجيه المستخدم إلى الصفحة المناسبة.
- تستخدم شجرة B+ "عامل التعبئة" لإدارة الزيادة والنقصان في الشجرة.
- في أشجار B+، يمكن بسهولة وضع العديد من المفاتيح على صفحة الذاكرة لأنها لا تحتوي على البيانات المرتبطة بالعقد الداخلية. ولذلك، فإنه سيتم الوصول بسرعة إلى بيانات الشجرة الموجودة على العقدة الطرفية.
- لا يتطلب المسح الكامل الشامل لجميع العناصر سوى تمريرة خطية واحدة لأن جميع العقد الورقية لشجرة B+ مرتبطة ببعضها البعض.
شجرة B+ مقابل شجرة B
فيما يلي الاختلافات الرئيسية بين شجرة B+ وشجرة B.
| ب + شجرة | شجرة ب |
|---|---|
| يمكن تكرار مفاتيح البحث. | لا يمكن أن تكون مفاتيح البحث زائدة عن الحاجة. |
| يتم حفظ البيانات فقط على العقد الورقية. | يمكن لكل من العقد الطرفية والعقد الداخلية تخزين البيانات. |
| البيانات المخزنة على العقدة الطرفية تجعل البحث أكثر دقة وأسرع. | عملية البحث بطيئة بسبب البيانات المخزنة على العقد الطرفية والداخلية. |
| الحذف ليس صعباً، حيث تتم إزالة العنصر فقط من عقدة طرفية. | يعد حذف العناصر عملية معقدة وتستغرق وقتًا طويلاً. |
| العقد الورقية المرتبطة تجعل البحث فعالاً وسريعًا. | لا يمكنك ربط العقد الورقية. |
البحث Operaالإنتاج
في شجرة B+، يعد البحث أحد أسهل الإجراءات التي يمكن تنفيذها ويعطي نتائج سريعة ودقيقة.
يتم تطبيق خوارزمية البحث التالية:
- للعثور على السجل المطلوب، تحتاج إلى تنفيذ بحث ثنائي على السجلات المتوفرة في الشجرة.
- في حالة وجود تطابق تام مع مفتاح البحث، يتم إرجاع السجل المقابل للمستخدم.
- في حالة عدم العثور على المفتاح الدقيق عن طريق البحث في العقدة الأصلية أو الحالية أو العقدة الورقية، فسيتم عرض رسالة "لم يتم العثور عليه" للمستخدم.
- ويمكن إعادة تشغيل عملية البحث للحصول على نتائج أفضل وأكثر دقة.
البحث 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. If 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 عقد، ويتم إضافة العناصر الثلاثة الأولى، وهي 1 و4 و6، في المواقع المناسبة في العقد.
- القيمة التالية في سلسلة البيانات هي 12، والتي يجب أن تُضاف إلى الشجرة.
- لتحقيق ذلك، قسّم العقدة وأضف 6 كعنصر مؤشر.
- الآن، يتم إنشاء تسلسل هرمي أيمن للشجرة، ويتم تعديل قيم البيانات المتبقية وفقًا لذلك بواسطة keeping مع مراعاة القواعد المطبقة للقيم المساوية أو الأكبر من مقابل عقد المفتاح والقيمة على اليمين.
حذف Operaالإنتاج
إن تعقيد عملية الحذف في شجرة B+ يتجاوز تعقيد وظيفة الإدراج والبحث.
يمكن تطبيق الخوارزمية التالية أثناء حذف عنصر من شجرة B+:
- أولاً، نحتاج إلى تحديد موقع إدخال الورقة في الشجرة الذي يحتوي على المفتاح والمؤشر، ثم حذف إدخال الورقة من الشجرة إذا كانت الورقة تستوفي الشروط الدقيقة لحذف السجل.
- في حالة استيفاء العقدة الطرفية لعامل الرضا المتمثل في كونها نصف ممتلئة فقط، فإن العملية تكتمل؛ وإلا فإن العقدة الطرفية تحتوي على الحد الأدنى من الإدخالات ولا يمكن حذفها.
- يمكن للعقد المرتبطة الأخرى على اليمين واليسار إخلاء أي مدخلات ثم نقلها إلى العقدة الطرفية. إذا لم تتحقق هذه المعايير، فيجب دمج العقدة الطرفية مع العقدة المرتبطة بها في التسلسل الهرمي للشجرة.
- عند دمج عقدة طرفية مع جيرانها على اليمين أو اليسار، يتم حذف إدخالات القيم في العقدة الطرفية أو الجار المرتبط الذي يشير إلى العقدة ذات المستوى الأعلى.
يوضح المثال أعلاه الإجراء اللازم لإزالة عنصر من شجرة B+ ذات ترتيب معين.
- أولاً، يتم تحديد المواقع الدقيقة للعنصر المراد حذفه في الشجرة.
- هنا، لا يمكن تحديد العنصر المراد حذفه بدقة إلا على مستوى الورقة وليس على مستوى الفهرس. وبالتالي، يمكن حذف العنصر دون التأثير على قواعد الحذف، وهي قيمة المفتاح الأدنى.
- في المثال أعلاه، علينا حذف 31 من الشجرة.
- نحتاج إلى تحديد حالات الرقم 31 في الفهرس والورقة.
- نلاحظ أن الرقم 31 متوفر على مستوى كل من عقدة الفهرس وعقدة الورقة. لذا، نقوم بحذفه من كلا الحالتين.
- لكن علينا ملء الفهرس الذي يشير إلى 42. سننظر الآن إلى العنصر الفرعي الأيمن تحت 25 ونأخذ أصغر قيمة ونضعها كفهرس. وبما أن 42 هي القيمة الوحيدة الموجودة، فستصبح هي الفهرس.
حذف Operaخوارزمية نشوئها
1) Start at the root and go up to the 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 وعقدها الأصلية إذا لزم الأمر.
