עץ B

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה לניווט קפיצה לחיפוש

במדעי המחשב, עץ Bאנגלית: B-tree) הוא מבנה נתונים בצורת עץ, הכללה של עץ חיפוש בינארי, בכך שלכל צומת יכולים להיות יותר מ-2 בנים. עץ B שומר מידע ממוין ומאפשר חיפוש, גישה סדרתית, הוספת איברים ומחיקתם בסיבוכיות לוגרתמית.

עץ B מסדר m מקיים את התכונות הבאות:

  1. לכל קודקוד יש מקסימום m ערכים.
  2. לכל צומת שאינו עלה ואינו השורש, יש לפחות m/2 ילדים.
  3. אם השורש אינו עלה, יש לו לפחות 2 ילדים.
  4. לצומת פנימית עם k ילדים יש בדיוק k-1 ערכים.
  5. כל העלים בעומק זהה.

להבדיל מעצי חיפוש מאוזנים, עץ B מיועד לעבודה יעילה במערכות שקוראות וכותבות בלוקים גדולים של מידע. השימוש בו שכיח במסדי נתונים ובמערכות קבצים.

עץ B+ הוא וריאנט של עץ B. ההבדל בין עץ B לבין עץ B+ הוא בכך שבעץ B+ המפתחות בצמתים הם העתק של המפתחות בעלים, ואילו בעץ B כל איבר נמצא בצומת פנימי או בעלה. בנוסף לכך בעץ B+ יש בדרך כלל רשימה המקשרת בין העלים לאפשר מעבר סדרתי מהיר.


קישורים חיצוניים[עריכת קוד מקור | עריכה]

ויקישיתוף מדיה וקבצים בנושא עץ B בוויקישיתוף
P Computer-science.svg ערך זה הוא קצרמר בנושא מדעי המחשב. אתם מוזמנים לתרום לוויקיפדיה ולהרחיב אותו.