עץ B Plus

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש
עץ +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 מפתחות ויש להוסיף לו מפתח נוסף, נקבל צומת בעלת 2n+1 בנים שאינה חוקית, לכן נפצל את הצומת לשני צמתים בעלי n מפתחות. הראשון יכיל את n המפתחות עם הערכים הנמוכים, השני יכיל את n המפתחות עם הערכים הגבוהים ואת המפתח האמצעי נעביר לאבא של הצומת. לכל אחד משני הצמתים שנוצרו מהחלוקה יש את מספר המפתחות המינימלי החוקי.

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