TF – זמן הבאת רשומה כלשהי.
בקובץ סדרתי A (קובץ ממוין) יש 4 שיטות חיפוש אפשריות:
1. חיפוש טורי(Serial search) – גוש אחר גוש, דורש מעבר על חצי קובץ בממוצע כדי למצוא רשומה:
קיבלנו ש TF של A שווה ל TF של ערימה TA F = TP F
וזה גרוע, אבל לא הגיוני להשתמש בחיפוש טורי בקובץ סדרתי ממוין,
לכן נפנה לשיטת החיפוש הבאה.
2. חיפוש בינארי (Binary searc (h
חיפוש לפי מפתח ראשי על גושי/רשומות הקובץ כדי להגיע למקום הרשומה המבוקשת. ניגשים לאמצע הקובץ בודקים אם הרשומה המבוקשת נמצאת שם,
אם לא שואלים האם הרשומה נמצאת בחצי העליון או בחצי התחתון של הקובץ ואל החצי המתאים ניגשים ושוב מחלקים אותו ל- 2 וכך הלאה עד למציאת או אי-מציאת הרשומה הרצויה.
כל גישה היא גישה לגוש בודד, לכן העלות של TF היא log2 של מס' הגושים בקובץ
(b) כפול זמן הזזת זרוע (s + r) + זמן קריאת הגוש (btt) + זמן עיבוד לרשומה (c).
c זה זמן מעבד לבדוק את מפתח הרשומה בהתחלת הגוש (שבאמצע הקובץ) ואולי גם את הרשומה בסופו, כדי לדעת אם זה הגוש בו נמצאת הרשומה המבוקשת.
אי אפשר לדעת את מען הגוש הבא לקריאה עד לסיום הבדיקה/חישוב cמיהו הגוש הבא שצריך לגשת אליו להמשך החיפוש.
גולשים מקוונים: 2