شجرة بي بلس

صفات

من جهة ثانية، يقيس الترتيب أو عامل التفرع لشجرة بي بلس سعة العقد الداخلية، أي الحد الأقصى المسموح به لعدد العقد الفرعية المباشرة. هذه القيمة ثابتة على الشجرة بأكملها. بالنسبة لشجرة بي بلس من الدرجة b مع مستويات من الفهرس:

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

ذاكرة الوصول العشوائي غير القابلة للتحويل

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

• انظر كذلك
• شجرة البحث الثنائية
• شجرة B
• خوارزمية فرق تسد
• مراجع
• روابط خارجية
• شجرة B+ في بايثون، تُستعمل لتنفيذ قائمة

بنية المؤشر

pi: المؤشر عند فهرس العقدة i الذي يبدأ من الصفر.

ki: مفتاح البحث عند فهرس العقدة i الذي يبدأ من الصفر.

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

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

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

أشجار B+-الجلب المسبق الكسري

علاوةً على ذلك، هياكل الفهرس التي تراعي ذاكرة التخزين المؤقت لقواعد بيانات الذاكرة الرئيسية

نحو أشجار pB+ في الميدان: التنفيذات والخيارات والأداء

تحسين عام 2019 عن السابق

• تنفيذ شجرة B+ المستندة إلى التدفق كمكتبة قالب C++
• تنفيذ شجرة B+ JavaScript مفتوحة المصدر
• تنفيذ Perl لأشجار B+

دالة بحث (k, root) هي

• let leaf = leaf_search(k, root)
• for leaf_key in leaf.keys:
• if k = leaf_key:
• return صحيح
• return خاطئ

الحذف

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

في المدخل L الذي نرغب في إزالته:

إذا كان L ممتلئًا إلى النصف على الأقل، فقد تم ذلك

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

ملاحظة: قد ينتشر الدمج إلى الجذر، مما يعني انخفاض الارتفاع.

علاوةً على ذلك، إذا كان L يحتوي على إدخالات d-1 فقط، فحاول إعادة التوزيع، عن طريق الاقتراض من العقدة الشقيقة (العقدة المجاورة التي لها نفس العقدة الأصلية مثل L). بعد إعادة توزيع العقدتين الشقيقتين، يجب تحديث العقدة الأصلية، لتعكس هذا التغيير. يجب أن يأخذ مفتاح الفهرس الذي يشير إلى العقدة الشقيقة الثانية أصغر قيمة لتلك العقدة ليكون مفتاح الفهرس.

أنظمة الملفات

إضافةً إلى ذلك، تستعمل أنظمة الملفات ReiserFS و NSS و XFS وJFS وReFS و BFS هذا النوع من الأشجار بهدف فهرسة البيانات الوصفية؛ ويستعمل BFS كذلك أشجار بي بلس لتخزين الدلائل. يستعمل نظام NTFS أشجار بي بلس لفهرسة البيانات التعريفية المتعلقة بالدليل والأمان. كما يستعمل EXT4 أشجار المدى (هيكل بيانات شجرة بي بلس معدل) لفهرسة مدى الملف. في حين يستعمل APFS أشجاربي بلس لتخزين التعيينات من معرفات كائنات نظام الملفات إلى مواقعها على القرص، وتخزين سجلات نظام الملفات (بما في ذلك الدلائل)، على الرغم من أن العقد الورقية لهذه الأشجار تفتقر إلى مؤشرات شقيقة.

المسافة

من جهة ثانية، يتم استخدام شجرة بي بلس بكفاءة لإنشاء طريقة بحث مفهرسة تسمى أي ديستانسiDistance. حيث يبحث آي ديستانس عن k من أقرب الجيران (kNN) في المساحات المترية ذات الأبعاد العالية. ويتم تقسيم البيانات في تلك المساحات ذات الأبعاد العالية استنادًا إلى استراتيجيات المساحة أو التقسيم، وكل قسم لديه قيمة فهرس قريبة فيما يتعلق بالقسم. ومن هنا، يمكن تنفيذ هذه النقاط بكفاءة باستخدام شجرة بي بلس، وبالتالي، يتم تعيين الاستعلامات إلى بحث محدد الأبعاد. وبعبارة أخرى، يمكن اعتبار تقنية آي ديستنانس بمثابة طريقة لتسريع المسح المتسلسل. بدلاً من مسح السجلات من البداية إلى نهاية ملف البيانات، حيث يبدأ آي ديستانس المسح من البقع التي يمكن الحصول على أقرب الجيران منها في وقت مبكر باحتمالية عالية جدًا.

ملاحظات فهرس شجرة B+ للدكتور مونج

تأثير حجم العقدة على أداء أشجار B+ الواعية للذاكرة المؤقتة

تقييم أداء أشجار CSB+ على البنيات متعددة الخيوط

حدود العقدة

يتم تلخيص حدود العقدة في الجدول أدناه:

الفواصل الزمنية في العقد الداخلية

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

من جانب آخر، ومن أجل أن يتم الاحتفاظ بمعلومات الفاصل الزمني المتكرر هذه، يجب أن تحتوي العقد الداخلية كذلك على نسخ من المفاتيح لـــ يمثل العنصر الأصغر ضمن الفاصل الذي يغطيه الطفل ذو الفهرس (والذي يمكن أن يكون في حد ذاته عقدة داخلية أو ورقة). حيث يمثل العدد الفعلي للأطفال لعقدة داخلية معينة.

وإلا، قبل إدخال السجل الجديد

العقدة الأصلية لديها أغراض

تقسيم العقدة.

دالة leaf_search(k, node) هي

• if node is a leaf:
• return node
• let p = node.children
• let l = node.left_sided_intervals
• assert

let m = p.len

• for i from 1 to m - 1:
• if :
• return leaf_search(k, p[i])
• return leaf_search(k, p[m])
• لاحظ أن هذا الكود الزائف يستعمل فهرسة المصفوفة القائمة على 1.

يبحث

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

يتطلب العثور على سجل العمليات

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

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

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

كذلك، لا يؤثر أي تغيير في البنية على الأداء بسبب خصائص الشجرة المتوازنة.

ومن جهة أخرى، يتوسع هيكل الشجرة بي بلس/ينكمش مع زيادة/نقصان عدد السجلات. لا توجد قيود على حجم الأشجار بي بلس. وبالتالي زيادة قابلية استخدام نظام قاعدة البيانات.

الخوارزميات

وفي هذا الصدد، يتطلب تنفيذ استعلام نطاق يحتوي على k عنصرًا تحدث داخل نطاق العمليات

تتطلب إزالة سجل العمليات (الموجود سابقًا)

تنفيذات Java/C#/Python لأشجار B+

• شجرة B+ في لغة C# وهياكل البيانات ذات الصلة "قائمة A"
• شجرة B+Tree مبنية على ملف في C# مع دعم الخيوط وMVCC
• شجرة B+ سريعة شبه ثابتة في الذاكرة في TypeScript/JavaScript، ترخيص MIT
• شجرة JavaScript B+، ترخيص MIT

أشجار B(+)-الغافلة عن ذاكرة التخزين المؤقت

• قوة أشجار B: تنفيذ شجرة B+ في CouchDB
• تصور شجرة B+
• ب + - الأشجار بواسطة كيرتو بولاري-مالمي
• هياكل البيانات أشجار B وأشجار B+
• التنفيذات
• تنفيذ شجرة B+ التفاعلية في C

تطبيق

من جهة ثانية، يمكن كذلك استخدام أشجار بي بلس للبيانات المخزنة في ذاكرة الوصول العشوائي (رام RAM). وفي هذه الحالة، سيكون الاختيار المعقول لحجم الكتلة هو حجم خط ذاكرة التخزين المؤقت للمعالج.

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

التطبيقات

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

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

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

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

إدراج

ومن ناحية أخرى، قم بإجراء بحث لتحديد العقدة التي يجب أن ينتقل إليها السجل الجديد.

ومن جهة أخرى، إذا لم تكن العقدة ممتلئة (على الأكثر (المدخلات بعد الإدراج)، قم بإضافة السجل.

أنظمة قواعد البيانات

من جانب آخر، أنظمة إدارة قواعد البيانات العلائقية مثل IBM Db2 ، Informix ، Microsoft SQL Server ، Oracle 8 ، Sybase ASE ، و SQLite   يدعم هذا النوع من الأشجار لمؤشرات الجدول، على الرغم من أن كل نظام من هذه الأنظمة ينفذ بنية الشجرة الأساسية بي بلس مع الاختلافات والامتدادات. الكثير من أنظمة إدارة قواعد البيانات NoSQL مثل CouchDB   وخزانة طوكيو تدعم كذلك هذا النوع من الأشجار للوصول إلى البيانات وتخزينها.

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

تنفيذ شجرة B+ التفاعلية في C++

تنفيذ شجرة B+ المستندة إلى الذاكرة كمكتبة قالب C++

التحميل بالجملة

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

في هذا الإطار، قد يؤدي هذا الإجراء، بدوره، إلى تقسيم صفحة الفهرس اليمنى إلى خطوة واحدة أقرب إلى الجذر؛

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

من جانب آخر، عندما تمتلئ صفحة الفهرس اليمنى فوق مستوى الورقة، يتم تقسيمها؛

في هذا الإطار، تحدث الانقسامات فقط على المسار الأيمن من الجذر إلى مستوى الورقة.

ومن جهة أخرى، الخطوة الأولى هي فرز إدخالات البيانات بحسب مفتاح البحث بترتيب تصاعدي.

عندما يمتلئ الجذر، نقوم بتقسيم الجذر وإنشاء صفحة جذر جديدة.

من جانب آخر، استمر في إدراج الإدخالات في صفحة الفهرس الموجودة في أقصى اليمين فوق مستوى الورقة، حتى تتم فهرسة جميع الإدخالات.

ملحوظة:

تاريخ

البنية

كذلك، لا توجد ورقة بحثية واحدة تقدم مفهوم شجرة بي بلس. بدلاً من ذلك، يتم طرح فكرة الاحتفاظ بجميع البيانات في العقد الورقية بشكل متكرر باعتبارها متغيرًا مثيرًا للاهتمام لشجرة بي، والتي قدمها كل من: R. Bayer و E. McCreight. ويلاحظ علم الحاسوب الأمريكي دوغلاس كومر في دراسة مبكرة لأشجار بي (والتي تغطي كذلك أشجار بي بلس) أن شجرة بي بلس كانت تستعمل في برنامج الوصول إلى البيانات VSAM الخاص بشركة IBM، ويشير إلى مقال نشرته شركة IBM في سنة 1973م.

العقدة الجديدة لديها أغراض

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