» נושאי לימוד
» נושאי לימוד
יום שישי 20 בספטמבר 2019
זמן הוספת רשומה כלשהי
דף ראשי  קובץ אינדקס סדרתי  זמן הוספת רשומה כלשהי גרסה להדפסה

מדד TI - זמן הוספת רשומה כלשהי.

 

הנחות: שרשור ברמת הגוש,  רשומות הגלישה נמצאות באותו גליל.

עלינו לקחת בחשבון שני מקרים (בדיעבד מסתבר שהעלות זהה לגבי שני המקרים):

 

 

1) הרשומה החדשה תכנס לגוש של השטח הראשי:

 

יש להגיע אל הגוש - TF

יש לכתוב את הגוש מחדש -  TRW , עם מצביע לגוש האחרון בשימוש של שטח הגלישה בגליל, שיכיל את הרשומה שנדחפה החוצה.

 

דוגמא:  נניח שרוצים להוסיף את k=25. ייקח לנו TF לאתר את מקום ההכנסה של k=25. נדחוק את 25 פנימה וכתוצאה מכך רשומה 29 תדחק החוצה. היא תכנס למקום הפנוי בשטח הגלישה ונעדכן את המצביעים כך ששרשרת הגלישה תהיה ממוינת.

 

 

בשטח הראשי: עושים גיווש מחדש כדי להכניס את 25 ולדחוק החוצה את 29 ולעדכן את המצביע אל שטח הגלישה (שיצביע על 29). העלות: TRW

 

בשטח הגלישה: צריכים לקרוא את הגוש הפנוי בשטח הגלישה כדי לקרוא את 29. העלות:  r+btt   לאחר מכן יש כתיבה חזרה ועדכון המצביעים בתוך שטח הגלישה - TRW

 

                                      

 

*  הערה TRW = 2r    

 20-01-04 / 22:45  עודכן ,  22-11-03 / 11:25  נוצר ע"י רועי לוי  בתאריך 
 טבלת חישוב הסתברויות - הקודםהבא - המשך זמן הוספת רשומה 
תגובות הקוראים    תגובות  -  0
דרכונט
מהי מערכת הדרכונט?
אינך מחובר, להתחברות:
דוא"ל
ססמא
נושאי לימוד
חיפוש  |  לא פועל
משלנו  |  לא פועל
גולשים מקוונים: 4