היי הבר! אני מציג לתשומת לבך את התרגום של המאמר
"כיצד עובד מסד נתונים יחסי".

כשזה מגיע למאגרי מידע יחסי אני לא יכול שלא לחשוב שמשהו חסר. הם משמשים בכל מקום. ישנם מסדי נתונים רבים ושונים, החל מ-SQLite הקטן והשימושי ועד ל-Teradata העוצמתי. אבל יש רק כמה מאמרים שמסבירים איך מסד הנתונים עובד. אתה יכול לחפש בעצמך באמצעות "howdoesarelationaldatabasework" כדי לראות כמה מעט תוצאות יש. יתר על כן, המאמרים הללו קצרים. אם אתה מחפש את הטכנולוגיות הבאזז העדכניות ביותר (BigData, NoSQL או JavaScript), תמצא מאמרים מעמיקים יותר המסבירים כיצד הם פועלים.

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

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

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

אתחיל עם כמה יסודות במדעי המחשב, כגון מורכבות הזמן של אלגוריתמים (BigO). אני יודע שחלקכם שונאים את המושג הזה, אבל בלעדיו לא תוכלו להבין את המורכבויות בתוך מסד הנתונים. מכיוון שזה נושא ענק, אני אתמקד ב מה שאני חושב שחשוב: כיצד מעבד מסד הנתונים SQL запрос. אני רק אציג מושגי מסד נתונים בסיסייםכך שבסוף המאמר יש לך מושג מה קורה מתחת למכסה המנוע.

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

לבעלי ידע מבינכם, מאמר זה מחולק ל-3 חלקים:

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

בחזרה לבסיס

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

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

O(1) לעומת O(n2)

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

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

מושג

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

לדוגמה, כשאני אומר "לאלגוריתם הזה יש מורכבות O(some_function())", זה אומר שהאלגוריתם דורש פעולות some_function(a_certain_amount_of_data) כדי לעבד כמות מסוימת של נתונים.

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

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

• O(1) או מורכבות קבועה נשארת קבועה (אחרת זה לא ייקרא מורכבות קבועה).
• O(היכנס(n)) נשאר נמוך אפילו עם מיליארדי נתונים.
• הקושי הגרוע ביותר - O(n2), שבו מספר הפעולות גדל במהירות.
• שני הסיבוכים האחרים מתגברים באותה מהירות.

דוגמאות

עם כמות קטנה של נתונים, ההבדל בין O(1) ל-O(n2) הוא זניח. לדוגמה, נניח שיש לך אלגוריתם שצריך לעבד 2000 אלמנטים.

• אלגוריתם O(1) יעלה לך פעולה אחת
• האלגוריתם O(log(n)) יעלה לך 7 פעולות
• אלגוריתם O(n) יעלה לך 2 פעולות
• האלגוריתם O(n*log(n)) יעלה לכם 14 פעולות
• אלגוריתם O(n2) יעלה לך 4 פעולות

ההבדל בין O(1) ל-O(n2) נראה גדול (4 מיליון פעולות) אבל תאבד מקסימום 2 ms, רק זמן למצמץ את העיניים. אכן, מעבדים מודרניים יכולים לעבד מאות מיליוני פעולות בשנייה. זו הסיבה שביצועים ואופטימיזציה אינם מהווים בעיה בפרויקטי IT רבים.

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

• אלגוריתם O(1) יעלה לך פעולה אחת
• האלגוריתם O(log(n)) יעלה לך 14 פעולות
• אלגוריתם O(n) יעלה לך 1 פעולות
• האלגוריתם O(n*log(n)) יעלה לך 14 פעולות
• אלגוריתם O(n2) יעלה לך 1 פעולות

לא עשיתי את החשבון, אבל הייתי אומר שעם האלגוריתם O(n2) יש לך זמן לשתות קפה (אפילו שניים!). אם תוסיף עוד 0 לנפח הנתונים, יהיה לך זמן לנמנם.

בואו נעמיק יותר

למידע שלך:

• בדיקת טבלת hash טובה מוצאת אלמנט ב-O(1).
• חיפוש בעץ מאוזן מספק תוצאות ב-O(log(n)).
• חיפוש במערך מייצר תוצאות ב-O(n).
• לאלגוריתמי המיון הטובים ביותר יש מורכבות O(n*log(n)).
• לאלגוריתם מיון גרוע יש מורכבות O(n2).

הערה: בחלקים הבאים נראה אלגוריתמים ומבני נתונים אלו.

ישנם מספר סוגים של מורכבות זמן אלגוריתם:

• תרחיש מקרה ממוצע
• התרחיש הטוב ביותר
• ותרחיש הגרוע ביותר

מורכבות הזמן היא לרוב התרחיש הגרוע ביותר.

דיברתי רק על מורכבות הזמן של האלגוריתם, אבל המורכבות חלה גם על:

• צריכת זיכרון של האלגוריתם
• אלגוריתם צריכת קלט/פלט דיסק

כמובן, ישנם סיבוכים גרועים מ-n2, למשל:

• n4: זה נורא! לחלק מהאלגוריתמים שהוזכרו יש את המורכבות הזו.
• 3n: זה אפילו יותר גרוע! לאחד האלגוריתמים שנראה באמצע מאמר זה יש את המורכבות הזו (והוא משמש למעשה במאגרי מידע רבים).
• פקטורי n: לעולם לא תקבל את התוצאות שלך אפילו עם כמות קטנה של נתונים.
• nn: אם אתה נתקל במורכבות הזו, אתה צריך לשאול את עצמך אם זה באמת תחום הפעילות שלך...

הערה: לא נתתי לך את ההגדרה האמיתית של ייעוד ה-O הגדול, רק רעיון. אתה יכול לקרוא מאמר זה ב ויקיפדיה להגדרה האמיתית (אסימפטוטית).

מיזוג מיון

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

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

לְמַזֵג

כמו אלגוריתמים שימושיים רבים, מיון מיזוג מסתמך על טריק: שילוב של 2 מערכים ממוינים בגודל N/2 למערך ממוין N-אלמנט עולה רק N פעולות. פעולה זו נקראת מיזוג.

בואו נראה מה זה אומר עם דוגמה פשוטה:

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

• 1) אתה משווה את שני האלמנטים הנוכחיים בשני מערכים (בהתחלה הנוכחי = ראשון)
• 2) ואז קח את הקטן ביותר כדי להכניס אותו למערך של 8 אלמנטים
• 3) ועבור לאלמנט הבא במערך שבו לקחתם את האלמנט הקטן ביותר
• וחזור על 1,2,3 עד שתגיע לאלמנט האחרון של אחד המערכים.
• אז אתה לוקח את האלמנטים הנותרים של המערך השני כדי להכניס אותם למערך של 8 אלמנטים.

זה עובד מכיוון ששני המערכים של 4 אלמנטים ממוינים ולכן אינך צריך "לחזור" במערכים הללו.

עכשיו כשהבנו את הטריק, הנה הפסאודוקוד שלי למיזוג:

array mergeSort(array a)
   if(length(a)==1)
      return a[0];
   end if

   //recursive calls
   [left_array right_array] := split_into_2_equally_sized_arrays(a);
   array new_left_array := mergeSort(left_array);
   array new_right_array := mergeSort(right_array);

   //merging the 2 small ordered arrays into a big one
   array result := merge(new_left_array,new_right_array);
   return result;

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

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

שלב החלוקה

בשלב החלוקה המערך מחולק למערכים יחידתיים ב-3 שלבים. המספר הרשמי של השלבים הוא log(N) (מכיוון ש-N=8, log(N) = 3).

איך אני יודע את זה?

אני גאון! במילה אחת - מתמטיקה. הרעיון הוא שכל שלב מחלק את גודל המערך המקורי ב-2. מספר השלבים הוא מספר הפעמים שניתן לחלק את המערך המקורי לשניים. זוהי ההגדרה המדויקת של לוגריתם (בסיס 2).

שלב המיון

בשלב המיון מתחילים עם מערכים אוניטריים (אלמנט בודד). במהלך כל שלב אתה מחיל פעולות מיזוג מרובות והעלות הכוללת היא N = 8 פעולות:

• בשלב הראשון יש לך 4 מיזוגים שעולים 2 פעולות כל אחד
• בשלב השני יש לך 2 מיזוגים שעולים 4 פעולות כל אחד
• בשלב השלישי יש לך מיזוג 1 שעולה 8 פעולות

מכיוון שישנם שלבים ביומן (N), עלות כוללת N * log(N) פעולות.

יתרונות מיון מיזוג

למה האלגוריתם הזה כל כך חזק?

כי:

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

הערה: סוג זה של אלגוריתם נקרא in-מקום (מיון ללא זיכרון נוסף).

• אתה יכול לשנות את זה כדי להשתמש בשטח דיסק וכמות קטנה של זיכרון בו-זמנית מבלי להכניס תקורה משמעותית לדיסק I/O. הרעיון הוא לטעון לזיכרון רק את החלקים שנמצאים כעת בעיבוד. זה חשוב כאשר אתה צריך למיין טבלה מרובה גיגה עם מאגר זיכרון של 100 מגה-בייט בלבד.

הערה: סוג זה של אלגוריתם נקרא מיון חיצוני.

• אתה יכול לשנות אותו כך שיפעל במספר תהליכים/שרשורים/שרתים.

לדוגמה, מיון מיזוג מבוזר הוא אחד ממרכיבי המפתח Hadoop (שזה מבנה בביג דאטה).

• האלגוריתם הזה יכול להפוך עופרת לזהב (באמת!).

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

טבלת מערך, עץ ו- Hash

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

Массив

מערך דו מימדי הוא מבנה הנתונים הפשוט ביותר. אפשר לחשוב על טבלה כמערך. לדוגמה:

מערך דו מימדי זה הוא טבלה עם שורות ועמודות:

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

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

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

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

עץ מסד נתונים ואינדקס

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

• גדול יותר מכל המפתחות המאוחסנים בתת העץ השמאלי
• פחות מכל המפתחות המאוחסנים בתת-עץ הימני

בוא נראה מה זה אומר מבחינה ויזואלית

רעיון

לעץ הזה יש N = 15 אלמנטים. נניח שאני מחפש 208:

• אני מתחיל בשורש שהמפתח שלו הוא 136. מאז 136<208, אני מסתכל על תת-העץ הימני של צומת 136.
• 398>208 לכן אני מסתכל על תת-העץ השמאלי של צומת 398
• 250>208 לכן אני מסתכל על תת-העץ השמאלי של צומת 250
• 200<208, לכן אני מסתכל על תת-העץ הימני של צומת 200. אבל ל-200 אין תת-עץ ימני, ערך לא קיים (כי אם זה קיים, זה יהיה בתת-עץ הימני 200).

עכשיו נניח שאני מחפש 40

• אני מתחיל בשורש שהמפתח שלו הוא 136. מאז 136 > 40, אני מסתכל על תת-העץ השמאלי של צומת 136.
• 80 > 40, מכאן שאני מסתכל על תת-העץ השמאלי של צומת 80
• 40=40, צומת קיים. אני מחזיר את מזהה השורה בתוך הצומת (לא מופיע בתמונה) ומחפש בטבלה את מזהה השורה הנתון.
• הכרת מזהה השורה מאפשרת לי לדעת בדיוק היכן הנתונים נמצאים בטבלה, כך שאוכל לאחזר אותם באופן מיידי.

בסופו של דבר, שני החיפושים יעלו לי במספר הרמות בתוך העץ. אם אתה קורא את החלק על מיון מיזוג בקפידה, אתה אמור לראות שיש רמות log(N). מתברר, יומן עלויות חיפוש (N), לא רע!

בואו נחזור לבעיה שלנו

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

• אם אתה רוצה לדעת מי עובד בבריטניה
• אתה מסתכל על העץ כדי לקבל את הצומת שמייצג את בריטניה הגדולה
• בתוך "UKnode" תמצא את המיקום של רשומות עובדים בבריטניה.

החיפוש הזה יעלה פעולות log(N) במקום N פעולות אם תשתמש במערך ישירות. מה שהצגת זה עתה היה אינדקס מסד נתונים.

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

B+TreeIndex

למרות שעץ זה עובד היטב לקבלת ערך ספציפי, יש בעיה גדולה כאשר אתה צריך לקבל מספר אלמנטים בין שני ערכים. זה יעלה O(N) כי תצטרך להסתכל על כל צומת בעץ ולבדוק אם הוא בין שני הערכים הללו (למשל עם מעבר מסודר של העץ). יתר על כן, פעולה זו אינה ידידותית ל-Disk I/O כיוון שעליך לקרוא את כל העץ. אנחנו צריכים למצוא דרך לביצוע יעיל בקשת טווח. כדי לפתור בעיה זו, מסדי נתונים מודרניים משתמשים בגרסה שונה של העץ הקודם בשם B+Tree. בעץ B+Tree:

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

כפי שאתה יכול לראות, יש כאן יותר צמתים (פעמיים). אכן, יש לך צמתים נוספים, "צמתי החלטה", שיעזרו לך למצוא את הצומת הנכון (שמאחסן את מיקום השורות בטבלה המשויכת). אבל מורכבות החיפוש היא עדיין O(log(N)) (יש רק עוד רמה אחת). ההבדל הגדול הוא זה צמתים ברמה התחתונה מחוברים ליורשיהם.

עם B+Tree זה, אם אתה מחפש ערכים בין 40 ל-100:

• אתה רק צריך לחפש 40 (או הערך הקרוב ביותר אחרי 40 אם 40 לא קיים) כמו שעשית עם העץ הקודם.
• לאחר מכן אסוף 40 יורשים באמצעות קישורי יורשים ישירים עד שתגיע ל-100.

נניח שאתה מוצא M יורשים ולעץ יש N צמתים. מציאת צומת ספציפי עולה יומן(N) כמו העץ הקודם. אבל ברגע שתקבל את הצומת הזה, תקבל M יורשים בפעולות M עם הפניות ליורשיהם. חיפוש זה עולה רק M+log(N) פעולות בהשוואה ל-N פעולות בעץ הקודם. יתר על כן, אינך צריך לקרוא את העץ המלא (רק צמתים M+log(N)), מה שאומר פחות שימוש בדיסק. אם M קטן (למשל 200 שורות) ו-N גדול (1 שורות), יהיה הבדל גדול.

אבל יש כאן בעיות חדשות (שוב!). אם תוסיף או תמחק שורה במסד הנתונים (ולכן באינדקס B+Tree המשויך):

• עליך לשמור על סדר בין הצמתים בתוך B+Tree, אחרת לא תוכל למצוא את הצמתים בתוך עץ לא ממוין.
• עליך לשמור על המספר המינימלי האפשרי של רמות ב-B+Tree, אחרת מורכבות הזמן O(log(N)) הופכת ל-O(N).

במילים אחרות, B+Tree חייב להיות מזמין ומאוזן. למרבה המזל, זה אפשרי עם פעולות מחיקה והוספה חכמות. אבל זה כרוך בעלות: הוספות ומחיקות בעץ B+ עולות O(log(N)). זו הסיבה שחלק מכם שמעו את זה שימוש ביותר מדי אינדקסים אינו רעיון טוב. בֶּאֱמֶת, אתה מאט הכנסה/עדכון/מחיקה מהירה של שורה בטבלהכי מסד הנתונים צריך לעדכן את האינדקסים של הטבלה באמצעות פעולת O(log(N)) יקרה עבור כל אינדקס. יתר על כן, הוספת אינדקסים פירושה עומס עבודה נוסף עבור מנהל עסקאות (יתואר בסוף המאמר).

לפרטים נוספים, אתה יכול לראות את המאמר בוויקיפדיה על B+עֵץ. אם אתה רוצה דוגמה ליישום B+Tree במסד נתונים, תסתכל מאמר זה и מאמר זה ממפתח MySQL מוביל. שניהם מתמקדים באופן שבו InnoDB (מנוע MySQL) מטפל באינדקסים.

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

טבלת גיבוב

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

טבלת hash היא מבנה נתונים שמוצא במהירות אלמנט לפי המפתח שלו. כדי לבנות טבלת גיבוב אתה צריך להגדיר:

• ключ עבור האלמנטים שלך
• פונקציית hash עבור מפתחות. הגיבובים המחושבים של המפתח נותנים את מיקום האלמנטים (נקרא קטעים ).
• פונקציה להשוואת מפתחות. לאחר שמצאת את הפלח הנכון, עליך למצוא את האלמנט שאתה מחפש בתוך הפלח באמצעות השוואה זו.

דוגמה פשוטה

ניקח דוגמה ברורה:

טבלת הגיבוב הזו כוללת 10 מקטעים. בגלל שאני עצלן, צילמתי רק 5 קטעים, אבל אני יודע שאתה חכם, אז אני אתן לך לצלם את 5 האחרים לבד. השתמשתי בפונקציית Hash modulo 10 של המפתח. במילים אחרות, אני מאחסן רק את הספרה האחרונה של המפתח של האלמנט כדי למצוא את הקטע שלו:

• אם הספרה האחרונה היא 0, האלמנט נכנס לקטע 0,
• אם הספרה האחרונה היא 1, האלמנט נכנס לקטע 1,
• אם הספרה האחרונה היא 2, האלמנט נכנס לאזור 2,
• ...

פונקציית ההשוואה שבה השתמשתי היא פשוט שוויון בין שני מספרים שלמים.

נניח שאתה רוצה לקבל רכיב 78:

• טבלת הגיבוב מחשבת את קוד הגיבוב עבור 78, שהוא 8.
• טבלת הגיבוב מסתכלת על קטע 8, והאלמנט הראשון שהיא מוצאת הוא 78.
• היא מחזירה לך פריט 78
• חיפוש עולה רק 2 פעולות (אחד כדי לחשב את ערך הגיבוב והשני כדי לחפש את האלמנט בתוך הקטע).

עכשיו נניח שאתה רוצה לקבל אלמנט 59:

• טבלת הגיבוב מחשבת את קוד הגיבוב עבור 59, שהוא 9.
• טבלת הגיבוב מחפשת בקטע 9, האלמנט הראשון שנמצא הוא 99. מכיוון ש-99!=59, אלמנט 99 אינו אלמנט חוקי.
• בעזרת אותו היגיון נלקחים האלמנט השני (9), השלישי (79), ..., האחרון (29).
• הרכיב לא נמצא.
• החיפוש עלה 7 פעולות.

פונקציית Hash טובה

כפי שאתה יכול לראות, בהתאם לתמורה שאתה מחפש, העלות אינה זהה!

אם עכשיו אני משנה את פונקציית הגיבוב modulo 1 של המפתח (כלומר לוקח את 000 הספרות האחרונות), הבדיקה השנייה עולה רק פעולה אחת מכיוון שאין אלמנטים בקטע 000. האתגר האמיתי הוא למצוא פונקציית Hash טובה שתיצור דליים המכילים מספר קטן מאוד של אלמנטים.

בדוגמה שלי, קל למצוא פונקציית Hash טובה. אבל זו דוגמה פשוטה, קשה יותר למצוא פונקציית Hash טובה כאשר המפתח הוא:

• מחרוזת (לדוגמה - שם משפחה)
• 2 שורות (לדוגמה - שם משפחה ושם פרטי)
• 2 שורות ותאריך (לדוגמה - שם משפחה, שם פרטי ותאריך לידה)
• ...

עם פונקציית Hash טובה, חיפושי טבלת Hash עולים O(1).

מערך לעומת טבלת hash

למה לא להשתמש במערך?

הממ, שאלה טובה.

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

למידע נוסף, אתה יכול לקרוא את המאמר על Javaמפת גיבוב, שהוא יישום יעיל של טבלת hash; אינך צריך להבין ג'אווה כדי להבין את המושגים המכוסים במאמר זה.

מקור: www.habr.com