B+ Tree הוא הרחבה של B Tree המאפשרת פעולות הכנסה, מחיקה וחיפוש יעילות.
ב-B Tree, מפתחות ורשומות יכולים להיות מאוחסנים בצמתים הפנימיים וגם בצמתים העלים. בעוד שבעץ B+, ניתן לאחסן רשומות (נתונים) רק בצמתי העלים בעוד שצמתים פנימיים יכולים לאחסן רק את ערכי המפתח.
צמתי העלים של עץ B+ מקושרים יחד בצורה של רשימות מקושרות בודדות כדי להפוך את שאילתות החיפוש ליעילות יותר.
B+ Tree משמשים לאחסון כמות הנתונים הגדולה שלא ניתן לאחסן בזיכרון הראשי. בשל העובדה שגודל הזיכרון הראשי תמיד מוגבל, הצמתים הפנימיים (מפתחות גישה לרשומות) של עץ B+ מאוחסנים בזיכרון הראשי ואילו צמתי עלים מאוחסנים בזיכרון המשני.
הצמתים הפנימיים של עץ B+ נקראים לעתים קרובות צמתי אינדקס. עץ B+ מסדר 3 מוצג באיור הבא.
יתרונות B+ Tree
- ניתן להביא רשומות במספר שווה של גישה לדיסק.
- גובה העץ נשאר מאוזן ופחות בהשוואה לעץ B.
- אנו יכולים לגשת לנתונים המאוחסנים בעץ B+ ברצף וגם ישירות.
- מפתחות משמשים לאינדקס.
- שאילתות חיפוש מהירות יותר מכיוון שהנתונים מאוחסנים רק בצמתי העלים.
B Tree VS B+ Tree
| SN | B עץ | B+ עץ |
|---|---|---|
| 1 | לא ניתן לאחסן שוב ושוב מקשי חיפוש. | מפתחות חיפוש מיותרים יכולים להיות קיימים. |
| 2 | ניתן לאחסן נתונים בצמתים עלים כמו גם בצמתים פנימיים | ניתן לאחסן נתונים רק בצמתי העלים. |
| 3 | חיפוש אחר נתונים מסוימים הוא תהליך איטי יותר מכיוון שניתן למצוא נתונים על צמתים פנימיים כמו גם על צמתים עלים. | החיפוש מהיר יותר באופן יחסי מכיוון שניתן למצוא נתונים רק בצמתי העלים. |
| 4 | מחיקה של צמתים פנימיים היא כל כך מסובכת וגוזלת זמן. | המחיקה לעולם לא תהיה תהליך מורכב מכיוון שאלמנט תמיד יימחק מצמתי העלים. |
| 5 | לא ניתן לקשר צמתים עלים. | צמתי עלים מקושרים יחד כדי להפוך את פעולות החיפוש ליעילות יותר. |
הכנסה בעץ B+
שלב 1: הכנס את הצומת החדש כצומת עלה
שלב 2: אם לעלה אין מקום נדרש, פצל את הצומת והעתק את הצומת האמצעי לצומת האינדקס הבא.
שלב 3: אם לצומת האינדקס אין מקום נדרש, פצל את הצומת והעתק את האלמנט האמצעי לעמוד האינדקס הבא.
דוגמא :
הכנס את הערך 195 לעץ B+ בסדר 5 המוצג באיור הבא.
195 יוכנס בתת-עץ הימני של 120 לאחר 190. הכנס אותו במיקום הרצוי.
הצומת מכיל יותר מהמספר המרבי של אלמנטים, כלומר 4, לכן פצל אותו והצב את הצומת החציוני עד להורה.
כעת, צומת האינדקס מכיל 6 ילדים ו-5 מפתחות אשר מפר את מאפייני העץ B+, לכן עלינו לפצל אותו, המוצג כדלקמן.
מחיקה ב-B+ Tree
שלב 1: מחק את המפתח והנתונים מהדפים.
שלב 2: אם צומת העלה מכיל פחות ממספר מינימלי של אלמנטים, מיזוג את הצומת עם אחיו ומחק את המפתח שביניהם.
שלב 3: אם צומת האינדקס מכיל פחות ממספר מינימלי של אלמנטים, מיזוג את הצומת עם האח והזז את המקש מטה ביניהם.
דוגמא
מחק את המפתח 200 מעץ B+ המוצג באיור הבא.
200 קיים בתת-עץ הימני של 190, לאחר 195. מחק אותו.
מיזוג את שני הצמתים באמצעות 195, 190, 154 ו-129.
כעת, אלמנט 120 הוא האלמנט הבודד הקיים בצומת אשר מפר את מאפייני B+ Tree. לכן, עלינו למזג אותו באמצעות 60, 78, 108 ו-120.
כעת, גובה עץ B+ יקטן ב-1.
