مستخدم:PediAki/ملعب3

من https://en.wikipedia.org/wiki/B%2B_tree

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

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

خوارزميات عدل

بحث عدل

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

^ Navathe, Ramez Elmasri, Shamkant B. (2010). Fundamentals of database systems (6th ed.). Upper Saddle River, N.J.: Pearson Education. pp. 652–660. ISBN 978-0-13-608620-8.
^ http://www.seanster.com/BplusTree/BplusTree.html
^ http://www.nobius.org/~dbg/practical-file-system-design.pdf
^ Ramakrishnan Raghu, Gehrke Johannes – Database Management Systems, McGraw-Hill Higher Education (2000), 2nd edition (en) page 267
^ http://sqlite.org/version3.html

[1] Navathe, Ramez Elmasri, Shamkant B. (2010). Fundamentals of database systems (6th ed.). Upper Saddle River, N.J.: Pearson Education. pp. 652–660. ISBN 978-0-13-608620-8.

[2] ttp://www.seanster.com/BplusTree/BplusTree.html

[3] ttp://www.nobius.org/~dbg/practical-file-system-design.pdf

[4] Ramakrishnan Raghu, Gehrke Johannes – Database Management Systems, McGraw-Hill Higher Education (2000), 2nd edition (en) page 267

[5] ttp://sqlite.org/version3.html

[1]

[2]

[3]

[4]

[5]