3. חיפוש גיחה (Probe) – יש מידע מוקדם על מס' הרשומות בקובץ או על ההתפלגות שלהן ומשתמשים בזה כדי לעשות גיחה למען מסוים בקובץ, קצת לפני מיקום הרשומה המבוקשת, ומשם ממשיכים בחיפוש טורי (מגוש לגוש):
אם Z - מס' הגושים הנקראים, אמור להיות מספר קטן אז החיפוש מתבצע בתוך גליל אחד.
4. חיפוש אינטרפולציה (Interpolation) – שילוב של חיפוש גיחה קודם והמשך בחיפוש בינארי בשטח מצומצם:TA F ≈ O(log log b) * (s + r + btt +c) .
כל השיטות, פרט לחיפוש טורי, טובות רק כשמחפשים רשומה לפי שדה המפתח. חיפוש בקובץ סדרתי לפי שדה שאינו שדה המפתח הראשי הוא למעשה חיפוש כמו בערמה, עד שמגיעים לרשומה הרצויה.
לגבי קובץ C, החיפוש בשטח האב הוא כמו בקובץ סדרתי A, אבל אחרי מציאת התשובה הראשונה בקובץ האב חייבים להמשיך לחפש גם בקובץ התנועות, מכיוון שייתכן שלאותו מפתח יש רשומת עדכון, ביטול או הוספה בקובץ התנועות, ולכן חייבים לעבור על כל קובץ התנועות.
אם הנחנו שיש O מקומות בקובץ התנועות ובממוצע O’ תנועות, אזי עלות הבאת רשומה מקובץ התנועות היא:
זמן הבאת רשומה מקובץ התנועות (TF O) שווה לקריאת O’ רשומות במחיר של קריאת רשומה אחת. ולכן, בהכללה )לכל 4 שיטות החיפוש האפשריות בקובץ (A :
TF O + TA F= TC F
זמן הבאת רשומה מקובץ C שווה לזמן התייעצות עם הקובץ הראשי + זמן התייעצות עם קובץ התנועות.
גולשים מקוונים: 2