ברוכים הבאים לשיעור בנושא אינדקסים במערכות נתונים. יחידה זו חיונית להבנת האופן שבו מסדי נתונים משיגים ביצועים גבוהים בטיפול בכמויות אדירות של מידע. נתמקד במבני נתונים המשמשים לאינדקסים, בשיפור ביצועי שאילתות ובניתוח עלויות גישה, נושא מרכזי בבחינות הקורס.
מבוא לאינדקסים: למה אנחנו צריכים אותם?
במערכות נתונים גדולות, הנתונים מאוחסנים על דיסק קשיח. גישה לדיסק (קלט/פלט - I/O) היא פעולה יקרה ואיטית משמעותית מגישה לזיכרון הראשי. ללא אינדקסים, כל שאילתה הדורשת איתור רשומות ספציפיות עלולה לדרוש סריקה מלאה של הטבלה כולה על הדיסק, מה שמוביל לביצועים ירודים באופן דרמטי. אינדקסים הם מבני נתונים מיוחדים המאפשרים למסד הנתונים לאתר רשומות במהירות, על ידי צמצום מספר פעולות הקלט/פלט הנדרשות.
סוגי אינדקסים וארגון נתונים
קיימים מספר סיווגים לאינדקסים, המשפיעים על אופן אחסון הנתונים ועל ביצועי השאילתות:
אינדקס מקובץ (Clustered Index)
האינדקס קובע את הסדר הפיזי של הרשומות על הדיסק. לכל טבלה יכול להיות לכל היותר אינדקס מקובץ אחד. גישה דרך אינדקס מקובץ מהירה מאוד, במיוחד עבור שאילתות טווח, מכיוון שהרשומות הסמוכות במפתח האינדקס סמוכות גם פיזית על הדיסק.
אינדקס לא מקובץ (Unclustered Index)
האינדקס אינו קובע את הסדר הפיזי של הרשומות. הוא מכיל מצביעים (pointers) למיקום הפיזי של הרשומות בטבלה. לטבלה יכולים להיות אינדקסים לא מקובצים רבים. גישה דרך אינדקס לא מקובץ דורשת קריאת בלוקים נוספים מהדיסק כדי לאחזר את הרשומות עצמן.
אינדקס ראשי (Primary Index)
אינדקס על המפתח הראשי של הטבלה. לרוב הוא גם אינדקס מקובץ, אך לא בהכרח (תלוי ביישום מסד הנתונים). הוא מבטיח ייחודיות של המפתח.
אינדקס משני (Secondary Index)
אינדקס על עמודה שאינה המפתח הראשי. אינדקסים משניים הם תמיד לא מקובצים, אלא אם כן הטבלה אינה מכילה אינדקס ראשי מקובץ (ואז אינדקס משני יכול להיות מקובץ, אך זהו מקרה נדיר). הם מאפשרים חיפוש מהיר על עמודות שאינן המפתח הראשי.
מבני נתונים נפוצים לאינדקסים: עצי B+ ואינדקסי גיבוב
עצי B+ (B+ Trees)
עצי B+ הם מבנה הנתונים הנפוץ ביותר לאינדקסים במערכות נתונים יחסיות. הם מאוזנים באופן אוטומטי, מה שמבטיח שכל החיפושים יארכו זמן דומה (מספר קבוע של פעולות I/O), ללא קשר לערך המבוקש.
- מבנה: מורכב מצמתים פנימיים (Internal Nodes) ומצמתי עלה (Leaf Nodes).
- צמתים פנימיים: מכילים מפתחות ומצביעים לצמתים אחרים בעץ. הם משמשים להכוונה בלבד.
- צמתי עלה: מכילים את כל המפתחות וכן מצביעים לרשומות הנתונים עצמן (או את הרשומות עצמן אם זהו אינדקס מקובץ). צמתי העלה מקושרים ביניהם ברשימה מקושרת, המאפשרת סריקת טווח יעילה.
- גורם הסתעפות (Fan-out): מספר המצביעים שצומת יכול להכיל. גורם הסתעפות גבוה מפחית את גובה העץ.
- גובה העץ (Tree Height): מספר הרמות בעץ. ככל שהגובה נמוך יותר, כך נדרשות פחות פעולות I/O לחיפוש.
אינדקסי גיבוב (Hash Indexes)
אינדקסי גיבוב משתמשים בפונקציית גיבוב כדי למפות מפתח לכתובת אחסון ישירה. הם מצוינים לשאילתות שוויון (לדוגמה: WHERE id = 123) אך אינם יעילים כלל לשאילתות טווח (לדוגמה: WHERE age BETWEEN 20 AND 30).
ניתוח עלויות גישה (Access Cost Analysis): מדוע זה קריטי לבחינה?
היכולת לחשב את מספר פעולות הקלט/פלט הנדרשות לביצוע פעולות שונות (חיפוש, הכנסה, מחיקה, סריקה) על מבני אינדקס שונים היא אבן יסוד בבחינות הקורס. שאלות רבות דורשות מכם להשוות ביצועים של אינדקסים שונים תחת תרחישי עומס ספציפיים. עליכם להבין היטב כיצד פרמטרים כמו גודל בלוק, גודל רשומה, גורם הסתעפות, גובה העץ, והאם האינדקס מקובץ או לא, משפיעים על עלות ה-I/O.
- חיפוש בעץ B+: מספר פעולות I/O שווה לגובה העץ (לגישה לצמתי האינדקס) + 1 (לגישה לבלוק הנתונים). אם האינדקס מקובץ, זהו סך הכל. אם לא מקובץ, ייתכן שיהיו פעולות I/O נוספות לכל רשומה מאותגרת (במקרה הגרוע, N פעולות I/O עבור N רשומות).
- סריקת טווח בעץ B+: גישה לצמתים הפנימיים (גובה העץ) + גישה לצמתים העלה הרלוונטיים + סריקה לינארית של צמתי העלה המקושרים + גישה לבלוקי הנתונים (תלוי אם מקובץ או לא).
- חיפוש באינדקס גיבוב: בדרך כלל 1-2 פעולות I/O (גישה לבלוק הגיבוב וגישה לבלוק הנתונים), בהנחה שאין התנגשויות רבות.
- הכנסה/מחיקה: דורשות חיפוש + שינוי באינדקס (שעלול לגרור פיצול/איחוד בלוקים) + שינוי בנתונים עצמם.
שאלות לדיון
- מתי עדיף להשתמש באינדקס מקובץ על פני אינדקס לא מקובץ, ומתי ההפך?
- כיצד משפיע גורם ההסתעפות של עץ B+ על ביצועי שאילתות חיפוש ועלויות אחסון?
- תאר תרחיש שבו אינדקס גיבוב יהיה עדיף באופן מובהק על עץ B+, ותרחיש שבו עץ B+ יהיה עדיף. נמק.
- כיצד תחשב את עלות ה-I/O עבור שאילתת טווח (לדוגמה:
SELECT * FROM Students WHERE Grade BETWEEN 80 AND 90) כאשר קיים אינדקס B+ לא מקובץ על העמודה Grade?
נקודות לתשובת מודל
- אינדקס מקובץ מול לא מקובץ: מקובץ עדיף לסריקות טווח ולשליפת רשומות רבות לאחר איתור ראשוני (כי הנתונים סמוכים פיזית). לא מקובץ עדיף כאשר יש צורך במספר אינדקסים על אותה טבלה, או כאשר רוצים לחפש על עמודות רבות ושונות.
- השפעת גורם ההסתעפות: גורם הסתעפות גבוה מקטין את גובה העץ, ובכך מפחית את מספר פעולות ה-I/O הנדרשות לחיפוש. עם זאת, כל צומת מכיל יותר מפתחות ומצביעים, מה שמגדיל את מורכבות הניהול הפנימי שלו.
- B+ Tree מול Hash Index:
- Hash Index עדיף: לשאילתות שוויון מדויקות (
WHERE key = value), כאשר מהירות הגישה למפתח יחיד היא קריטית ואין צורך בשאילתות טווח או סדר. - B+ Tree עדיף: לרוב המקרים, כולל שאילתות שוויון, שאילתות טווח, מיון, וגישה סדרתית. הוא גמיש יותר ומתאים למגוון רחב של תרחישים.
- Hash Index עדיף: לשאילתות שוויון מדויקות (
- עלות I/O לשאילתת טווח עם אינדקס B+ לא מקובץ:
- גישה לעץ: גובה העץ פעולות I/O (לצורך איתור צומת העלה הראשון בטווח).
- סריקת צמתי עלה: מספר פעולות I/O השווה למספר בלוקי העלה המכילים את המפתחות בטווח.
- גישה לנתונים: עבור כל רשומה שנמצאה בטווח, נדרשת פעולת I/O נוספת לגישה לבלוק הנתונים שלה (במקרה הגרוע, אם כל רשומה נמצאת בבלוק נתונים שונה). יש לזכור שייתכנו אופטימיזציות (לדוגמה, אם מספר רשומות מצביעות לאותו בלוק נתונים).