מה קורה בתוך אינדקס מסד נתונים - איך עץ B-Tree באמת בנוי¶
הפוסט על אינדקסים במסד נתונים הסביר את האנלוגיה של תוכן עניינים בספר, וקבע שברוב המסדי נתונים אינדקס בנוי על עץ מאוזן שנקרא B-Tree. אבל "עץ מאוזן שמחלק את מרחב החיפוש בערך בחצי" זו רק הכותרת. השאלה המעניינת באמת היא איך עץ כזה בכלל נשאר מאוזן, גם אחרי מיליוני הכנסות ומחיקות של שורות לאורך שנים.
מה מבדיל B-Tree מעץ בינארי רגיל¶
בעץ בינארי רגיל, כל צומת מחזיק ערך אחד ומצביע לכל היותר על שני ילדים. B-Tree שונה - כל צומת יכול להחזיק כמה ערכים ממוינים בבת אחת, ולהצביע על הרבה יותר משני ילדים, לפעמים מאות. המספר המקסימלי הזה נקרא הסדר (order) של העץ. הרעיון המרכזי - כל מה שנמצא בין שני ערכים בצומת מכוון בדיוק לילד אחד ספציפי, שמכיל את כל הערכים שנמצאים בטווח שביניהם.
היתרון המיידי הוא גובה נמוך דרמטית. בעץ בינארי, כל שלב יורד רק לשני כיוונים אפשריים, כך שגובה העץ גדל בערך כמו log בבסיס 2 של מספר האיברים. ב-B-Tree, כל שלב יורד לעשרות או מאות כיוונים אפשריים בבת אחת, כך שהגובה גדל בקצב הרבה יותר איטי - log בבסיס גדול, נגיד מאה, של מספר האיברים. התוצאה - טבלה עם מיליון שורות עשויה להזדקק לעץ בגובה שלוש או ארבע רמות בלבד, כלומר שלוש או ארבע קפיצות דיסק בלבד כדי למצוא כל שורה.
למה זה חשוב במיוחד למסדי נתונים ולא רק לזיכרון¶
התכונה הזאת קריטית במיוחד למסדי נתונים כי הם עובדים מול דיסק, לא רק זיכרון RAM. פנייה לדיסק יקרה משמעותית מפנייה לזיכרון, ומנועי מסדי נתונים בונים כל צומת של B-Tree בגודל שמתאים בדיוק לבלוק קריאה אחד מהדיסק. כל "קפיצה" בעץ היא בדיוק פנייה אחת לדיסק, ולכן גובה נמוך משמעו פחות פניות יקרות, וזו בדיוק הסיבה שאינדקס יכול להפוך שאילתה מסריקה של מיליון שורות לחיפוש שלוקח שלוש או ארבע פניות בלבד.
איך צומת מתפצל כשהוא מתמלא¶
מה קורה כשמכניסים ערך חדש לצומת שכבר מלא לגמרי? כאן קורה הקסם שמשמר את האיזון. הצומת המלא מתפצל לשניים - חצי מהערכים נשארים בצומת המקורי, חצי עוברים לצומת חדש, והערך האמצעי "עולה" צעד אחד למעלה לצומת ההורה, כדי לשמש כמפריד בין שני הצמתים החדשים. אם גם ההורה מלא, אותו תהליך פיצול קורה שם, ויכול להמשיך ולהתפשט כלפי מעלה עד לשורש. כשגם השורש מתפצל, נוצר שורש חדש, וזו הדרך היחידה שבה גובה העץ כולו גדל - תמיד מלמעלה, ותמיד באופן שמשמר איזון מושלם, כי הפיצול קורה בו-זמנית בכל צמתי העלים.
עלים מקושרים - למה B-Tree מצוין גם לטווחים¶
תכונה נוספת שהופכת B-Tree לכלי אידיאלי לאינדקסים - עלי העץ, השכבה התחתונה ביותר שמחזיקה בפועל את הפניות לשורות בטבלה, מקושרים אחד לשני ברשימה מקושרת. המשמעות - שאילתה כמו WHERE price BETWEEN 100 AND 200 לא צריכה לרדת בעץ מחדש עבור כל ערך. היא יורדת בעץ פעם אחת כדי למצוא את הערך 100, ואז פשוט הולכת ימינה לאורך העלים המקושרים עד שהיא עוברת את 200. זה הופך שאילתות טווח, לא רק חיפוש ערך בודד, למהירות באותה מידה.
למה כדאי להבין את זה, לא רק "לשים אינדקס"¶
מתכנת שמבין את מבנה ה-B-Tree מבין גם למה כתיבה לטבלה עם הרבה אינדקסים איטית - כל הכנסת שורה עלולה לגרום לפיצולי צמתים בכמה עצים בו-זמנית, למה מפתח אינדקס עם ערכים אקראיים (כמו UUID) גורם ליותר פיצולים מאשר מפתח עולה בסדר (כמו מספר סידורי), ולמה שאילתות טווח כל כך יעילות עם אינדקס נכון. זו בדיוק ההבנה שהופכת אופטימיזציית שאילתות מניחוש לתהליך מבוסס.
בקורס צד-שרת עוברים על ביצועי מסדי נתונים בהקשר מעשי, כולל איך לבחור ולתכנן אינדקסים נכון.
יש לכם שאילתה שלא מתנהגת כמו שציפיתם למרות שיש לה אינדקס? שאלו בדיסקורד.
לסיכום¶
B-Tree שומר על גובה נמוך גם עם מיליוני רשומות בזכות צמתים רחבים במיוחד ומנגנון פיצול שמתפשט תמיד מלמעלה, ולא מתפרק לרוחב באופן לא מאוזן. עלים מקושרים הופכים אותו למהיר גם לחיפוש טווחים, לא רק ערך בודד. זו בדיוק הסיבה שהוא הבחירה הכמעט אוניברסלית לאינדקסים במסדי נתונים.