עץ B

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

עץ B מסדר m מקיים את התכונות הבאות:
 לכל צומת יש לכל היותר m ילדים.
 לכל צומת שאינו עלה ואינו השורש, יש לפחות ⌈m/2⌉ ילדים.
 אם השורש אינו עלה, יש לו לפחות 2 ילדים. 
 צומת פנימי עם k ילדים מכיל בדיוק k-1 מפתחות.
 כל העלים בעומק זהה.

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

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

קישורים חיצוניים

 

B, עץ