עץ B Plus

עץ +B לדוגמה

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

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

תיאור פורמלי

כל עץ +B מאופיין על ידי דרגה, שמתארת עד כמה הוא רחב. עץ +B מדרגה $n$ מוגדר כעץ המקיים את התכונות הבאות:

1. כל הערכים נמצאים בעלים, וכל העלים באותה רמה של העץ.
2. לכל צומת פנימי בעץ (פרט אולי לשורש) יש לכל הפחות $n/2$ בנים (אם $n$ אי זוגי, מעגלים כלפי מעלה או מטה את ערך המינימום, אך הוא אחיד עבור כל הצמתים בעץ) ולכל היותר $n$ בנים.
3. בשורש העץ לכל הפחות שני בנים ולכל היותר $n$.
4. צומת פנימי בעל $c$ בנים מכיל $c-1$ אינדקסים הממוינים לפי גודלם, ומקיימים שכל הערכים שנמצאים בתת-העץ ה-i של הצומת קטנים מהאינדקס ה-i וגדולים או שווים לאינדקס ה-i-1 בצומת.

לרוב גם מוסיפים לכל בן בעץ מצביע לאחיו הקרוב, כדי להקל על חיפושי טווח.

הוספה ומחיקה מהעץ

העובדה שיש לצומת פנימי בין $n/2$ ל-$n$ בנים מבטיחה שניתן יהיה לפצל או לאחד צמתים. כאשר לצומת פנימי יש $n$ מפתחות ויש להוסיף לו מפתח נוסף, נקבל צומת בעל $n+1$ בנים שאינו חוקי, לכן נפצל את הצומת לשני צמתים בעלי $n/2$ מפתחות. הראשון יכיל את $n/2$ המפתחות עם הערכים הנמוכים, השני יכיל את $n/2$ המפתחות עם הערכים הגבוהים ואת המפתח האמצעי נעביר לאבא של הצומת. לכל אחד משני הצמתים שנוצרו מהחלוקה יש את מספר המפתחות המינימלי החוקי.

בצורה דומה אם לשני צמתים פנימיים יש $n/2$ מפתחות ניתן למחוק מפתח מאחד מהם על ידי איחוד שניהם לצומת חדש. מחיקת המפתח הופכת את הצומת לבעל $n/2-1$ מפתחות. איחוד הצומת עם שכנו מוסיף $n/2$ מפתחות ומפתח אחד נוסף מועבר מהאב של הצומת השכן. התוצאה היא צומת חדש בעל $n$ מפתחות.

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

מדיה וקבצים בנושא עץ B Plus בוויקישיתוף