شجرة بي بلس

شجرة بي بلس
النوع	شجرة (هيكل بيانات)
تعقيد زمني in رمز O الكبير
	المتوسط	أسوء حالة
المساحة	O(n)	O(n)
بحث	O(log n)	O(log n)
ادراج	O(log n)	O(log n)
مسح	O(log n)	O(log n)

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

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

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

تاريخ

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

البنية

بنية المؤشر

تنسيق عقدة الشجرة بي بلس حيث K=4. (p_i يمثل المؤشرات، k_i يمثل مفاتيح البحث).

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

• إذا كانت ${\textstyle k_{i}}$ موجودة في أي عقدة في شجرة بي بلس، إذن k_i-1 تكون موجودة في تلك العقدة حيث $i\geq 1$ .
• جميع عقد الأوراق لها نفس عدد الأسلاف (أي أنها كلها على نفس العمق).

يتم تلخيص خصائص المؤشر للعقد في الجداول أدناه:

• K: الحد الأقصى لعدد مفاتيح البحث المحتملة لكل عقدة في شجرة بي بلس. (هذه القيمة ثابتة على مستوى الشجرة بأكملها).
• pi: المؤشر عند فهرس العقدة i الذي يبدأ من الصفر.
• ki: مفتاح البحث عند فهرس العقدة i الذي يبدأ من الصفر.

بنية مؤشر العقدة الداخلية

	p0	pi
متى	k0 موجود	ki-1 و ki موجودان	ki-1 موجود، و ki غير موجود	ki-1 و ki غير موجودين
P : يشير إلى شجرة فرعية تحتوي على جميع مفاتيح البحث	P < k0 .	ki-1 ≤ P < ki .	P ≥ ki-1 .	pi فارغ.

بنية مؤشر عقدة الورقة

pi عندما يكون ki موجودًا	pi عندما لا يكون ki موجودًا و $i\neq K$	pK
يشير إلى سجل بقيمة تساوي ki .	هنا، pi فارغ.	يشير إلى الورقة التالية في الشجرة.

حدود العقدة

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

نوع العقدة	عدد المفاتيح		عدد العقد الفرعية
	الحد الأدنى	الأعلى	الحد الأدنى	الأعلى
العقدة الجذرية (عندما تكون عقدة ورقية)	0	K	0	0
العقدة الجذرية (عندما تكون عقدة داخلية)	1	K	2	$K+1$
العقدة الداخلية	$\lfloor K/2\rfloor$	K	$\lceil (K+1)/2\rceil \equiv \lfloor K/2\rfloor +1$	$K+1$
عقدة ورقية	$\lceil K/2\rceil$	K	0	0

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

مثال بسيط لشجرة بي بلس يربط المفاتيح من 1 إلى 7 بقيم البيانات d ₁ -d ₇ . تسمح القائمة المرتبطة (باللون الأحمر) بالتنقل السريع حسب الترتيب. عامل التفرع لهذه الشجرة على وجه الخصوص هو $b$ =4. تم تلوين كلا المفتاحين في العقد الورقية والداخلية باللون الرمادي هنا.

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

ومن أجل أن يتم الاحتفاظ بمعلومات الفاصل الزمني المتكرر هذه، يجب أن تحتوي العقد الداخلية أيضًا على $m-1$ نسخ من المفاتيح $l_{i}$ لـــ $i\in [1,m-1]$ يمثل العنصر الأصغر ضمن الفاصل الذي يغطيه الطفل ذو الفهرس i (والذي يمكن أن يكون في حد ذاته عقدة داخلية أو ورقة). حيث يمثل m العدد الفعلي للأطفال لعقدة داخلية معينة.

صفات

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

• الحد الأقصى لعدد السجلات المخزنة هو $n_{\max }=b^{h}-b^{h-1}$
• الحد الأدنى لعدد السجلات المخزنة هو $n_{\min }=2\left\lceil {\tfrac {b}{2}}\right\rceil ^{h-1}-2\left\lceil {\tfrac {b}{2}}\right\rceil ^{h-2}$
• الحد الأدنى لعدد المفاتيح هو $n_{\mathrm {kmin} }=2\left\lceil {\tfrac {b}{2}}\right\rceil ^{h-1}-1$
• الحد الأقصى لعدد المفاتيح هو $n_{\mathrm {kmax} }=b^{h}-1$
• المساحة المطلوبة لتخزين الشجرة هي $O(n)$
• يتطلب إدراج سجل العمليات $O(\log _{b}n)$
• يتطلب العثور على سجل العمليات $O(\log _{b}n)$
• تتطلب إزالة سجل العمليات (الموجود سابقًا) $O(\log _{b}n)$
• يتطلب تنفيذ استعلام نطاق يحتوي على k عنصرًا تحدث داخل نطاق العمليات$O(\log _{b}n+k)$
• يتوسع هيكل الشجرة بي بلس/ينكمش مع زيادة/نقصان عدد السجلات. لا توجد قيود على حجم الأشجار بي بلس. وبالتالي زيادة قابلية استخدام نظام قاعدة البيانات.
• لا يؤثر أي تغيير في البنية على الأداء بسبب خصائص الشجرة المتوازنة.
• يتم تخزين البيانات في العقد الورقية، ويساعد المزيد من التفرع للعقد الداخلية على تقليل ارتفاع الشجرة، وبالتالي تقليل وقت البحث. ونتيجة لذلك، فإنه يعمل بشكل جيد في أجهزة التخزين الثانوية.
• يصبح البحث بسيطًا للغاية لأن جميع السجلات يتم تخزينها فقط في العقدة الورقية ويتم فرزها بشكل تسلسلي في القائمة المرتبطة.
• يمكننا استرجاع استرجاع النطاق أو الاسترجاع الجزئي باستخدام شجرة بي بلس. يتم جعل هذا الأمر أسهل وأسرع من خلال عبور بنية الشجرة. تجعل هذه الميزة هيكل الشجرة بي بلس قابلاً للتطبيق في العديد من طرق البحث.

الخوارزميات

يبحث

نحن نبحث عن القيمة k في شجرة بي بلس. هذا يعني أنه بداية من الجذر، نبحث عن الورقة التي قد تحتوي على القيمة k. عند كل عقدة، نحدد العقدة الداخلية التي يجب متابعتها. تحتوي عقدة شجرة بي بلس الداخلية على ما لا يزيد عن $m\leq b$ الأطفال، حيث يمثل كل واحد منهم فترة زمنية فرعية مختلفة. نقوم باختيار الطفل المناسب من خلال بحث خطي عن مدخلات m، ثم عندما نصل أخيرًا إلى ورقة، نقوم بإجراء بحث خطي عن عناصرها n للحصول على المفتاح المطلوب. لأننا نعبر فرعًا واحدًا فقط من جميع الأطفال في كل درجة من درجات الشجرة، فإننا نحقق $O(\log N)$ وقت التشغيل، حيث N هو العدد الإجمالي للمفاتيح المخزنة في أوراق شجرة بي بلس.

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

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

دالة leaf_search(k, node) هي
    if node is a leaf:
        return node
    let p = node.children()
    let l = node.left_sided_intervals()
    assert $|p|=|l|+1$
    let m = p.len()
    for i from 1 to m - 1:
        if $k\leq l[i]$:
            return leaf_search(k, p[i])
    return leaf_search(k, p[m])

لاحظ أن هذا الكود الزائف يستخدم فهرسة المصفوفة القائمة على 1.

إدراج

• قم بإجراء بحث لتحديد العقدة التي يجب أن ينتقل إليها السجل الجديد.
• إذا لم تكن العقدة ممتلئة (على الأكثر $b-1$ (المدخلات بعد الإدراج)، قم بإضافة السجل.
• وإلا، قبل إدخال السجل الجديد
  • تقسيم العقدة.
    • العقدة الأصلية لديها $\lceil (K+1)/2\rceil$ أغراض
    • العقدة الجديدة لديها $\lfloor (K+1)/2\rfloor$ أغراض
  • ينسخ $\lceil (K+1)/2\rceil$ - المفتاح إلى الأصل، ثم أدخل العقدة الجديدة إلى الأصل.
  • كرر ذلك حتى يتم العثور على أحد الوالدين الذي لا يحتاج إلى الانقسام.
  • أدخل السجل الجديد في العقدة الجديدة.
• إذا انقسم الجذر، تعامل معه كما لو كان له أصل فارغ وانقسم كما هو موضح أعلاه.

تنمو الأشجار من النوع بي بلس عند الجذور وليس عند الأوراق.

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

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

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

ملحوظة:

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

الحذف

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

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

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

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

حذف شجرة بي بلس

تطبيق

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

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

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

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

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

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

التطبيقات

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

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

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

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

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

المسافة

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

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

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

انظر أيضًا

• شجرة البحث الثنائية
• شجرة B
• خوارزمية فرق تسد

روابط خارجية

• شجرة B+ في بايثون، تُستخدم لتنفيذ قائمة
• ملاحظات فهرس شجرة B+ للدكتور مونج
• تقييم أداء أشجار CSB+ على البنيات متعددة الخيوط
• تأثير حجم العقدة على أداء أشجار B+ الواعية للذاكرة المؤقتة
• أشجار B+-الجلب المسبق الكسري
• نحو أشجار pB+ في الميدان: التنفيذات والخيارات والأداء
• هياكل الفهرس التي تراعي ذاكرة التخزين المؤقت لقواعد بيانات الذاكرة الرئيسية
• أشجار B(+)-الغافلة عن ذاكرة التخزين المؤقت
• قوة أشجار B: تنفيذ شجرة B+ في CouchDB
• تصور شجرة B+
• ب + - الأشجار بواسطة كيرتو بولاري-مالمي
• هياكل البيانات أشجار B وأشجار B+

التنفيذات

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