עץ B
קפיצה לניווט
קפיצה לחיפוש
במדעי המחשב, עץ B (באנגלית: B-tree) הוא מבנה נתונים בצורת עץ, הכללה של עץ חיפוש בינארי, בכך שלכל צומת יכולים להיות יותר מ-2 בנים. עץ B שומר מידע ממוין (לפי מפתח) ומאפשר חיפוש, גישה סדרתית, הוספת איברים ומחיקתם בסיבוכיות לוגרתמית.
עץ B מסדר m מקיים את התכונות הבאות:
- לכל צומת יש לכל היותר m ילדים.
- לכל צומת שאינו עלה ואינו השורש, יש לפחות ⌈m/2⌉ ילדים.
- אם השורש אינו עלה, יש לו לפחות 2 ילדים.
- צומת פנימי עם k ילדים מכיל בדיוק k-1 מפתחות.
- כל העלים בעומק זהה ואינם מכילים מידע.
להבדיל מעצי חיפוש מאוזנים, עץ B מיועד לעבודה יעילה במערכות שקוראות וכותבות בלוקים גדולים של מידע. השימוש בו שכיח במסדי נתונים ובמערכות קבצים.
עץ B+ הוא וריאנט של עץ B. ההבדל בין עץ B לבין עץ B+ הוא בכך שבעץ B+ המפתחות בצמתים הם העתק של המפתחות בעלים, ואילו בעץ B כל איבר נמצא בצומת פנימי או בעלה. בנוסף לכך בעץ B+ יש בדרך כלל רשימה המקשרת בין העלים לאפשר מעבר סדרתי מהיר.
| מבני נתונים | ||
|---|---|---|
| מבנים מופשטים | רשימה • מחסנית • קבוצה • רב קבוצה • תור • דו-תור • תור עדיפויות • מילון • מחרוזת • איחוד קבוצות זרות | |
| מימושים ליניאריים | מערך • מערך משונן • טבלת גיבוב • רשימה מקושרת • רשימת דילוגים • חוצץ | |
| גרפים ועצים | ערימה (בינארית • בינומית • פיבונאצ'י) • עץ חיפוש (עץ אדום שחור • עץ 2-3 • עץ 2-3-4) • עץ סיפות • עץ B • עץ +B • עץ AVL • עץ Splay • עץ BSP • עץ kd • עץ R • Trie • טריי X מהיר • טריי y מהיר• עץ WAVL | |
| הסתברותיים | מסנן בלום | |
קישורים חיצוניים
