» נושאי לימוד
» נושאי לימוד
יום רביעי 17 ביולי 2019
שיטות חיפוש 2
דף ראשי  קובץ סדרתי  שיטות חיפוש 2 גרסה להדפסה

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 שווה לזמן התייעצות עם הקובץ הראשי + זמן התייעצות עם קובץ התנועות.

 21-02-04 / 21:32  עודכן ,  18-11-03 / 00:06  נוצר ע"י רועי לוי  בתאריך 
 שיטות חיפוש 1 - הקודםהבא - מדד הבאה של הרשומה הלוגית הבאה 
תגובות הקוראים    תגובות  -  0
דרכונט
מהי מערכת הדרכונט?
אינך מחובר, להתחברות:
דוא"ל
ססמא
נושאי לימוד
חיפוש  |  לא פועל
משלנו  |  לא פועל
גולשים מקוונים: 3