شجرة B+

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

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

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

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

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

p i عندما k i موجود	p i عندما لا يكون k i موجودًا و${\displaystyle i\neq K}$	pK​
يشير إلى سجل بقيمة تساوي k i .	هنا، p i فارغ.	يشير إلى الورقة التالية في الشجرة.

تم تلخيص حدود العقدة في الجدول أدناه: ^{[ 4 ] [ 5 ]}

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

بحسب التعريف، كل قيمة في شجرة B+ هي مفتاح موجود في عقدة طرفية واحدة فقط. يجب أن يكون كل مفتاح قابلاً للمقارنة مباشرةً مع جميع المفاتيح الأخرى، مما يُشكّل ترتيبًا كليًا . ^{[ 6 ]} يُمكّن هذا كل عقدة طرفية من الحفاظ على ترتيب جميع مفاتيحها باستمرار، مما يُمكّن كل عقدة داخلية من إنشاء مجموعة مُرتبة من الفترات التي تُمثّل النطاق المتصل للقيم الموجودة في عقدة طرفية مُعينة. بعد ذلك، تستطيع العقد الداخلية الأعلى في الشجرة إنشاء فتراتها الخاصة، والتي تُجمّع بدورها الفترات الموجودة في عقدها الداخلية الفرعية. في النهاية، يُمثّل جذر شجرة B+ النطاق الكامل للقيم في الشجرة، حيث تُمثّل كل عقدة داخلية فترة فرعية.

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

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

دالة البحث ( k ، الجذر ) هي: let leaf = leaf_search(k، الجذر) for leaf_key in leaf.keys(): if k = leaf_key: return true return false

دالة leaf_search( k , node ) هي: إذا كانت node ورقة: تُرجع node let p = node.children() let l = node.left_sided_intervals() assert${\displaystyle |p|=|l|+1}$ليكن m = p.len() لـ i من 1 إلى m - 1: إذا${\displaystyle k\leq l[i]}$: return leaf_search(k, p[i]) return leaf_search(k, p[m])

لاحظ أن هذه الشفرة الزائفة تستخدم فهرسة المصفوفات بدءًا من 1.

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

تنمو أشجار B+ من الجذور وليس من الأوراق. ^{[ 1 ]}

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

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

ملحوظة:

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

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

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

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

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

تستخدم أنظمة الملفات ReiserFS و NSS و XFS و JFS و ReFS و BFS هذا النوع من الأشجار لفهرسة البيانات الوصفية؛ كما يستخدم BFS أشجار B+ لتخزين الدلائل. ويستخدم NTFS أشجار B+ لفهرسة الدلائل والبيانات الوصفية المتعلقة بالأمان. ويستخدم EXT4 أشجار الامتداد (وهي بنية بيانات معدلة من أشجار B+) لفهرسة امتدادات الملفات. ^{[ 12 ]} ويستخدم APFS أشجار B+ لتخزين عمليات الربط بين معرّفات كائنات نظام الملفات ومواقعها على القرص، ولتخزين سجلات نظام الملفات (بما في ذلك الدلائل)، على الرغم من أن عقد الأوراق في هذه الأشجار تفتقر إلى مؤشرات العقد الشقيقة. ^{[ 13 ]}

تدعم أنظمة إدارة قواعد البيانات العلائقية ، مثل IBM Db2 [ ^{11 ] و} Informix [ ^{11 ] و Microsoft} SQL Server [ ^{11 ] و} Oracle 8 [ ^{11 ] و} Sybase ASE [ ^{11 ] و} SQLite [ ^{14 ] ،} هذا النوع من بنية الشجرة لفهارس الجداول، مع العلم أن كل نظام منها يُطبّق بنية شجرة B+ الأساسية مع بعض الاختلافات والتوسعات. كما تدعم العديد من أنظمة إدارة قواعد بيانات NoSQL ، مثل CouchDB ^{[ 15 ] [ a ]} و Tokyo Cabinet ^{[ 16 ]} ، هذا النوع من بنية الشجرة للوصول إلى البيانات وتخزينها.

يُعدّ البحث عن كائنات في قاعدة بيانات متعددة الأبعاد تُشابه كائن استعلام مُحدد من أكثر الإجراءات استخدامًا، ولكنه في الوقت نفسه مُكلف في هذه الأنظمة. في مثل هذه الحالات، يكون البحث عن أقرب جار باستخدام شجرة B+ مُجديًا. ^{[ 17 ]}