TechCodeview

במדריך הבא, נלמד על מבנה הנתונים של B Tree ונשקול להמחיש אותו.

אז בואו נתחיל.

מהו עץ B?

ה B עץ הוא סוג מיוחד של עץ חיפוש רב כיווני , הידוע בכינויו ה M-way עץ, שמאזן את עצמו. בגלל המבנה המאוזן שלהם, עצים אלה משמשים בדרך כלל לתפעול וניהול מסדי נתונים עצומים ולפשט חיפושים. בעץ B, לכל צומת יכולים להיות לכל היותר n צמתים צאצאים. B Tree הוא דוגמה לאינדקס רב-שכבתי במערכת ניהול מסדי נתונים (DBMS). לצמתים עלה וצמתים פנימיים יהיו שניהם הפניות לרשומות. B Tree ידוע בתור Balanced Stored Tree מכיוון שכל צמתי העלים נמצאים באותה רמה.

התרשים הבא הוא דוגמה לעץ B:

איור 1. עץ B עם סדר 3

הבנת הכללים של עץ B

להלן המאפיינים החשובים של עץ B:

1. כל צמתי העלים נמצאים באותה רמה.
2. מבנה הנתונים של B Tree מוגדר על ידי המונח דרגה מינימלית 'd'. הערך של 'd' תלוי בגודל בלוק הדיסק.
3. כל צומת, למעט השורש, חייב להיות מורכב ממפתחות d-1 לפחות. צומת השורש עשוי להיות מורכב ממפתח אחד לפחות.
4. כל הצמתים (כולל צומת השורש) עשויים להכיל לכל היותר (2d-1) מפתחות.
5. מספר הילדים של צומת שווה ל- תוספת של מספר המפתחות הקיימים בו ו .
6. כל המפתחות של צומת ממוינים בסדר עולה. הילד בין שני מפתחות, k1 ו-k2, מורכב מכל המקשים הנעים בין k1 ל-k2, בהתאמה.
7. שלא כמו עץ ​​החיפוש הבינארי, מבנה הנתונים של B Tree גדל ומתכווץ מהשורש. ואילו עץ החיפוש הבינארי גדל כלפי מטה ומתכווץ כלפי מטה.
8. בדומה לעצי חיפוש בינאריים מאוזנים אחרים, מורכבות הזמן של מבנה הנתונים של B Tree עבור פעולות כמו חיפוש, הכנסה ומחיקה היא O(log?n) .
9. הכנסת צומת בעץ B מתרחשת רק בצומת העלה.

הבה נבחן את הדוגמה הבאה של עץ B בסדר גודל מינימלי 5.

איור 2. A B עץ סדר 5

הערה: הערך של ההזמנה המינימלית הוא הרבה יותר מ-5 ב-B Trees מעשי.

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

הניסוח הקבוע של חוקי B Tree:

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

חוק מספר 1: לשורש יכול להיות רק אלמנט נתונים אחד (או אפילו ללא רכיבי נתונים אם הוא גם לא ילדים); לכל צומת אחר יש לפחות מִינִימוּם רכיבי נתונים.

כלל 2: המספר המרבי של רכיבי נתונים המאוחסנים בצומת הוא כפול מהערך של מִינִימוּם .

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

כלל 4: המספר הכולל של תת-עצים מתחת לצומת שאינו עלה הוא תמיד אחד יותר ממספר רכיבי הנתונים באותו צומת.

• תת-עץ 0, תת-עץ 1,...

כלל 5: ביחס לכל צומת שאינו עלה:

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

כלל 6: לכל עלה בעץ B יש אותו עומק. כך, הוא מבטיח שעץ B מונע את הבעיה של עץ לא מאוזן.

פעולות על מבנה נתונים B Tree

על מנת להבטיח שאף אחד מהמאפיינים של מבנה נתונים B Tree אינו מופר במהלך הפעולות, ניתן לפצל או לצרף את B Tree. להלן כמה פעולות שאנו יכולים לבצע על עץ B:

1. חיפוש אלמנט נתונים ב-B Tree
2. הכנסת אלמנט נתונים בעץ B
3. מחיקה של רכיב נתונים ב-B Tree

פעולת חיפוש על עץ B

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

שלבים לחיפוש רכיב נתונים בעץ B:

שלב 1: החיפוש מתחיל מצומת השורש. השווה את אלמנט החיפוש, k, עם השורש.

שלב 1.1: אם צומת השורש מורכב מהאלמנט k, החיפוש יושלם.

שלב 1.2: אם האלמנט k קטן מהערך הראשון בשורש, נעבור לילד השמאלי ביותר ונחפש את הילד באופן רקורסיבי.

שלב 1.3.1: אם לשורש יש רק שני ילדים, נעבור לילד הימני ביותר ונחפש רקורסיבית בצמתי הילד.

שלב 1.3.2: אם לשורש יש יותר משני מפתחות, נחפש את השאר.

שלב 2: אם האלמנט k לא נמצא לאחר חציית העץ כולו, אזי אלמנט החיפוש אינו קיים בעץ B.

תן לנו לדמיין את השלבים לעיל בעזרת דוגמה. נניח שרצינו לחפש מפתח k=34 בעץ B הבא:

איור 3.1. עץ B נתון

1. ראשית, נבדוק אם המפתח k = 34 נמצא בצומת השורש. מכיוון שהמפתח אינו בשורש, נעבור לצמתי הצאצא שלו. אנו יכולים גם לראות שלצומת השורש יש שני ילדים; לכן, נשווה את הערך הנדרש בין שני המפתחות.
   
   איור 3.2. המפתח k אינו קיים בשורש
2. כעת, כשנוכל לשים לב שהמפתח k גדול יותר מצומת השורש, כלומר 30, נמשיך עם הילד הימני של השורש.
   
   איור 3.3. המקש k > 30, עבור לילד הנכון
3. כעת נשווה את המפתח k עם הערכים הקיימים בצומת, כלומר 40 ו-50, בהתאמה. מכיוון שהמפתח k קטן מהמפתח השמאלי, כלומר 40, נעבור לילד השמאלי של הצומת.
   
   איור 3.4. המפתח ק<40, move to left child< li>
4. מכיוון שהערך בבן השמאלי של 40 הוא 34, שהוא הערך הנדרש, אנו יכולים להסיק שהמפתח נמצא, ותפעולת החיפוש הושלמה.
   
   איור 3.4. המפתח k = 34, הילד השמאלי של 40

השווינו את המפתח עם ארבעה ערכים שונים בדוגמה שלמעלה עד שמצאנו אותו. לפיכך, מורכבות הזמן הנדרשת עבור פעולת החיפוש ב-B Tree היא O(log?n) .

הכנסת פעולה על עץ B

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

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

שלבים להוספת רכיב נתונים בעץ B:

שלב 1: נתחיל בחישוב המספר המרבי של מפתחות בצומת על בסיס סדר ה-B Tree.

שלב 2: אם העץ ריק, מוקצה צומת שורש, ונכניס את המפתח שפועל כצומת השורש.

שלב 3: כעת נחפש את הצומת הרלוונטי להכנסה.

שלב 4: אם הצומת מלא:

מופע של java

שלב 4.1: נכניס את רכיבי הנתונים בסדר עולה.

שלב 4.2: אם רכיבי הנתונים גדולים ממספר המפתחות המרבי, נחלק את הצומת המלא בחציון.

שלב 4.3: נדחוף את המקש החציוני כלפי מעלה ונפצל את המקשים השמאלי והימני כילד שמאלי וימני.

שלב 5: אם הצומת לא מלא, נכניס את הצומת בסדר עולה.

תן לנו לדמיין את השלבים לעיל בעזרת דוגמה. נניח שאנו נדרשים ליצור עץ B מסדר 4. רכיבי הנתונים שצריך להכניס לעץ B הם 5,3,21,11,1,16,8,13,4 ו-9 .

1. מכיוון ש-m שווה ל-3, המספר המרבי של מפתחות עבור צומת = m-1 = 3-1 = 2 .
2. נתחיל בהכנסה 5 בעץ הריק.
   
   איור 4.1. הכנסת 5
3. כעת נכניס 3 לעץ. מכיוון ש-3 הוא פחות מ-5, נכניס 3 משמאל ל-5 באותו צומת.
   
   איור 4.2. הכנסת 3
4. כעת נכניס 21 לעץ, ומכיוון ש-21 גדול מ-5, הוא יוכנס מימין ל-5 באותו צומת. עם זאת, מכיוון שאנו יודעים שמספר המפתחות המקסימלי בצומת הוא 2, אחד מהמקשים הללו יועבר לצומת למעלה על מנת לפצל אותו. לפיכך, 5, אלמנט הנתונים האמצעי, ינוע למעלה, ו-3 ו-21 יהפכו לצמתים השמאלי והימני שלו, בהתאמה.
   
   איור 4.3. מכניס 21
5. כעת הגיע הזמן להכניס את אלמנט הנתונים הבא, כלומר, 11, שהוא גדול מ-5 אך פחות מ-21. לכן, 11 יוכנס כמפתח משמאל לצומת המורכב מ-21 כמפתח.
   
   איור 4.4. מכניס 11
6. באופן דומה, נכניס לעץ את אלמנט הנתונים הבא 1, וכפי שאנו יכולים לראות, 1 הוא פחות מ-3; לכן, הוא יוכנס כמפתח משמאל לצומת המורכב מ-3 כמפתח.
   
   איור 4.5. הכנסת 1
7. כעת, נכניס את רכיב הנתונים 16 לעץ, שהוא גדול מ-11 אך פחות מ-21. עם זאת, מספר המפתחות באותו צומת חורג ממספר המפתחות המרבי. לכן, הצומת יתפצל, ויעביר את המפתח האמצעי לשורש. לפיכך, 16 יוכנס מימין ל-5, תוך פיצול 11 ו-21 לשני צמתים נפרדים.
   
   איור 4.6. מכניס 16
8. רכיב הנתונים 8 יוכנס כמפתח משמאל ל-11.
   
   איור 4.7. הכנסת 8
9. נכניס לעץ 13, שהוא קטן מ-16 ויותר מ-11. לכן, יש להכניס את אלמנט הנתונים 13 מימין לצומת המורכב מ-8 ו-11. עם זאת, מכיוון שמספר המפתחות המרבי בעץ יכול רק יהיה 2, יתרחש פיצול, שיעביר את אלמנט הנתונים האמצעי 11 לצומת למעלה ו-8 ו-13 לשני צמתים נפרדים. כעת, הצומת לעיל יורכב מ-5, 11 ו-16, אשר שוב חורג ממספר המפתחות המקסימלי. לכן, יהיה פיצול נוסף, מה שהופך את אלמנט הנתונים 11 לצומת השורש עם 5 ו-16 בתור הילדים שלו.
   
   איור 4.8. מכניס 13
10. מכיוון שאלמנט הנתונים 4 קטן מ-5 אך גדול מ-3, הוא יוכנס מימין לצומת המורכב מ-1 ו-3, אשר יחרוג שוב מהספירה המקסימלית של מפתחות בצומת. לכן, שוב תתרחש שפיכה, ותעביר את ה-3 לצומת העליון לצד 5.
    
    איור 4.9. הכנסת 4
11. לבסוף, אלמנט הנתונים 9, שהוא גדול מ-8 אך פחות מ-11, יוכנס מימין לצומת המורכב מ-8 כמפתח.
    
    איור 4.10. הכנסת 9

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

מחיקת פעולה על עץ B

מחיקת רכיב נתונים בעץ B מכילה שלושה אירועים עיקריים:

1. חיפוש הצומת שבו קיים המפתח שיש למחוק,
2. מחיקת המפתח, ו

• איזון העץ במידת הצורך.

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

להלן כמה מונחים שנדרשים להבין לפני הצגת פעולת המחיקה/הסרה:

קודמו לפי הסדר:המפתח המשמעותי ביותר בצאצא השמאלי של צומת ידוע בתור קודמו לפי הסדר.יורש לפי הסדר:המפתח המינורי בצאצא הימני של צומת ידוע כיורשו לפי הסדר.

להלן שלושה מקרים בולטים של פעולת המחיקה בעץ B:

מקרה 1: המחיקה/הסרה של המפתח נמצאת בצומת העלה - מקרה זה מתחלק לשני מקרים שונים:

1. המחיקה/הסרה של המפתח אינה מפרה את המאפיין של מספר המפתחות המינימלי שצומת צריך להחזיק.

הבה נדמיין את המקרה הזה באמצעות דוגמה שבה נמחק מקש 32 מהעץ הבא B.

שיטות ב-java

איור 4.1: מחיקת מפתח צומת עלה (32) מעץ B

כפי שאנו יכולים לראות, מחיקת 32 מעץ זה אינה מפרה את המאפיין הנ'ל.

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

ראשית, נבקר את האח השמאלני הקרוב. אם לצומת האח השמאלי יש יותר ממספר מינימלי של מפתחות, הוא ישאל מפתח מהצומת הזה.

אחרת, נבדוק לשאול מהצומת הימני הקרוב של האחים.

כעת נדמיין את המקרה הזה בעזרת דוגמה שבה נמחק 31 מהעץ B לעיל. נשאל מפתח מהצומת השמאלי של האחים במקרה זה.

איור 4.2: מחיקת מפתח צומת עלה (31) מעץ B

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

תן לנו לדמיין שוב על ידי מחיקת מקש 30 מעץ B לעיל.

איור 4.3: מחיקת מפתח צומת עלה (30) מעץ B

מקרה 2: המחיקה/הסרה של המפתח טמונה בצומת שאינו עלה - מקרה זה מתחלק עוד יותר למקרים שונים:

1. הצומת שאינו עלה/פנימי, שהוסר, מוחלף בקודם לפי הסדר אם לצומת הצאצא השמאלי יש יותר ממספר המפתחות המינימלי.

הבה נדמיין את המקרה הזה באמצעות דוגמה שבה נמחק את המפתח 33 מהעץ B.

איור 4.4: מחיקת מפתח צומת עלה (33) מעץ B

2. הצומת שאינו עלה/פנימי, שהוסר, מוחלף ביורש לפי הסדר אם לצומת הילד הימני יש יותר ממספר המפתחות המינימלי.

אם לכל אחד מהילדים יש מספר מינימלי של מפתחות, נמזג את צמתי הילד השמאלי והימין.

תן לנו לדמיין את המקרה הזה על ידי מחיקת המפתח 30 מהעץ B.

איור 4.5: מחיקת מפתח צומת עלה (30) מעץ B

לאחר המיזוג, אם לצומת האב יש פחות ממספר המפתחות המינימלי, אפשר לחפש את האחים, כמו ב תיק 1 .

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

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

הבה נדמיין את המקרה הזה בעזרת דוגמה שבה נמחק את רכיב הנתונים 10 מעץ B הנתון.

איור 4.6: מחיקת מפתח צומת עלה (10) מעץ B

מורכבות הזמן בדוגמאות לעיל משתנה בהתאם למיקום שממנו יש למחוק את המפתח. לפיכך, מורכבות הזמן עבור פעולת המחיקה בעץ B היא O(log?n) .

המסקנה

במדריך זה, למדנו על עץ B וראינו את הפעולות השונות שלו בעזרת דוגמאות שונות. הבנו גם כמה מאפיינים וכללים בסיסיים של עץ B.