אינדקסים - חלק 1 - ilDBA Portal

אינדקסים – חלק 1

08/11/2011 | פורסם על ידי

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

מבנה בסיסי

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

לפני שניכנס לתאור, בואו נסתכל על התמונה למעלה ונגדיר מספר מונחים:

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

ישנם מספר מאפיינים שמתארים B*Tree והם:

  1. לכל צומת בעץ יש הרבה "ילדים" (צמתים שהצומת הזה מצביע אליהם).
  2. המידע עצמו יושב אך ורק בעלים, כל שאר הצמתים מכילים רק מצביעים.
  3. קיימים מצביעים בין כל שני עלים סמוכים.
  4. העץ תמיד מאוזן, כלומר, כל העלים יהיו תמיד באותה רמה.
  5. העץ ממוין, כלומר כל המידע שיושב בעלים הוא תמיד ממוין. אם נרצה לסרוק את כל הערכים בצורה ממוינת נצטרך להגיע לערך הקיצוני בעלה הקיצוני (ימני או שמאלי) ולעבור על כל העלים, אחד אחרי השני.

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

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

חיפוש באינדקס

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

):

,5,,10,,35,,100,

P1 הוא מצביע לבלוק המכיל מספרים שקטנים מ- 5, P2 מצביע לבלוק שמכיל מספרים בין 5 ל- 10 וכן הלאה. לכן, אם אנחנו מחפשים 22 נלך לבלוק עליו מצביע P3. ככה נתקדם בעץ, רמה אחרי רמה, עד שנגיע לעלה. בעלה יהיה הערך 22 (המספר 22 יופיע כמספר הפעמים שהערך מופיע בטבלה) ואת ה- ROWID של הרשומה או הרשומות, לדוגמא:

20,,22,,22,,30,

בדוגמא הנ"ל, יש 2 רשומות המכילות את הערך 22 ולכן נפנה לרשומות שנמצאות ב- ROWID2 ו- ROWID3.

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

מכאן אפשר להבין שאם השאיפה היא לבצע כמה שפחות פעולות IO, נרצה שהעץ יהיה כמה שפחות עמוק (או יותר רדוד). כדי לעשות את זה נצטרך להרחיב כמה שאפשר את הרמות בעץ. אם בעץ א' יש שני בלוקים מקסימום ברמה הראשונה, ובעץ ב' יש 500, ברור שנוכל להכניס יותר ערכים ומצביעים לרשומות (ROWID) בעץ השני מאשר בראשון.

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

בואו נראה את זה קורה. ניצור אינדקס על שדה מסוג תאריך ונראה כמה ערכים הוא צריך כדי ליצור רמה נוספת בעץ. על זה גם נרחיב בפעם הבאה. שימו לב שכדי לראות את עומק העץ נסתכל על עמודה בשם blevel ב- user_indexes. עמודה זו מאוכלסת רק עם איסוף סטטיסטיקות על האינדקס.

SQL> create table ildba (mydate date);
Table created.

SQL> create index ildba_idx on ildba(mydate);
Index created.

-- I performed several inserts
SQL> select count(*) from ildba;
COUNT(*)
----------
421

SQL> dbms_stats.gather_index_stats(user,'ILDBA_IDX');

SQL> exec dbms_stats.gather_index_stats(user,'ILDBA_IDX');
PL/SQL procedure successfully completed.

SQL> select blevel from user_indexes
2  where index_name='ILDBA_IDX';
BLEVEL
----------
0

SQL> insert into ildba values(sysdate);
1 row created.

SQL> select count(*) from ildba;
COUNT(*)
----------
422

SQL> exec dbms_stats.gather_index_stats(user,'ILDBA_IDX');
PL/SQL procedure successfully completed.

SQL> select blevel from user_indexes
2  where index_name='ILDBA_IDX';
BLEVEL
----------
1

מה זאת אומרת האינדקס תמיד מאוזן?

עץ לא מאוזן הוא עץ שהעלים שבו נמצאים בעומק שונה מהשורש. מבנה B*Tree הוא מבנה מאוזן בהגדרתו, כלומר כל העלים תמיד יהיו בעומק שווה. הסיבה נעוצה במבנה הנתונים עצמו ואיך בונים ומתחזקים אותו. אני לא אכנס לזה פה, כי זה קצת מורכב (וביננו, גם לא עד כדי כך מעניין) מי שממש רוצה לדעת, יכול לקרוא על כל האלגוריתמים בוויקיפדיה: https://secure.wikimedia.org/wikipedia/en/wiki/B-tree.

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

סיכום חלק 1

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

נתראה ברשומה הבאה !

לירון אמיצי.

ניתן ליצור קשר עם לירון דרך עמוד האודות שלו: אודות.

The following two tabs change content below.
ירון אמיצי הוא סמנכ"ל שירותי מומחה בחברת בריליקס ו-DBA בכיר בעל נסיון של למעלה מ- 15 שנים. ללירון תואר Oracle Ace ומתמחה בנושאי ביצועים, תשתיות, פתרונות זמינות גבוהה, גיבויים ושחזורים. ללירון יש גם בלוג עצמאי בכתובת: https://amitzil.wordpress.com

5 תגובות ל- “אינדקסים – חלק 1”

commenter

תודה עמיאל,

ואגב, ROWID כן חד חד ערכי, הוא מורכב מקובץ, בלוק ומספר רשומה בבלוק. מקרה חריג הוא ב- clusters. אתה יכול לראות את זה בתיעוד:

http://download.oracle.com/docs/cd/E11882_01/server.112/e26088/pseudocolumns008.htm#SQLRF00254

commenter

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

commenter

כפי שטענתי, הוא לא חד חד ערכי.
פשוט עניתי על זה פעם בפורום  אחר:
http://isql.co.il/tabid/55/forumid/-1/threadid/124/scope/posts/Default.aspx
אז המשפט קפץ לי לראש (;
בכל מקרה מחכה לחלק השני של המאמר
 

[…] של האינדקסים: Bitmap, Function based וכו'. לירון אמיצי כתב סדרת מאמרים על אינדקסים ואיך הם עובדים – שווה ללכת ולקרוא אותם אם הנושא מעניין […]

[…] של המאמרים הקודמים: חלק 1, חלק […]

השאר תגובה:

שם (חובה):
אימייל (לא יפורסם) (חובה):
תגובה (חובה):

*



מאמרים קשורים

Baruch Osoveskiy

תיקון מהיר לדיסק איטי

  רציתי לשתף אתכם בתקלה שהיתה לי ובפיתרון שלה. לפעמים אני רוצה לבדוק גירסה חדשה או יכולת שלא מתועדת מספיק בספרות, ואז אני מסתפק בהקמה של סביבה ווירטואלית בדרך כלל על חומרה זולה (לפעמים זולה [...]
OS

OS Background operations

אורי לרנר בטיפ קצר ושימושי על העברת פעולות לרקע במערכת [...]
רשימת

רשימת הפיצ'רים החדשים של אורקל 12.1

אורקל פרסמו את הספרות הרשמית לגרסה 12.1 שיצאה לאחרונה וזמינה להורדה. בין שאר הספרים (החשובים כל אחד שלעצמו), פורסם הספר המסקרן ביותר בעיני – Oracle Database 12c Release 1 (12.1) New Features. זהו ספר שראוי שכל DBA [...]
גרסת

גרסת אורקל 12c זמינה להורדה

בשעה טובה ולאחר המתנה סופר ארוכה, גרסת אורקל 12c (גרסה 12.1) זמינה סוף סוף להורדה רשמית מהאתר של אורקל. הגרסה החדשה מנסה לתת פתרונות לעולם ה"ענן" – ומוסיפה פיצ'רים חדשים שבאים לתת מענה בדיוק [...]
Copyright 2019 ilDBA Portal. Brought to you by Brillix - Israel Leading DBA company. Sponsored by: DBSnaps - Database Video Tutorialss
Website Security Test
%d בלוגרים אהבו את זה: