עץ B Plus

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

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

עץ B+ מוגדר לפי דרגה n שמגדירה כמה הוא רחב. כל הערכים שמורים בעלים והעלים כולם באותה רמה. צומת פנימי (למעט אולי השורש) חייב להכיל לפחות סביב n/2 בנים ולמקסימום n בנים. השורש חייב להכיל לפחות שני בנים. צומת פנימי שיש לו c בנים כולל c-1 אינדקסים שממוינים לפי גודל. האינדקסים מחלקים את טווחי הערכים כך שכל תת-עץ מכיל ערכים בתחום מוגדר. כדי להקל על חיפושי טווח מוסיפים לעתים מצביע לאח (אחיה) של כל בן.

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

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

בכל עץ יש דרגה n שמגדירה כמה ילדים יש לצמתים. כל העלים באותה רמה. צומת פנימי בדרך כלל צריך לפחות חצי מהילדים האפשריים ועד למספר המקסימלי n. לשורש חייבים להיות לפחות שני ילדים. צומת עם c ילדים מכיל c-1 אינדקסים שממוינים. לפעמים מחברים כל בן לאח שלו כדי לחפש טווחים בקלות.

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