شجرة بي بلس

شجرة B + هي شجرة N-ary مع متغير ولكن في كثير من الأحيان عدد كبير من الأطفال في كل عقدة. تتكون شجرة B + من الجذر والعقد والأوراق الداخلية.^[1] قد يكون الجذر إما ورقة أو عقدة مع طفلين أو أكثر.^[2]

مثال بسيط على شجرة B+ يربط المفاتيح من 1 إلى 7 بقيم البيانات d1-d7. تسمح القائمة المرتبطة (باللون الأحمر) بالانتقال السريع في الطلب. العامل المتفرع لهذه الشجرة هو {\ displaystyle b} b = 4.

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

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

تستخدم أنظمة الملفات ReiserFS و NSS و XFS و JFS و ReFS و BFS هذا النوع من الشجرة لفهرسة البيانات الوصفية ؛ يستخدم BFS أيضاً أشجار B + لتخزين الدلائل. يستخدم NTFS أشجار B + لفهرسة بيانات التعريف والأدلة المرتبطة بالأمان. يستخدم EXT4 نطاق الأشجار (بنية بيانات شجرة B + معدلة) لفهرسة امتداد الملف.^[3] أنظمة إدارة قواعد البيانات العلائقية مثل ^[4] IBM DB2 ، Informix ، Microsoft SQL Server ، Oracle 8 ، Sybase ASE ، و SQLite^[5] يدعم هذا النوع من الشجرة لمقاييس الجدول. تدعم أنظمة إدارة قواعد البيانات ذات القيمة الرئيسية مثل CouchDB و Tokyo Cabinet هذا النوع من الأشجار للوصول إلى البيانات.

نظرة عامة

يقيس الترتيب، أو العامل المتفرع، ب لشجرة B + سعة العقد (أي عدد عقد الأطفال) للعقد الداخلية في الشجرة. العدد الفعلي للأطفال لعقدة، المشار إليها هنا باسم م، مقيد للعقد الداخلية بحيث ${\displaystyle [b/2]\leq m\leq b}$. الجذر هو استثناء: يمكن أن يكون لديه عدد قليل من طفلين. على سبيل المثال، إذا كان ترتيب الشجرة B + هو 7 ، فقد يكون لكل عقدة داخلية (باستثناء الجذر) ما بين 4 و 7 أطفال ؛ قد يكون الجذر بين 2 و 7. العقد الورقية ليس لديها أطفال، ولكن مقيدة بحيث يجب أن يكون عدد المفاتيح على الأقل ${\displaystyle [b/2]-1}$ وعلى الأكثر ${\displaystyle b-1}$. في الحالة التي تكون فيها شجرة B + فارغة تقريبًا، فإنها تحتوي فقط على عقدة واحدة، وهي عقدة أوراق. (الجذر هو أيضًا الورقة المفردة، في هذه الحالة). يُسمح لهذه العقدة أن تحتوي على أقل من مفتاح واحد إذا لزم الأمر وعلى الأكثر ${\displaystyle b-1}$.

نوع العقدة	نوع الاطفال	أقل عدد من الاطفال	أقصى عدد من الأطفال	مثال ${\displaystyle b=7}$	مثال ${\displaystyle b=100}$
عقدة الجذر (عندما تكون العقدة الوحيدة في الشجرة)	محفوظات	1	${\displaystyle b-1}$	1–6	1–99
عقدة الجذر	العقد الداخلية أو العقد الورقية	2	b	2–7	2–100
العقدة الداخلية	العقد الداخلية أو العقد الورقية	${\displaystyle \lceil b/2\rceil }$	b	4–7	50–100
عقدة ورقة	محفوظات	${\displaystyle \lceil b/2\rceil -1}$	${\displaystyle b-1}$	3–6	49–99

خوارزميات

بحث

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

موسوعات ذات صلة :

• موسوعة علم الحاسوب