بي - تري

وينبغي عدم الخلط مع التسلسل الثنائي الشجري (بالإنجليزية: Binary tree)‏

B-tree
النوع	tree
سنة التطوير	1972
طور بواسطة	رودولف باير, Edward M. McCreight
تعقيد زمني 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)‏ في علوم الحاسب هي بيانات متسلسلة شجريا tree data structure , ومتوازنه ذاتيا Self-Balancing وهي تساعد على بقاء البيانات مفروزة sorted وتسمح بالبحث searches ووالوصول المتسلسل sequential access والإدراج insertions والمسح deletions في ما يسمى logarithmic time , بي تري هي تعميم للبحث الشجري الثنائي حيث ان الرابط الواحد Node يمكن ان يكون له أكثر من فرعين (Children),(Comer 1979, p. 123). وعلى عكس البيانات المتسلسلة شجريا ومتوازنة ذاتيا، بي - تري هي الحل الامثل للنظم التي تقراء وتكتب الكميات الكبيرة من البيانات، بي تري هي مثال جيد لبنية البيانات للذاكرة الخارجية وهي مستخدمة بكثرة في قواعد البيانات ونظم الملفات.

نظرة عامة

A B-tree (Bayer & McCreight 1972) of order 5 (Knuth 1998).

متغيرات

المصطلح بي تري قد يشير إلى تصميم معين أو أنه قد يشير إلى فئة عامة للتصاميم a General Class of Designes , بمعنى ان بي تري تخزن مفاتيحها في Nodes داخلية ولا تحتاج ان تخزن هذه المفاتيح في سجلات في leaves ,

• في بي + تري
• في بي * تري
• يمكن تحويل بي - تري إلى نظام شجري متسلسل مرتب ثابت وهذا يسمح بسرعة البحث أو البحث المتسارع عن السجلات بالترتيب المفتاحي أو احصاء عدد السجلات بين أي سجلين ويفيدنا في عدة عمليات أخرى.

مصادر ومراجع

عام general

• Bayer، R.؛ McCreight، E. (1972)، "Organization and Maintenance of Large Ordered Indexes" (PDF)، Acta Informatica، ج. 1، ص. 173–189، DOI:10.1007/bf00288683 {{استشهاد}}: الوسيط |ref=harv غير صالح (مساعدة)
• Comer، Douglas (يونيو 1979)، "The Ubiquitous B-Tree"، Computing Surveys، ج. 11، ص. 123–137، DOI:10.1145/356770.356776، ISSN:0360-0300 {{استشهاد}}: الوسيط |ref=harv غير صالح (مساعدة).
• Cormen، Thomas؛ Leiserson، Charles؛ Rivest، Ronald؛ Stein، Clifford (2001)، مقدمة في الخوارزميات (كتاب) (ط. Second)، MIT Press and McGraw-Hill، ص. 434–454، ISBN:0-262-03293-7. Chapter 18: B-Trees.
• Folk، Michael J.؛ Zoellick، Bill (1992)، File Structures (ط. 2nd)، Addison-Wesley، ISBN:0-201-55713-4 {{استشهاد}}: الوسيط |ref=harv غير صالح (مساعدة)
• Knuth، Donald (1998)، Sorting and Searching، فن برمجة الحاسوب (ط. Second)، Addison-Wesley، ج. Volume 3، ISBN:0-201-89685-0 {{استشهاد}}: |المجلد= يحوي نصًّا زائدًا (مساعدة). Section 6.2.4: Multiway Trees, pp. 481–491. Also, pp. 476–477 of section 6.2.3 (Balanced Trees) discusses 2-3 trees.

الابحاث الأصلية

• Bayer، Rudolf؛ McCreight، E. (يوليو 1970)، Organization and Maintenance of Large Ordered Indices، Boeing Scientific Research Laboratories، ج. Mathematical and Information Sciences Report No. 20.
• Bayer، Rudolf (1971)، Binary B-Trees for Virtual Memory، Proceedings of 1971 ACM-SIGFIDET Workshop on Data Description, Access and Control، San Diego, California{{استشهاد}}: صيانة الاستشهاد: مكان بدون ناشر (link).