ארגון קבצים וגישה אליהם
הוצג| English | משמעות |
|---|---|
| file organisation/faɪl ˌɔːɡənaɪˈzeɪʃn/ | ארגון קבצים |
| access method/ˈækses ˈmeθəd/ | שיטת גישה |
| serial file/ˈsɪərɪəl faɪl/ | קובץ סדרתי |
| sequential file/siːˈkwenʃl faɪl/ | קובץ רצף-סדרי |
| key field/kiː fiːld/ | שדה מפתח |
| direct access/daɪˈrekt ˈækses/ | גישה ישירה |
| sequential access/siːˈkwenʃl ˈækses/ | גישה רצף-סדרית |
| random file/ˈrændəm faɪl/ | קובץ אקראי |
מדוע העבודה הלילית של הבנק נמשכה כל הלילה
- בשנות ה-1980 חשבונות הבנק נשמרו על סרט מגנטי. סרט ניתן לקריאה רק מקצה אחד לאחר, ולכן העסקאות של היום נסדרו בלילה והקובץ הראשי כולו נקרא מהתחלה לסוף, פעם אחת, כדי ליישם אותן.
- אם ביקשת את יתרת לקוח באמצע היום, התשובה הייתה: לא לפני מחר. ארגון הקובץ, ולא מהירות המחשב, קבעו מה שהבנק יכול להציע.
- דיסקים אפשרו ארגון שונה: לחשב את מיקום הרקורד מתוך המקדם שלו ולקפוץ לשם. זה בדיוק מה שמאפשר למכונת אוטומטית לתג תוך שנייה.
- שיעור זה עוסק בארגון קבצים, בשתי שיטות הגישה, ובאיך לבחור מתוך מה שהתוכנה עושה בעיקר.
שלושה ארגונים
- קובץ סריאלי (סדרתי) מכיל רקורדים בסדר ההופעה שלהם, ללא סינון. הוספה היא מהירה; חיפוש דורש קריאה מהתחלה. משמש ליומני מערכת ונתיבי בדיקה.
- קובץ סדרתי מכיל רקורדים ממוינים לפי שדה מקדם. החיפוש מהיר יותר, כי ניתן לעצור מוקדם או לבצע חיפוש בינארי; ההוספה איטית, כי רקורדים מאוחרים צריכים להזיז. משמש לקבצי ראשיים המועברים בקבוצות.
- קובץ רנדומלי (או קובץ בגישה ישירה) מכיל כל רקורד במיקום המחושב מהמקדם שלו, בדרך כלל באמצעות פונקציית Hash. חיפוש לפי מקדם הוא מאוד מהיר; קריאה בסדר המקדמים היא לא נוחה. משמש לטבלאות חיפוש גדולות וחשבונות לקוחות.
סריאלי: סדר ההופעה, אין יותר
סדרתי: אותו סוג רקורדים, בסדר מקדם
שתי שיטות הגישה
- גישה סדרתית קוראת מהתחלה של הקובץ ועד לרקורד הרצוי. זוהי הגישה היחידה שקובץ סריאלי מאפשר, וכך מעובד קובץ סדרתי בקבוצות.
- גישה ישירה מקפיצה ישירות למיקום ידוע ללא קריאה של מה שמגיע לפני כן. זוהי הדרך שבה נקרא קובץ רנדומלי, וקובץ סדרתי יכול גם כן להיות נקרא ישירות כאשר מיקום המקדם ידוע או מאונדקס.
- לכן זוגיות הסילבוס היא: גישה סדרתית לקבצים סריאליים וגם סדרתיים; גישה ישירה לקבצים סדרתיים וגם רנדומליים.
רנדומלי: המקדם אומר לך איפה לחפש
מסלול גישה לקובץ
עקבו אחר קובץ מהאחסון לתוכנית וחזרה בבטחה.
קובץ סדרתי מאחסן רשומות:
Difficulty 1/5 · 100 coins + a small bonus on first completion today
קבצים סדרתיים שומרים את הרשומות בסדר הגרסתן — מהיר להוספה, איטי לחיפוש. קבצים רציפים מסודרים לפי מפתח.
התאימו כל ארגון קבצים לסגנון האחסון של הרשומות.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
סדר הגעה = סדר ההגעה; רציף = מסודר; אקראי = מיקום מחושל; רציף-מדוד = מסודר + מדד.
קובץ אקראי (נגיש ישירות) שומר כל רשומה:
Difficulty 1/5 · 100 coins + a small bonus on first completion today
מפתח הופך (לרוב על ידי פונקציית חשיבה) למיקום, כך שהחיפוש לפי מפתח יחיד הוא מהיר מאוד.
מה ההבדל בין קובץ סדר הגעה לקובץ רציף?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
סדר הגעה לעומת סידור לפי מפתח. הבדל זה היחיד גורם לכך שקובץ רציף ניתן לחיפוש מוקדם אך איטי להוספה.
דוגמה פתורה: בחירת הארגון
- תוכנת משכורות קוראת כל רקורד של עובד פעם בחודש, בסדר מספר עובד, כדי להפיק שוטרי שכר. איזה ארגון ואיזו גישה, ולמה?
- ארגון סדרתי עם גישה סדרתית: כל רשומה מעובדת, ולכן אין יתרון לקפוץ בין נקודות, ואחסוןן בסדר מפתחות אומר שהצ'קים יוצאים בסדר ללא צורך בשלב מיון.
- מכונת אוטומט חייבת למצוא חשבון אחד לפי מספרו תחת שנייה. ארגון אקראי עם גישה ישירה: המיקום מחושב מהמספר של החשבון, ולכן נדרשת קריאה אחת בדיוק במקום לחפש במיליונים.
- אפליקציית שרת אתר מצרפת שורה אחת לכל בקשה ללוג. סדרתי: רק הצרפה חשובה, והצרפה בסוף היא הפעולה המהירה ביותר שאקבץ סדרתי יכול לבצע.
קובץ רציף ניתן לקריאה באמצעות גישה רציפה וגם באמצעות גישה ישירה.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
גישה רציפה משמשת קבצי סדר הגעה וקבצים רציפים; גישה ישירה משמשת קבצים רציפים ואקראיים. רק קובץ סדר הגעה מוגבל לשיטה אחת.
סדרו את שלבי החיפוש של חשבון אחד מקובץ אקראי.
Difficulty 3/5 · 200 coins + a small bonus on first completion today
אין חיפוש כלל: המפתח הופך למיקום ונקרא פעם אחת. הבדיקה הסופית חושפת התנגשות.
ההשלכות, זה לצד זה
| סדרתי | סדרתי | אקראי | |
|---|---|---|---|
| סדר הרשומות | כנוספו | ממוין לפי מפתח | מחושב מהמפתח |
| הוספת רשומה | מהיר, הצרפה | איטי, הרשומות זזות | מהיר, אם המיקום פנוי |
| מציאת רשומה אחת | איטי, קוראים הכל | מהיר יותר, ניתן לעצור מוקדם | המהיר ביותר, קריאה אחת |
| קריאה בסדר מפתחות | דורש מיון | טבעי | דורש מיון |
- התשובה הנכונה תמיד מבוססת על ה-פעולה הדומיננטית: מה העשייה המרכזית של תוכנה זו?
ארגון קובץ רצפי מתאים לעיבוד כל ריקוד בתורו.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
גישה ישירה מתאימה לחיפוש ריקוד יחיד.
התאם כל מצב לארגון הקובץ המתאים לו.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
הוספה בלבד, עיבור הכל בסדר, או חיפוש ריקוד יחיד: הפעולה הדומיננטית קובעת את הארגון.
דוגמה פתורה: נימוק שינוי
- קובץ הספרים בספרייה הוא סדרתי. חיפוש ספר אחד הוא איטי. הציע שינוי ונמק אותו.
- ארגן מחדש כקובץ אקראי, על ידי השחתת המספר הבינלאומי (ISBN) למיקום, כך שהחיפוך יהפוך לקריאה ישירה אחת במקום לסרוק את הקובע כולו.
- אם הספרייה מדפיסה גם קטלוג בסדר שמות, ארגון סדרתי לפי שמות ישרת שתי מטרים סבירות: הקטלוג לא דורש מיון, וחיפוש יכול להיעצר מוקדם או להשתמש בחיפוש בינארי.
- קרא לארגון, קרא לשיטת הגישה, וחבר את שניהם לפעולה שהשאלה מזכירה.
ליצירת דוחות בסדר מפתח, ארגון הקובי הטוב ביותר הוא:
Difficulty 1/5 · 100 coins + a small bonus on first completion today
קובץ רציפי כבר במצב סדר מפתח, ולכן קריאה רציפית שלו נותנת דוח בסדר.
ארגון קובי נבחר על ידי הצצה לפעולה ____ של התוכנה.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
כל ארגון מהיר בדבר מה ואיטי בדבר אחר, ולכן הפעולה שנעשתה הכי הרבה קובעת.
מה שהמפתח חייב להיות, ולמה השחזה שוברת
- גישה ישירה דורשת מפתח, והמפתח חייב להיות ייחודי לרשומה אחת. שם משפחה אינו מפתח; מספר לקוח כן.
- השחזה ממרת את המפתח למיקום רשומה בחישוב אחד, כך שקריאה אחת מגיעה לרשומה ללא קשר לגודל הקובע.
- שני מפתחות שונים יכולים לשחזר לאותו מיקום. זהו תנגשות, ואינו תקלה באלגוריתם: זה בלתי נמנע ברגע שישנם יותר מפתחות אפשריים מאשר מיקומים.
- הפתרון שנכתב בתכנית האומדן הוא אזור עדיפות, או אחסון מצביע במיקום אל שרשרת רשומות שתורשות אותו. תנגשות לכן עולה בקריאה נוספת, ולא באובדן רשומה.
- לכן ההשוואה המוצדקת היא: גיבוי (hashing) מספק גישה קרובה לקבועה עד למילוי הקובץ, וביצועיו מתדרדרים ככל שהעומס מהתנגשויות עולה. גישה רציפה לעולם לא מתדרדרת, אך מעולם לא הייתה מהירה.
שני ריקודים מתגשים למאותו כתובת. איזה טענות נכונות? סמן את כולן החלות.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
אין אובדן; ההתנגשות דורשת קריאה נוספת בלבד. היא בלתי נמנעת בעיקרון, מכיוון שתמיד ישנם יותר מקשיים אפשריים מאשר כתובות.
סימונים נופלים מהיד
- סדר הוא סדר הגעה; רציף הוא ממוין לפי מפתח. הם אינם סינונימים, והמבחן בודק בדיוק את ההבדל הזה.
- ארגון הוא האופן שבו השטחים מונחים; גישה היא האופן שבו התוכנית מגיעה לשטח אחד. שאלה תכנה אחת או את השנייה.
- קובץ רציף תומך בשתי שיטות הגישה; קובץ סדר תומך רק בגישה רציפה.
- נמקו מהפעולה הדומיננטית, ולא מ"זה מהיר יותר". ציינו מה מהיר, ולמה.
הבנתך מושלמת
- סדר: סדר הוספה, הוספה מהירה, חיפוש איטי, משמש ליומנים · רציף: ממוין לפי שדה מפתח, מתאים לעיבוד חבילות ולתפוקה בסדר · אקראי: מיקום מחושב מהמפתח של השטח, קריאה אחת כדי למצוא שטח
- גישה רציפה קוראת מהתחלה; גישה ישירה קופצת למיקום מסוים
- גישה רציפה משמשת קבצים סדר ורציפים; גישה ישירה משמשת קבצים רציפים ואקראיים
- בחרו מהפעולה הדומיננטית: לעבד הכל, לחפש שטח אחד, או להוסיף בלבד