بي - تري

وينبغي عدم الخلط مع التسلسل الثنائي الشجري (بالإنجليزية: 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 ,

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

مصادر ومراجع
  1. Counted B-Trees, retrieved 2010-01-25 نسخة محفوظة 19 نوفمبر 2017 على موقع واي باك مشين.
    عام general
    • Bayer, R.; McCreight, E. (1972), "Organization and Maintenance of Large Ordered Indexes" (PDF), Acta Informatica, 1, صفحات 173–189, doi:10.1007/bf00288683 الوسيط |CitationClass= تم تجاهله (مساعدة); الوسيط |separator= تم تجاهله (مساعدة)CS1 maint: ref=harv (link)
    • Comer, Douglas (June 1979), "The Ubiquitous B-Tree", Computing Surveys, 11, صفحات 123–137, doi:10.1145/356770.356776, ISSN 0360-0300 الوسيط |CitationClass= تم تجاهله (مساعدة); الوسيط |separator= تم تجاهله (مساعدة)CS1 maint: ref=harv (link).
    • Cormen, Thomas; Leiserson, Charles; Rivest, Ronald; Stein, Clifford (2001), مقدمة في الخوارزميات (كتاب) (الطبعة Second), MIT Press and McGraw-Hill, صفحات 434–454, ISBN 0-262-03293-7 الوسيط |CitationClass= تم تجاهله (مساعدة); الوسيط |separator= تم تجاهله (مساعدة)CS1 maint: ref=harv (link). Chapter 18: B-Trees.
    • Folk, Michael J.; Zoellick, Bill (1992), File Structures (الطبعة 2nd), Addison-Wesley, ISBN 0-201-55713-4 الوسيط |CitationClass= تم تجاهله (مساعدة); الوسيط |separator= تم تجاهله (مساعدة)CS1 maint: ref=harv (link)
    • Knuth, Donald (1998), Sorting and Searching, Volume 3 (الطبعة Second), Addison-Wesley, ISBN 0-201-89685-0 الوسيط |CitationClass= تم تجاهله (مساعدة); الوسيط |separator= تم تجاهله (مساعدة)CS1 maint: ref=harv (link). 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. (July 1970), Organization and Maintenance of Large Ordered Indices, Mathematical and Information Sciences Report No. 20, Boeing Scientific Research Laboratories الوسيط |CitationClass= تم تجاهله (مساعدة); الوسيط |separator= تم تجاهله (مساعدة)CS1 maint: ref=harv (link).
    • Bayer, Rudolf (1971), Binary B-Trees for Virtual Memory, San Diego, California الوسيط |CitationClass= تم تجاهله (مساعدة); الوسيط |separator= تم تجاهله (مساعدة)CS1 maint: ref=harv (link).
    في كومنز صور وملفات عن: بي - تري
    • بوابة عقد 1970
    This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.