2.65M
Category: informaticsinformatics

ذخیره و بازیابی اطلاعات(3)

1.

‫ترجمه‪:‬‬
‫مهندس عين ا‪ ...‬جعفرنژاد قمي‬
‫ابراهيم محرابي‬
‫تعداد واحد‪3 :‬‬
‫‪1‬‬

2.

‫فهرست جلسات‬
‫جلسه اول‪ :‬آشنايي با طراحي و مشخصات ساختار فايلها‪ ،‬عمليات مهم‬
‫پردازش فايل‪ ،‬حافظه جانبي و نرم افزار سيستم‬
‫جلسه دوم‪ :‬ادامه مبحث حافظه جانبي و نرم افزار سيستم‬
‫جلسه سوم‪ :‬ادامه مبحث حافظه جانبي و نرم افزار‬
‫سيستم‬
‫جلسه چهارم‪ :‬مفاهيم اساسي ساختار فايل‪ ،‬مديريت فايلهايي از رکوردها‬
‫جلسه پنجم‪ :‬ادامه مبحث مديريت فايلهايي از رکوردها‬
‫جلسه ششم‪ :‬ادامه مبحث مديريت فايلهايي از رکوردها‪ ،‬سازماندهي فايلها براي‬
‫کارايي‬
‫‪2‬‬

3.

‫فهرست جلسات‬
‫جلسه هفتم‪ :‬ادامه مبحث سازماندهي فايلها براي کارايي‪ ،‬شاخص گذاري‬
‫جلسه هشتم‪ :‬ادامه مبحث شاخص گذاري‬
‫جلسه نهم‪ :‬ادامه مبحث شاخص گذاري‪ ،‬پردازش کمک‬
‫ترتيبي و مرتب سازي فايل هاي بزرگ‬
‫جلسه دهم‪ :‬ادامه مبحث پردازش کمک ترتيبي و مرتب سازي فايل هاي بزرگ‬
‫جلسه يازدهم‪ :‬ادامه مبحث پردازش کمک ترتيبي و مرتب سازي‬
‫فايلهاي بزرگ‪ ،‬شاخص بندي چند سطحي و درختهاي ‪B‬‬
‫جلسه دوازدهم‪ :‬ادامه مبحث شاخص بندي چند سطحي و‬
‫درختهاي ‪B‬‬
‫‪3‬‬

4.

‫فهرست جلسات‬
‫جلسه سيزدهم‪ :‬دستيابي به فايل هاي ترتيبي شاخص دار و درخت هاي‬
‫‪B+‬‬
‫جلسه چهاردهم‪ :‬ادامه مبحث دستيابي به فايل هاي ترتيبي شاخص دار و‬
‫درخت هاي ‪ ،B+‬درهم سازي‬
‫جلسه پانزدهم‪ :‬ادامه مبحث درهم سازي‬
‫جلسه شانزدهم‪ :‬ادامه مبحث درهم سازي‪ ،‬درهم سازي قابل‬
‫توسعه‬
‫‪4‬‬

5.

‫• آشنايي با طراحي و مشخصات ساختار فايلها‬
‫• عمليات مهم پردازش فايل‬
‫• حافظه جانبي و نرمافزار سيستم‬
‫‪5‬‬

6.

‫آشنايي با طراحي و مشخصات ساختار فايلها‬
‫‪6‬‬

7.

‫ساختار فايل ترکيبي از نحوه نمااي اااه ااا ار فايال‬
‫اااا و لمليااات بزا بااراا اسااتيابي بااا اااه اااا اساات‪.‬‬
‫ساااختار فاياال بااا برناماا کاااربراا ايااک امراااک را مااي‬
‫ااا کا اااه اا را بخوانا ‪،‬بنويسا و اصالح کنا‪.‬‬
‫‪7‬‬

8.

‫طي سا ااا اخير با بررسي ترامل ساختارااا فايل‬
‫مشاااه مي کنيا کا طراحي ساختار فايل ابتاا از ترتيباي‬
‫شااارود شاااا ‪،‬ساااتا باااا سااااختارااا ارختاااي رسااايا و‬
‫سرانجاا استيابي مستقيا مطرح شا‪ .‬ار اما اياک ماوارا‬
‫مشااارالت و ابزاراااااا طراحاااي مشاااابهي مشااااااه شااااه‬
‫اساات‪ .‬ايااک ابزاراااا را ابزارااااا ممهااومي مااي نامنااا کااا‬
‫رو اايي براا تنظيا و حل يک مسئلا طراحي انا‪.‬‬
‫‪8‬‬

9.

‫يک مشرل اصلي ار توصيف کاالا ااايي کاا بتاواک‬
‫براا طراحي ساختار فايل آنها را با کار برا ‪ ،‬آک است‬
‫کا ايک کالا ااا تيييااه و ار حاال رشاا اساتنا‪ .‬کاالا‬
‫ااا جايا غالبا ً شرل اصالح شاه يا توسعا يافتا اا از‬
‫کالا اا ايگار باواه ‪،‬جزئياات ارائاا اااه ااا و لملياات‬
‫باز اا تييياه تر مي شوا‪.‬‬
‫‪9‬‬

10.

‫ار يااک سيسااتا اطاللاااتي شاايت ااارا محتااوا و رفتااار‬
‫اااه ااااا ‪ ،‬ار ياااک طراحاااي منساااجا ماااي شاااوا‪ .‬اشاااياا‬
‫سيساتا بااا کااالا اااا اشاايايي بااا ويتااي ااااا مشااترک‬
‫تقساااااايا مااااااي شااااااونا‪ .‬ااااااار کااااااالا توسااااااط ال اااااااا‬
‫(‪ )members‬خااوا توصاايف مااي شااوا کااا يااا صاامات‬
‫اااه اااا (ل ااوااا اااه اا) يااا تواب ا (تواب ا ل ااو يااا‬
‫متااا) استنا‪.‬‬
‫‪10‬‬

11.

‫مشاارل اصاالي ار طراحااي ساااختار فاياال زماااک نساابتا ً‬
‫زيااا است کا باراا اارفتک تطاللاات از ايساک ماورا‬
‫نياااز اساات‪ .‬ار امااا طراحااي ااااا ساااختار فاياال آنيااا‬
‫مورا توجا است با حا اقل رساناک افعات اساتيابي باا‬
‫ايسااک و بااا حااا اکناار رساااناک احتمااال وجااوا اطاللااات‬
‫مورا نظر برناما کاربراا ار حافظا است‪.‬‬
‫‪11‬‬

12.

‫لمليات مها ترااز‬
‫‪12‬‬
‫فايل‬

13.

‫انگااامي کااا ارباااره فااايلي روا يااک ايسااک يااا ناااوار‬
‫صحبت ماي کنايا ‪،‬منظاور ماا مجمولاا اا از بايات ااا اسات‬
‫کااااا ار آنجااااا هخيااااره شاااااه انااااا‪ .‬فاياااال ار ايااااک معنااااا ااراا‬
‫موجواياات فيزيرااي اساات‪ .‬يااک ايسااک ممرااک اساات حاااوا‬
‫صااا و حتي ازاراک فايل فيزيري باشا‪.‬‬
‫‪13‬‬

14.

‫برناما غالبا ً نمي ااناا بايات ااا از کجاا ماي آيناا ياا باا‬
‫کجااا مااي رونااا ‪ ،‬ايااک را مااي اانااا کااا کااااا خااط را مااورا‬
‫استمااه قرار اااه است‪ .‬ايک خطوط را معموبً فايل منطقي‬
‫مي نامنا تا از فايل فيزيري ‪،‬کا روا ايسک يا نوار قرار‬
‫اارا متمايز اراا‪.‬‬
‫‪14‬‬

15.

‫انگامي کا شناسا (‪ )identifier‬فايل منطقي با استگاه يا‬
‫فايل فيزيري ارتباط تياا کرا ‪،‬بايا الالا کنيا کا مي خواايا با‬
‫فايل يا کنيا ‪:‬‬
‫‪ )۱‬باز کراک يک فايل موجوا‬
‫‪ )۲‬ايجاا يک فايل جايا و حهف محتويات موجوا ار‬
‫فايل فيزيري‬
‫‪15‬‬

16.

‫انگامي کا برناما اا با صورت لااا تاياک مي ياباا‬
‫فاياال اااا معمااوبً بااا طااور خواکااار بسااتا مااي شااونا‪ .‬ار‬
‫نتيجااا اجااراا يااک اسااتور بسااتک ار ااخاال برنامااا فقااط‬
‫بااراا محافظاات آک ار براباار اتااالف اااه اااا ار صااورت‬
‫توقااف برنامااا و آزاا کااراک ناااا فاياال ااااا منطقااي بااراا‬
‫استمااه اوباره رورا است‪.‬‬
‫‪16‬‬

17.

‫خوانااااک و نوشاااتک ار تااارااز فايااال ااميااات بنياااااا‬
‫اارنا ‪،‬اينها المالي استنا کاا تارااز فايال را باا ياک‬
‫لمل ورواا‪/‬خروجي تبايل مي کننا‪.‬‬
‫‪17‬‬

18.

‫براا استيابي آساک با تعااا زيااا از فايال ااا کاامتيوتر‬
‫روشااي بااراا سااازمانااي فاياال اااا اارا‪ .‬ار يااونيرا ايااک‬
‫رو سيستا فايل نامياه مي شاوا‪ .‬ياوک اار نااا فايال ار‬
‫سيستا يونيرا بخشي از سيستا فايلي است کا باا ريشاا‬
‫آغاز مي شوا ‪،‬ار فايل را مي تواک انحصاارا ً باا اااک نااا‬
‫مسير آک شناسايي کرا‪.‬‬
‫‪18‬‬

19.

‫يرااي از تاار قااارت تااريک اياااه اااا ار يااونيرا تعريمااي‬
‫است کا از فايل مي شاوا‪ .‬ار ياونيرا فايال مجمولاا اا‬
‫از بايت اا است و يگاونگي و محال هخياره آنهاا ااا مهاا‬
‫نيساات‪ .‬اميناايک مهااا نيساات کااا ايااک باياات اااا از کجااا مااي‬
‫آينا‪ .‬ايک نگر معمولي با فايل موجب مي شاو کاارا را‬
‫کا ار سيستا لامل ااا ايگر با زحمت انجااا ماي شاونا‬
‫‪ ،‬ار ايک سيستا لامل با راحتي انجاا تهير باشا‪.‬‬
‫‪19‬‬

20.

‫يونيرا فرماک ااا بسيارا براا استرارا فايل اا اارا‬
‫کا لبارتنا از ‪:‬‬
‫‪cat, tail, cp, mv, rm, chmod, ls, mkdir, rmdir‬‬
‫‪20‬‬

21.

‫حافظا جانبي و نرا افزار سيستا‬
‫‪21‬‬

22.

‫استگاه ااا حافظا جانبي ‪،‬با حافظا تماوت بسيار اارناا‪.‬‬
‫اماک طور کا تي از ايک نياز متاهکر شاايا ياک اخاتالف از‬
‫آنجا ناشي مي شوا کا ار استگاه ااا حافظا جاانبي زمااک‬
‫بيشااترا بااراا اسااتيابي مااورا نياااز اساات‪ .‬اخااتالف ايگار آک‬
‫است کا اما استيابي اا يرساک نيستنا‪.‬‬
‫‪22‬‬

23.

‫ايسک اا انواد مختلمي اارنا ‪:‬‬
‫‪ )۱‬ايسک ااا سخت (‪)hard disks‬‬
‫‪ )۲‬ايسک ااا فالتي (‪)floppy disks‬‬
‫‪ )۳‬کارتريج ايسک‬
‫‪ )۴‬ايسک ااا نورا‬
‫‪23‬‬

24.

‫• ادامه مبحث حافظه جانبي و نرم افزار سيستم‬
‫‪24‬‬

25.

‫اطاللات هخيره شاه روا ايسک ‪،‬ار سطح يک ياا‬
‫ينا صامحا نگهااارا ماي شاوا‪ .‬ترتياب کاار باا صاورتي‬
‫اسااات کاااا اطاللاااات باااا صاااورت شاااياراايي (‪)tracks‬‬
‫روا سطح ايسک نگهاارا ماي شاونا‪ .‬اار شايار غالباا ً‬
‫بااا ينااا ساارتور (‪ )sector‬تقساايا مااي شااوا‪ .‬ساارتور‬
‫کااويرتريک بخشااي از ايسااک اساات کااا قاباال آارا اااي‬
‫است‪.‬‬
‫‪25‬‬

26.

26

27.

‫ايسک ارااک اا معموبً ينا صمحا اارنا‪ .‬شياراايي کاا‬
‫مستقيما ً ار باب و تاييک يرايگر قرار اارنا ‪،‬يک سايلنار را‬
‫تشااريل مااي اانااا‪ .‬اامياات ساايلنار ار آک اساات کااا بااا ام اا‬
‫اطاللاااات روا ياااک سااايلنار ماااي تاااواک بااااوک حرکااات اااک‬
‫بااازوا نگهاارناااه اااا (‪ )head‬خواناااک‪/‬نوشااتک اسااتيابي‬
‫ااشت‪ .‬حرکت ايک بازو تيگرا (‪ )seeking‬ناا اارا‪.‬‬
‫‪27‬‬

28.

28

29.

‫ظرفياات ايسااک تااابعي از تعااااا ساايلناراا ‪،‬تعاااا شااياراا ب اا‬
‫ازاا ار سيلنار و ظرفيت ار شيار است‪.‬‬
‫‪29‬‬

30.

‫او رو‬
‫براا سازمانااي اااه اا بر روا ايسک وجوا اارا ‪:‬‬
‫‪ )۱‬بر اساا سرتور‬
‫‪ )۲‬بر اساا بلوک ااا تعريف شاه توسط کاربر‬
‫‪30‬‬

31.

‫کالستر لبارت از تعااا نابتي از سرتورااا تيوستا‬
‫است‪.‬‬
‫مايريت فايل براا ار نظر ارفتک فايل با لنواک‬
‫مجمولا اا از کالستراا و ار ليک حال حمظ حالت‬
‫سرتورا ‪،‬سرتورااا منطقي را با کالسترااا‬
‫فيزيري کا با آنها تعلق اارا ‪،‬با وسيلا جاول‬
‫تخصيص فايل (‪ )FAT‬ارتباط مي ااا‪.‬‬
‫‪31‬‬

32.

‫اااار ف اااا زيااااا روا ايسااک باشااا ‪ ،‬ممرااک اساات‬
‫بتااواک کااارا کاارا کااا فاياال بااا طااور کاماال از کالسااترااا‬
‫تيوستا تشريل شوا‪ .‬ار ينيک موراا امتا ماي شاوا کاا‬
‫فايل حاوا يک حا (‪ )extent‬است‪.‬‬
‫‪32‬‬

33.

33

34.

‫اتالف ف ا ار ااخل ياک سارتور را تراکناااي ااخلاي‬
‫ماااي نامناااا‪ .‬ساااازمانااي بلاااوک ااااا مشااارالت توشاااايي‬
‫ساارتوراا و تراکنااااي را ناااارا ‪،‬زياارا اناااازه بااالک ااا‬
‫ماااي تواناااا تنييااار کناااا تاااا ساااازمانااي منطقاااي اااه ااااا‬
‫امراک تهير شوا‪.‬‬
‫‪34‬‬

35.

‫بلااوک معمااوبً طااورا سااازمانااي مااي شااوا کااا تعااااا‬
‫مناساابي از رکوراااااا منطقااي را نگهاااارا کنااا‪ .‬بااراا‬
‫اشاره با تعااا رکورااايي کا قرار اسات ار اار ياک از‬
‫بااالک ااااا فاياال نگهاااارا شااونا ‪،‬از اصااطالح ااريب‬
‫بلوک بناا استمااه مي شوا‪.‬‬
‫‪35‬‬

36.

‫ار الگواااا آارا اااي بالکااي اار بلاوک از اااه اااا‬
‫معموبً با يک يا يناا زيار بلاوک (‪ )subblock‬اماراه‬
‫است کا حاوا اطاللات ا افي راجا باا بلاوک اااه ااا‬
‫اساات‪ .‬معمااوبً يااک زيربلااوک شمارشااي وجااوا اارا کااا‬
‫تعااااا باياات ااااا موجااوا ار بلااوک مربااوط را نگااا مااي‬
‫اارا‪ .‬امينيک ممرک است کا يک زيربلوک کليا ‪،‬حاوا‬
‫کليا مربوط با آخريک رکورا ار بلوک اااه اا باشا‪.‬‬
‫‪36‬‬

37.

‫اااا بااالک اااا و اااا ساارتوراا نيازمنااا آننااا کااا مقاااار‬
‫معينااي از ف اااا ايسااک را بااا شاارل سااربار غياار اااه اا‬
‫اشنال کننا‪ .‬بخشي از ايک سربار از اطاللااتي تشاريل ماي‬
‫شوا کا طي فرمات کاراک ‪،‬بار روا ايساک نگهااارا ماي‬
‫شااوا‪ .‬فرماات کااراک ‪،‬تااي از آنرااا ايسااک بتوانااا مااورا‬
‫استمااه قرار ايرا ‪،‬صورت مي تهيرا‪.‬‬
‫‪37‬‬

38.

‫فرمت کراک موجب مي شوا تا شراف (‪ )gap‬و‬
‫لالمت ااا اا زماک سازا ‪،‬بيک فيلاااا اطاللاتي قرار‬
‫اااه شوا تا مرانيزا خواناک‪/‬نوشتک ‪ ،‬بيک آنها تمايز قائل‬
‫شوا‪.‬‬
‫‪38‬‬

39.

‫استيابي با ايسک را مي تواک با سا لمل فيزيري متمايز تقسيا‬
‫کرا کا ار يک ازينا خوا را اارا ‪:‬‬
‫‪ )۱‬زماک تيگرا (‪)seek time‬‬
‫‪ )۲‬تأخير يرخشي (‪)rotational delay‬‬
‫‪ )۳‬زماک انتقال (‪)transfer time‬‬
‫‪39‬‬

40.

‫• ادامه مبحث حافظه جانبي و نرم افزار سيستم‬
‫‪40‬‬

41.

‫زماک تيگرا لبارت اسات از زمااک بزا انتقاال‬
‫بازوا استيابي ‪،‬با سيلنار مناسب‪.‬‬
‫‪41‬‬

42.

‫تأخير ار يرخ لبارت است از زمااک بزا باراا‬
‫يااارخ ايساااک ‪،‬تاااا سااارتور ماااورا نظااار زيااار ااااا‬
‫خواناک‪/‬نوشتک قرار ايرا‪.‬‬
‫‪42‬‬

43.

‫للي رغا افزاي کارايي ايسک اا ‪،‬سرلت شبرا اا‬
‫با حاا باب رفتا است کا استيابي با ايسک غالبا ً‬
‫تنگناا مهمي ار کل سيستا ‪ I/O‬با شمار مي روا‪.‬‬
‫ينا ترنيک براا مقابلا با ايک مشرل وجوا اارا ‪:‬‬
‫‪ )۱‬نواربناا‬
‫‪ )۲‬استمااه از ايسک ‪RAM‬‬
‫‪ )۳‬حافظا نهاک‬
‫‪43‬‬

44.

‫نوارااا منناطيسي با اساتگاه ااايي تعلاق اارناا کاا‬
‫اسااتيابي مسااتقيا بااا اااه اااا را فاارااا نمااي آورنااا ولاي‬
‫اسااتيابي ترتيبااي بااا ساارلت انجاااا مااي شااوا‪ .‬نواراااا‬
‫فشراه انا ‪،‬شارايط محيطاي متمااوت را خاوب تحمال ماي‬
‫کننا‪،‬نگهااااارا و حمااال آنهاااا آسااااک اسااات و ارزانتااار از‬
‫ايسک اا استنا‪.‬‬
‫‪44‬‬

45.

‫نقااااط قاااوت ‪ CD-ROM‬شاااامل ظرفيااات هخياااره ساااازا‬
‫باب‪،‬بهاااا کااا و اواا آک اساات‪ .‬نقط اا ااعف اصاالي آک ايااک‬
‫اسااات کاااا جساااتجو ار ‪ CD-ROM‬بسااايار کناااا اسااات‪،‬يعني‬
‫غالبا ً ار جستجو نيا تا يک نانيا طول مي کشا‪.‬‬
‫‪45‬‬

46.

‫ار قالب سرلت خطي نابت (‪، )CLV‬سرلت يارخ‬
‫ايسک انگاا خواناک لبا ااا بيروني ‪،‬کنااتر از انگااا‬
‫خواناک لبا ااا ااخلي است‪.‬‬
‫ار سرلت زاويا اا نابت (‪، )CAV‬ايسک با شيارااا‬
‫متحاالمرکز و سرتورااا ماور خوا ‪،‬اااه اا را با تراکا‬
‫کمترا ار شيارااا خارجي نسبت با شيارااا ااخلي مي‬
‫نويسا‪.‬‬
‫‪46‬‬

47.

47

48.

‫بافر ‪ I/O‬سيستا ‪،‬با مايريت فايل ايک امراک را مي‬
‫ااااا تااا اااه اااا را ار واحااااايي بااا اناااازه ساارتور يااا‬
‫بلوک بخوانا يا بنويسا‪.‬‬
‫‪48‬‬

49.

‫لمل کنترل لمليات ايسک توسط اساتگااي انجااا‬
‫مي شوا کا کنترلگر ايسک نامياه مي شوا‪.‬‬
‫‪49‬‬

50.

‫سيساتا اااا ‪ I/O‬تقريباا ً اميشااا حاااقل او باافر اارناا‪.‬‬
‫يرااااي بااااراا ورواا و ايگاااارا بااااراا خروجااااي‪ .‬برخااااي‬
‫سيستا ااا فايل از يک طرح بافرااي موسوا باا اساتخر‬
‫بافرا (‪ )buffer spooling‬استمااه مي کننا‪.‬‬
‫‪50‬‬

51.

‫با تراکن ورواا ‪،‬با يک بار خواناک ‪،‬نا يک بار بافر‬
‫بلرا مجمولا اا از بافراايي کا اااه ااا يک بلوک بايا‬
‫ار آک اا تخ شوا شناسايي مي شوا‪.‬‬
‫با تمرکز خروجي ‪،‬ينا بافر را مي تواک ارااا آورا و‬
‫يرباره بر روا اما آنها نوشت ‪،‬بايک ترتيب بزا نيست‬
‫آنها را ار يک بافر خروجي کتي کرا‪.‬‬
‫‪51‬‬

52.

‫استا با نوبت با ايک يهار جاول زير مراجعا مي کنا تا‬
‫اطاللاتي را کا براا نوشتک ار فايل موجوا ار ايسک نياز اارا‬
‫با است آورا ‪:‬‬
‫‪ )۱‬جاول توصيف ار فايل‬
‫‪ )۲‬جاول فايل ااا باز‬
‫‪ )۳‬جاول تخصيص فايل‬
‫‪ )۴‬جاول اره ااا انايسي‬
‫‪52‬‬

53.

53

54.

‫اشاره ارا از يک فهرست با ايناوا فايال را اتصاال‬
‫سخت (‪ )hard link‬مي نامناا و اتصاال نارا ( ‪soft‬‬
‫‪ )link‬يا اتصال سمبوليک ‪ ،‬ناا فايال را باا جااا فايال‬
‫واقعي ‪،‬با يک ناا فايل ايگر مرتبط مي سازا‪.‬‬
‫‪54‬‬

55.

‫سا نود سيستا ‪ I/O‬متماوت ااريا ‪:‬‬
‫‪ )۱‬سيستا ‪ I/O‬بلوکي‬
‫‪ )۲‬سيستا ‪ I/O‬کاراکترا‬
‫‪ )۳‬سيستا ‪ I/O‬شبرا اا‬
‫‪55‬‬

56.

‫براا ار استگاه جانبي مجمولا اا از روال ااا جاااانا‬
‫وجوا اارا کا راه انااز استگاه نامياه مي شوا‪.‬‬
‫‪56‬‬

57.

‫• مفاهيم اساسي ساختار فايل‬
‫• مديريت فايلهايي از رکوردها‬
‫‪57‬‬

58.

‫مماايا اساسي ساختار فايل‬
‫‪58‬‬

59.

‫واحا اصلي اااه اا‪،‬فيلا است کا حاوا يک مقاار اااه است‪.‬‬
‫فيلااا با صورت مجمولا اا از اااه اا يا باا صاورت کتاي اااا‬
‫متعااااااا از يااااک فيلااااا (آرايااااا) يااااا ليسااااتي از فيلاااااااا متماااااوت‬
‫(رکورا)سازمانااي مي شونا‪.‬‬
‫‪59‬‬

60.

‫انگامي کا رکوراا ار حافظا نگهاارا شا آک را‬
‫يک شيت و فيلاااا آک را ال اا آک مي نامنا‪.‬‬
‫‪60‬‬

61.

‫رااهاا فراواني براا افزواک ساختار با فايل وجوا اارا‬
‫تا اويت فيلا حمظ شوا‪.‬‬
‫يهار رو‬
‫متااول لبارتنا از ‪:‬‬
‫‪ )۱‬نابت کراک طول فيلااا‬
‫‪ )۲‬قرار اااک نشانگر طول فيلا ار ابتااا ار فيلا‬
‫‪ )۳‬جاا کراک فيلااا با فاصل‬
‫‪ )۴‬استمااه از لبارت کلياا براا شناسايي فيلااا‬
‫‪61‬‬

62.

‫رکورا مجمولا اا از فيلا اا است و مجمولا اا از رکورااا‬
‫فايل را نشاک مي اانا‪.‬‬
‫‪62‬‬

63.

‫بع ي از رو‬
‫ااا سازمانااي رکوراااا فايل لبارتنا از ‪:‬‬
‫‪ )۱‬قابل تي بيني کراک طول رکورااا بر حسب بايت‬
‫‪ )۲‬قابل تي بيني کراک طول رکورااا بر حسب فيلااا‬
‫‪ )۳‬شرود ار رکورا با نشانگر طول‬
‫‪ )۴‬استمااه از انايا براا نگهاارا آارا اا‬
‫‪ )۵‬قرار اااک فاصل ار انتهاا ار رکورا‬
‫‪63‬‬

64.

‫او رو‬
‫براا نماي‬
‫طول رکورا وجوا اارا ‪:‬‬
‫‪ )۱‬طول رکورا با صورت يک لاا صحيح او بايتي ‪،‬‬
‫قبل از ار فيلا ايگر رکورا نوشتا شوا‪.‬‬
‫‪ )۲‬تبايل طول با يک کاراکتر رشتا اا با استمااه از‬
‫خروجي فرمت بناا شاه‬
‫‪64‬‬

65.

‫با روبراارا فايل مي تواک بايت ااا واقعي‬
‫نگهاارا شاه ار آک را مشاااه کرا‪.‬‬
‫‪65‬‬

66.

‫‪ C++‬ورانت را ار اختيار قرار مي ااا تا ينايک کالا‬
‫مي تواننا از ال ا و متاااا مشترک استمااه کننا‪.‬‬
‫‪66‬‬

67.

67

68.

‫مايريت فايلهايي از رکورااا‬
‫‪68‬‬

69.

‫انگامي کا کارايي جستجوااا انجاا شاه ار حافظا‬
‫الرترونيري را توصيف مي کنيا معموبً از تعااا‬
‫مقايسا ااا مورا نياز براا جستجو ‪،‬با لنواک واحا‬
‫کار استمااه مي کنيا‪.‬‬
‫‪69‬‬

70.

‫با طورکلي ‪،‬کار مورا نياز براا جستجوا ترتيبي ‪ ،‬ار‬
‫فايلي با ‪ n‬رکورا با ‪ n‬متناسب است ‪:‬‬
‫حااکنر ‪ n‬مقايسا و با طور ميانگيک ‪ n/2‬مقايسا مورا‬
‫نياز است‪.‬‬
‫‪70‬‬

71.

‫ار تحليل و بحث ارباره بلوک بناا رکورا ينا ييز را بايا مورا توجا قرار ااا ‪:‬‬
‫‪ )۱‬اريا بلوک بناا مي توانا منجر با بهبوا يشمگير کارايي‬
‫شوا ‪،‬مرتبا لملررا جستجوا ترتيبي را تنيير نمي ااا‪.‬‬
‫‪ )۲‬بلوک سارا ‪،‬اختالف مياک سرلت استيابي ار حافظا و زماک‬
‫استيابي ار حافظا نانويا را نشاک مي ااا‪.‬‬
‫‪ )۳‬بلوک سازا تعااا مقايسا اايي را کا بايا ار حافظا انجاا‬
‫شونا ‪،‬تنيير نمي ااا و احتمابً مقاار اااه ااا انتقال يافتا مياک‬
‫حافظا و ايسک را افزاي مي ااا‪.‬‬
‫‪ )۴‬با بلوک سازا ‪،‬ار زماک صرفا جويي مي شوا زيرا مقاار‬
‫جستجو کاا مي يابا‪.‬‬
‫‪71‬‬

72.

‫جستجوا ترتيبي براا اکنر شرايط بازيابي زماک بسيار مي برا‪.‬‬
‫ايک کا آيا جستجوا ترتيبي توصيا مي شوا يا خير تا حا‬
‫زيااا با يگونگي استمااه از فايل ‪،‬سرلت سيستا لامل ار‬
‫انجاا جستجو ‪،‬و يگونگي ساختار فايل بستگي اارا‪.‬‬
‫‪72‬‬

73.

‫متااول تريک ساختار فايل کا ار يونيرا وجوا اارا ‪،‬‬
‫يک فايل اسري با کاراکتر خط جايا با لنواک فاصل‬
‫رکورااا و ار صورت امراک ‪،‬ف اا خالي با لنواک فاصل‬
‫فيلااا است‪.‬‬
‫‪73‬‬

74.

‫رو ايگرا کا با جستجوا ترتيبي تماوت بنيااا اارا ‪،‬‬
‫استيابي مستقيا است‪.‬‬
‫انگامي کا بتوانيا مستقيما ً با ابتااا يک رکورا برويا و‬
‫آک را با حافظا وارا کنيا ‪،‬با آک رکورا استيابي مستقيا‬
‫ااريا‪.‬‬
‫‪74‬‬

75.

‫• ادامه مبحث مديريت فايلهايي از رکوردها‬
‫‪75‬‬

76.

‫غالبا ً بزا است از برخي اطاللات لمومي مربوط با فايل‬
‫آااه باشيا تا ار آيناه با استمااه از فايل کمک شوا ‪ ،‬رکورا‬
‫سرآينا غالبا ً ار آغاز فايل قرار اااه مي شوا تا ايک نود‬
‫اطاللات را نگهاارا کنا‪.‬‬
‫‪76‬‬

77.

‫ار فايل ااراا يک رکورا سرآينا (‪ )header‬است کا حاوا‬
‫سا مقاار ار تاييک است ‪:‬‬
‫‪ )۱‬اناازه سرآينا‬
‫‪ )۲‬تعااا رکورااا‬
‫‪ )۳‬اناازه ار رکورا‬
‫‪77‬‬

78.

‫او ساختار مختلف از رکورااا کا حاوا فيلاااا طول متنير ار يک‬
‫رکورا با طول نابت است ‪:‬‬
‫‪ )۱‬فايل حاوا سرآينا ‪ ۳۲‬بيتي و او رکورا طول نابت است‬
‫کا شامل فيلاااا طول متنيرا است کا با ‪ NULL‬ختا مي‬
‫شونا‪.‬‬
‫‪ )۲‬فايل حاوا سرآينا ‪ ۶۶‬بيتي و رکورااايي با طول ‪۶۸‬‬
‫بايت است کا با فيلاا او بايتي شرود مي شونا‪.‬‬
‫‪78‬‬

79.

‫يک طراحي شيتاراا خوب ‪،‬براا مانااار شاک اشيات‬
‫بايا لملياتي براا خواناک و نوشتک مستقيا اشيات فرااا‬
‫آورا‪.‬‬
‫‪79‬‬

80.

‫تا کنوک لمل نوشتک نيازمنا با او لمل جاااانا بوا ‪:‬‬
‫‪ )۱‬فشراه سازا ار يک بافر‬
‫‪80‬‬
‫‪ )۲‬نوشتک بافر روا فايل‬

81.

‫ار ايک بخ ‪،‬کالا ‪ recordfile‬را معرفي مي کنيا‬
‫کا نولي لمل خواناک را تشتيباني مي کنا کا شيئي از‬
‫يک کالا را ارفتا‪ ،‬آک را ار يک فايل مي نويسا‪.‬‬
‫کاربرا بافراا ار ااخل کالا تنهاک مي شوا‪.‬‬
‫‪81‬‬

82.

‫ار بحث اايي کا طي ايک فصل و فصل قبل ااشتيا با موارا زير‬
‫ترااختيا ‪:‬‬
‫‪)۱‬رکوراااا طول متنير‬
‫‪ )۲‬رکوراااا طول نابت‬
‫‪ )۳‬استيابي ترتيبي‬
‫‪ )۴‬استيابي مستقيا‬
‫او مورا اول با سازمانااي فايل و او مورا آخر با‬
‫استيابي با فايل مربوط مي شوا‪.‬‬
‫‪82‬‬

83.

‫اااه اايي منل صوت ‪،‬تصاوير ‪،‬و اسناا با صورت‬
‫فيلااا و رکورااا هخيره نمي شونا‪.‬‬
‫‪83‬‬

84.

‫اار ار زباک برناما نويسي امراک ااشتا باشا‪ ،‬مي توانيا‬
‫اطاللات کاربراا بيشترا ارباره ساختار فايل ار سرآينا قرار‬
‫اايا‪.‬‬
‫انگامي کا سرآينا فايل حاوا ايک نود اطاللات باشا‪ ،‬امتا‬
‫مي شوا ايک فايل ‪،‬خوا‪ -‬توصيمگر است‪.‬‬
‫‪84‬‬

85.

‫شبا اااه اا را مي تواک با ار فايلي امراه ساخت ‪،‬کا‬
‫اااه ااا اصلي آک نياز با اطاللات تشتيباک اارا‪.‬‬
‫‪85‬‬

86.

‫تصوير راستر رنگي ‪،‬آرايا اا راست اوشا از نقاط‬
‫رنگي يا تيرسل اا است ‪،‬کا روا صمحا با نماي ار‬
‫مي آينا‪.‬‬
‫‪86‬‬

87.

‫انواد متماوت فراواني از شبا اااه اا وجوا اارنا کا مي تواننا با‬
‫يک تصوير امراه شونا ‪،‬از جملا ‪:‬‬
‫‪ )۱‬تعااا بيت ااا با کار رفتا ار توصيف ارتيرسل‬
‫‪ )۲‬ابعاا تصوير‪ -‬تعااا تيرسل اا با ازاا ار سطر و تعااا‬
‫سطراا‬
‫‪ )۳‬يک جاول جستجوا رنگ يا جعبا رنگ (‪ )pallet‬کا‬
‫نشاک مي ااا کااا رنگ بايا با ار مقاار تيرسل ار تصوير‬
‫نسبت اااه شوا‪.‬‬
‫‪87‬‬

88.

‫متااايي براا کار با تصاوير با لنواک اشياا خاصي وجوا اارا ‪:‬‬
‫‪ )۱‬نماي‬
‫يک تصوير تنجره اا ار صمحا نماي‬
‫کنسول‬
‫‪ )۲‬امراه کراک يک تصوير با يک جاول جستجوا رنگ خاص‬
‫‪ )۳‬قرار اااک تصويرا بر روا يک تصوير ايگر و ايجاا يک‬
‫تصوير ترکيبي‬
‫‪ )۴‬با نماي‬
‫(‪)animation‬‬
‫‪88‬‬
‫ار آوراک تياتي ينا تصوير براا انيميشک‬

89.

‫اياه انبال کراک فايل اا براا قرار اااک اامنا وسيعي از‬
‫اشياا اونااوک ‪،‬اجتناب ناتهير است ‪،‬بويته براا‬
‫کاربرااايي کا نياز با مقاار زيااا از شبا اااه اا يا ترکيب‬
‫غير قابل تي بيني از انواد متماوت اااه اا اارنا ‪،‬زيرا با‬
‫ايک ترتيب ايگر بزا نيست رکورااا حتما ً از يک نود‬
‫باشنا‪.‬‬
‫‪89‬‬

90.

‫براا توصيف اياا کا يک برناما کاربراا از اشياا‬
‫اااه اا اارا ‪،‬از اصطالح مال ااا ااا انتزالي استمااه‬
‫نموايا‪.‬‬
‫ايک کار اساسا ً اياا کاربراارا و اروک‪ -‬حافظا اا از‬
‫اشيات است و ار آک از فرمت فيزيري اشيات با آک صورت‬
‫کا ار فايل اا نگهاارا مي شوا يشا توشي مي اراا‪.‬‬
‫‪90‬‬

91.

‫• ادامه مبحث مديريت فايلهايي از رکوردها‬
‫• سازماندهي فايلها براي کارايي‬
‫‪91‬‬

92.

‫يرااي از مزاياااا اسااتمااه از بريسااب اااا بااراا شناسااايي‬
‫اشااياا موجااوا ار فاياال اااا آک اساات کااا نيااازا نيساات کااا از‬
‫تي باانيا اما اشيايي کا نرا افزار با آنها سرو کار خوااا‬
‫ااشت با يا صورت خوااا بوا‪.‬‬
‫‪92‬‬

93.

‫اختالف مياک زباک اا ‪،‬سيستا ااا لامل ‪،‬و معمارا‬
‫ماشيک ‪،‬سا مشرل اصلي استنا کا انگاا توليا فايل ااا‬
‫قابل حمل با آک اا مواجهيا‪.‬‬
‫‪93‬‬

94.

‫ينا راه حل براا استيابي با قابليت حمل ‪:‬‬
‫‪ )۱‬توافق بر سر يک فرمت فيزيري استاناارا براا رکورا و‬
‫وفااارا با آک‬
‫‪ )۲‬توافق بر سر رمزاهارا اواويي استاناارا براا لناصر‬
‫اااه اا‬
‫‪ )۳‬تبايل الااا و متوک‬
‫‪ )۴‬تبايل ساختارااا فايل‬
‫‪94‬‬

95.

‫سازمانااي فايلها براا کارايي‬
‫‪95‬‬

96.

‫فشراه سازا يک فراينا استا اا (‪ )batch‬است‬
‫کا براا حهف حمره ااا خالي فايلي با کار مي روا‬
‫کا باراا و باراا مورا حهف و بهنگاا سازا قرار‬
‫ارفتا است‪.‬‬
‫‪96‬‬

97.

‫ابيل زيااا براا کويک کراک فايلها وجوا اارا ‪:‬‬
‫‪ )۱‬فايل ااا کويرتر نياز با حافظا ا کمترا اارنا‬
‫کا بالث صرفا جويي مي شوا‪.‬‬
‫‪ )۲‬سري تر انتقال اااه مي شونا کا زماک استرسي را‬
‫کوتااتر مي کنا يا با جاا آک مي تواک با اماک زماک‬
‫استرسي از تهناا بانا کمتر و ارزاک تر استمااه کرا‪.‬‬
‫‪ )۳‬با صورت ترتيبي ‪،‬سري تر قابل ترااز‬
‫‪97‬‬
‫استنا‪.‬‬

98.

‫فشراه سازا اااه اا لبارت است از رمزاهارا اطاللات‬
‫ار فايل ‪،‬با صورتي کا جاا کمترا بگيرا‪.‬‬
‫‪98‬‬

99.

‫ترنيک فشراه سازا کا ار آک تعااا بيت اا با استمااه‬
‫از يک نماااهارا فشراه تر کاا مي يابا يري از رو‬
‫ااا فشراه سازا است کا با لنواک کاا زوايا‬
‫شناختا مي شونا‪.‬‬
‫‪99‬‬

100.

‫آرايااا ااااا اسااتارا بااراا نااولي فشااراه سااازا بااا نااااا‬
‫رمزاهارا طول ران مناسب انا‪ .‬ابتاا مقاار خاصي را براا‬
‫شرود رمزاهارا طول اجرا ار يک بايات هخياره کاراه ساتا‬
‫الگوريتا آک را اجرا مي کنيا‪.‬‬
‫‪100‬‬

101.

‫الگوريتا آ رايا ااا استارا را با صورت زير اجرا مي کنيا ‪:‬‬
‫‪ )۱‬تيرسل ااا تشريل ااناه ا شرل را خواناه آنها با‬
‫ترتيب ار فايل هخيره کک‪.‬‬
‫‪ )۲‬جايي کا يک مقاار تيرسل بي از يک بار تشت سر اا‬
‫تررار شوا ايک سا بايت را با ترتيب جايگزيک کک ‪:‬‬
‫الف) نشاک ااناه کا طول اجرا‬
‫ب ) مقاار تيرسلي کا تررار شاه‬
‫ج ) تعااا افعاتي کا ايک مقاار تررار شاه است‪.‬‬
‫‪101‬‬

102.

‫نود ايگرا از فشراه سازا کاااا با طول متنير را بستا‬
‫با تعااا افعات ظاار شاک مقااير ‪ ،‬با آک مقااير نسبت مي‬
‫ااا‪ .‬با مقاايرا کا بيشتر تررار مي شونا کاااا‬
‫کوتااترا نسبت اااه مي شوا بنابر ايک جاا کمترا مي‬
‫ايرنا‪ .‬کاااا اافمک منالي از کاااا با طول متنير استنا‪.‬‬
‫‪102‬‬

103.

‫رااي ايگر براا صرفا جويي ف ا ار ياک فايال‪ ،‬بازياابي‬
‫ف ا ار آک فايل تا از تنيير يافتک فايل است‪.‬‬
‫‪103‬‬

104.

‫تنييرات فايل با سا شرل انجاا مي شوا ‪:‬‬
‫‪ )۱‬ا افا کراک رکورا‬
‫‪ )۲‬بهنگاا سازا رکورا‬
‫‪ )۳‬حهف رکورا‬
‫‪104‬‬

105.

‫متراکا کراک فايل از طريق تياا کراک مرااک ااايي ار فايال‬
‫کا حاوا ايچ اااه اا نيستنا و از بيک براک ايک مرااک اااا‬
‫خااالي فاياال اااا را کااويرتر مااي کنااا‪ .‬و مراااک ااااا خااالي اااا‬
‫وقتي ار فايل ايجاا مي شوا کا رکوراا را حهف مي کنيا‪.‬‬
‫‪105‬‬

106.

‫متراکا کاراک فايال آسااک تاريک و راياج تاريک رو‬
‫بازيابي ف ا است‪.‬‬
‫‪106‬‬
‫اااا‬

107.

‫با طور کلي براا فرااا کراک مرانيسمي براا حهف رکورااا و‬
‫با انبال آک استمااه اوباره از ف اا آزاا شاه بايا بتوانيا او‬
‫مسئلا را ت ميک کنيا ‪:‬‬
‫‪ )۱‬رکوراااا حهف شاه با طور خاصي لالمت اهارا‬
‫شونا‪.‬‬
‫‪ )۲‬بتوانيا محلي را کا توسط رکوراااا حهف شاه اشنال‬
‫شاه بوا تياا کنيا تا بتوانيا براا ا افا کراک رکوراااا‬
‫جايا از ايک محل اا استمااه کنيا‪.‬‬
‫‪107‬‬

108.

‫• ادامه مبحث سازماندهي فايلها براي‬
‫کارايي‬
‫• شاخص گذاري‬
‫‪108‬‬

109.

‫براا بازيابي سريعتر ف ا با وارا زير نيازمنايا ‪:‬‬
‫‪ )۱‬رااي کا بالفاصلا باانيا کا حمره ااا خالي ار فايل‬
‫وجوا اارا يا نا‬
‫‪ )۲‬رااي کا اار ينيک حمره اا وجوا اارا مستقيما ً با آک‬
‫تر کنيا‪.‬‬
‫‪109‬‬

110.

‫اساااتمااه از ليسااات اااااا تيونااااا باااراا تيوناااا اااک تمااااا‬
‫رکورااا ار او نياز فوق را برآوراه مي کنا‪.‬‬
‫‪110‬‬

111.

‫آساک تريک راه براا کار کراک با ليست استمااه از آک با‬
‫صورت تشتا است‪.‬‬
‫تشتا ليستي است کا ار آک ا افا و حهف اره اا از‬
‫يک انتهاا ليست انجاا مي شوا‪.‬‬
‫‪111‬‬

112.

‫براا بازيابي رکورااا از طريق ليست تيوناا با موارا زير نياز‬
‫ااريا ‪:‬‬
‫‪ )۱‬رااي براا تيونا اااک رکوراااا حهف شاه و تبايل‬
‫آنها با يک ليست‬
‫‪ )۲‬الگوريتمي براا ا افا کراک رکوراااا حهف شاه با‬
‫ليست‬
‫‪ )۳‬الگوريتمي براا تياا کراک و خارج کراک يک رکورا از‬
‫ليست انگامي کا مي خواايا از آک رکورا استمااه کنيا‪.‬‬
‫‪112‬‬

113.

‫براا مقابلا با تراکنااي خارجي يک رو‬
‫است و او راه ايگر با قرار زير است‪:‬‬
‫متراکا کراک فايل‬
‫‪ )۱‬اار او حمره رکورا ار ليست با صورت فيزيري کنار اا‬
‫قرار ايرنا آنها را با اا يري مي کنيا تا يک حمره رکورا‬
‫بزراتر ايجاا شوا‪ .‬با ايک کار ااغاا حمره اا ار فايل ميگوييا‪.‬‬
‫‪ )۲‬سعي مي کنيا تراکنااي را با حااقل برسانيا‪ .‬با ايک‬
‫ترتيب کا يک راابرا انتخاب جا را ار نظر مي ايريا کا‬
‫برناما با استمااه از آک يک حمره رکورا را از ليست انتخاب‬
‫کنا‪.‬‬
‫‪113‬‬

114.

‫انگامي کا نياز ااريا يک حمره رکورا را از ليست‬
‫خارج کنيا با شرود از ابتااا فايل لمل جستجو را انجاا‬
‫مي اايا تا رکوراا با اناازه کافي بزرگ تياا کنيا يا با‬
‫انتهاا ليست برسيا‪ .‬ايک راابرا انتخاب جا با لنواک‬
‫راابرا اوليک جاا مناسب( ‪ )first fit‬نامياه مي شوا‪.‬‬
‫‪114‬‬

115.

‫سا مشرل اساسي مربوط با مرتب سازا و جستجوا‬
‫اواويي لبارتنا از ‪:‬‬
‫‪ )۱‬جستجوا اواويي نياز با بي‬
‫استرسي با ايسک اارا‪.‬‬
‫از يک يا او‬
‫‪ )۲‬نگهاارا يک فايل با صورت مرتب شاه خيلي‬
‫اراک تماا مي شوا‪.‬‬
‫‪ )۳‬مرتب سازا ااخلي تنها ار مورا فايل ااا کويک‬
‫لملي است‪.‬‬
‫‪115‬‬

116.

‫مرتب سازا کلياا کا اااي با آک مرتب سازا با‬
‫بريسب مي اوينا بر ايک اياه استوار است کا وقتي‬
‫فايلي را ار حافظا مرتب مي کنيا تنها ييزيرا واقعا ً با‬
‫آک نياز ااريا کليا رکورااا است‪.‬‬
‫‪116‬‬

117.

‫ليب مرتب سازا کلياا ايک است کا مرتب کراک فايلي با‬
‫‪ n‬رکورا نياز با ‪ n‬استيابي تصاافي با فايل اصلي اارا‬
‫کا مي توانا بسيار بيشتر از خواناک ترتيبي اماک تعااا‬
‫رکورا وقت بگيرا‪.‬‬
‫‪117‬‬

118.

‫شاخص اهارا‬
‫‪118‬‬

119.

‫اما شاخص اا بر اساا يک ممهوا اصلي واحا‬
‫لمل مي کننا‪ :‬کليااا و آارا فيلااا‪.‬‬
‫‪119‬‬

120.

‫انواد شاخص اايي کا ار ايک فصل بررسي مي کنيا‬
‫شاخص سااه نامياه مي شونا زيرا با استمااه از آرايا‬
‫ااا سااه اا از ساختماک اا نشاک اااه مي شونا ‪،‬کا‬
‫حاوا کليااا و آارا فيلااا استنا‪.‬‬
‫‪120‬‬

121.

‫يوک شاخص اا با طاور غيار مساتقيا لمال ماي کنناا ‪،‬‬
‫باوک استرارا محتويات فايل ‪،‬باا فايال نظاا و ترتياب ماي‬
‫بخشنا‪.‬‬
‫‪121‬‬

122.

‫کاتالوگ کارتي ار واق مجمولا اا از سا شاخص‬
‫است کا ار کااا از يک فيلا کليا متماوت استمااه مي‬
‫کننا و اما انها از يک شماره کاتالوگ يرساک با‬
‫لنواک فيلا آارا بهره مي ايرنا‪.‬‬
‫‪122‬‬

123.

‫بنابرايک کاربرا ايگر شاخص بناا ايک است کا مي تواک‬
‫از طريق مسيرااا اونااوني با فايل است يافت‪.‬‬
‫‪123‬‬

124.

‫ار جستجوا اواويي بزا است امراک تر‬
‫فايل را ااشتا باشيا‪.‬‬
‫‪124‬‬
‫با وسط‬

125.

‫• ادامه مبحث شاخص گذاري‬
‫‪125‬‬

126.

‫راه ايگر براا مرتب سازا ‪ ،‬ايجاا شاخص براا فايل‬
‫است‪.‬‬
‫‪126‬‬

127.

‫ساختار شيت شاخص بسيار سااه است‪.‬‬
‫ايک ساختار ليستي است کا ار لنصر آک او فيلا اارا‪:‬‬
‫يک فيلا کليا و يک فيلا براا آفست بايت‪.‬‬
‫‪127‬‬

128.

‫لملياتي کا براا يافتک اااه ااا مورا نظر ‪،‬از طريق شاخص بزمنا لبارتنا از ‪:‬‬
‫‪ )۱‬ايجاا فايل اااه اا و شاخص خالي اوليا‬
‫‪ )۲‬باز کزاک فايل شاخص ار حافظا ‪،‬قبل از با کارايرا آک‬
‫‪ )۳‬نوشتک فايل شاخص بر روا ايسک ‪،‬تا از با کارايرا آک‬
‫‪ )۴‬افزواک رکورااايي با فايل و اااه اا‬
‫‪ )۵‬حهف رکورااا از فايل اااه اا‬
‫‪ )۶‬بهنگاا کراک رکورااا ار فايل اااه اا‬
‫‪ )۷‬بهنگاا کراک شاخص براا انعراا تنييرات با لمل آماه ار فايل اااه‬
‫اا‪.‬‬
‫‪128‬‬

129.

‫مزيت بزراي کا رو شيت ارا اارا آک است کا براا‬
‫اجراا ايک لمليات با اريا نياز ااشتا باشيا مي توانيا‬
‫ار متاااا کالا خوا بيابيا‪.‬‬
‫‪129‬‬

130.

‫ار ايجاا فايل اا بايا او فايل ايجاا شونا ‪:‬‬
‫‪ )۱‬فايل اااه اا براا نگهاارا اشياا اااه اا‬
‫‪ )۲‬فايل شاخص براا نگهاارا شاخص کليا اوليا‬
‫‪130‬‬

131.

‫بهنگاا سازا رکورااا با او صورت انجاا مي شوا ‪:‬‬
‫‪ )۱‬بهنگاا سازا ‪،‬تعااا فيلا و کليا را تنيير مي ااا‪.‬‬
‫‪ )۲‬بهنگاا سازا ‪،‬ار فيلا و کليا تأنير نمي اهارا‪.‬‬
‫‪131‬‬

132.

‫آشرارتريک بهينا سازا ‪،‬استمااه از جستجوا اواويي ار‬
‫متا ‪ find‬است کا توسط ‪:‬‬
‫‪ insert , search‬و ‪remove‬‬
‫مي شوا‪.‬‬
‫‪132‬‬
‫با کار ارفتا‬

133.

‫منب ايگر بهينا سازا ‪،‬ينانيا رکورا شاخص تنيير‬
‫نرراه باشا ‪ ،‬نوشتک ارباره رکورا شاخص ار فايل شاخص‬
‫است‪.‬‬
‫‪133‬‬

134.

‫استيابي با شاخص روا ايسک ااراا معايب زير است ‪:‬‬
‫‪ )۱‬جستجوا اواويي شاخص با جاا آنرا با سرلت‬
‫حافظا صورت تهيرا ‪،‬نياز با ينايک تيگرا اارا‪.‬‬
‫‪ )۲‬ترتيب مجاا شاخص کا از حهف يا افزواک رکورا‬
‫ناشي مي شوا نياز با جابا جا کراک يا مرتب سازا‬
‫رکورااا ار حافظا نانويا اارا کا ايک کار ميليونها بار‬
‫اراک تر از اجراا ايک لمليات ار حافظا است‪.‬‬
‫‪134‬‬

135.

‫ارااه يک شاخص سااه ار حافظا جا نشوا بايا از موارا زير‬
‫استمااه کرا ‪:‬‬
‫‪ )۱‬ار صورتي کا سرلت استيابي ار اولويت قرار ااشتا‬
‫باشا ‪،‬از سازمانااي ارامسازا استمااه شوا‪.‬‬
‫‪ )۲‬ار صورتي کا با ار او نود استيابي کلياا و ترتيبي‬
‫نياز ااشتا باشيا ‪،‬از يک شاخص ينا سطحي با ساختار‬
‫ارختي نظير ارخت ‪ B‬استمااه شوا‪.‬‬
‫‪135‬‬

136.

‫شاخص ااا سااه نسبت با استمااه از فايل اااه اا کا بر حسب کليا‬
‫مرتب شاه انا مزاياا يشمگيرا اارا ‪:‬‬
‫‪ )۱‬شاخص سااه استمااه از جستجوا اواويي را براا استيابي‬
‫کلياا با يک رکورا ار فايلي کا طول رکوراااا آک متنير است‬
‫امراک تهير مي سازا‪.‬‬
‫‪ )۲‬اار ورواا ااا شاخص بسيار کويرتر از رکوراااا فايل‬
‫اااه اا باشا ‪،‬مرتب سازا و نگهاارا شاخص نسبت با مرتب‬
‫سازا و نگهاارا فايل اااه اا زماک کمترا مي برا‪.‬‬
‫‪ )۳‬اار ار فايل اااه اا رکورااايي وجوا اارنا کا ار جاا خوا‬
‫مستقر استنا ‪،‬با استمااه از شاخص مي تواک ترتيب کليااا را‬
‫باوک جابجايي رکوراااا اااه اا لوض کرا‪.‬‬
‫‪136‬‬

137.

‫انگاميرا شاخص نانويا اا موجوا باشا ‪،‬افزواک يک‬
‫رکورا با فايل با معناا افزواک يک ورواا شاخص نانويا‬
‫است‪ .‬زماک بزا برا انجاا ايک کار بسيار مشابا زماک بزا‬
‫براا افزواک وروا يي با شاخص اوليا است‪.‬‬
‫‪137‬‬

138.

‫يک اختالف مها شاخص نانويا و شاخص اوليا آک‬
‫است کا شاخص نانويا مي توانا حاوا کلياااا اواانا‬
‫باشا‪.‬‬
‫‪138‬‬

139.

‫حهف يک رکورا معموبً با معناا حهف تمامي آارا‬
‫ااا آک رکورا ار سيستا فايل است‪.‬‬
‫بنابرايک حهف رکوراا از فايل اااه اا نا تنها با معناا‬
‫حهف ورواا مربوط ار شاخص اوليا بلرا با معناا حهف‬
‫اما ورواا ااا موجوا ار اما شاخص ااا نانويا اا‬
‫است کا با ايک ورواا از شاخص اوليا رجود مي کننا‪.‬‬
‫‪139‬‬

140.

‫مشرل ايک است کا شاخص ااا نانويا اماننا‬
‫شاخص اوليا با ترتيب کليااا نگهاارا مي شونا‪ .‬ار‬
‫نتيجا حهف يک ورواا شامل ترتيب مجاا ورواا ااا‬
‫موجوا ‪،‬با منظور بستک ف اا باقيماناه از حهف است‪.‬‬
‫‪140‬‬

141.

‫• ادامه مبحث شاخص گذاري‬
‫• پردازش کمک ترتيبي و مرتب سازي فايل هاي‬
‫بزرگ‬
‫‪141‬‬

142.

‫بهنگاا سا زا فايل اااه اا فقط انگامي شاخص نانويا را تحت‬
‫تأنير قرار مي ااا کا کليا اوليا يا نانويا تنيير يابنا‪ .‬کا سا‬
‫و عيت ممرک است تي بيايا ‪:‬‬
‫‪ )۱‬بهنگاا سازا بالث تنيير کليا نانويا مي شوا‪.‬‬
‫‪ )۲‬بهنگاا سازا بالث تنيير کليا اوليا مي شوا‪.‬‬
‫‪ )۳‬بهنگاا سازا محاوا با فيلاااا ايگر‬
‫‪142‬‬

143.

‫ساختارااا شاخص نانويا اا کا تا کنوک ارائا کرايا او مشرل‬
‫اارنا ‪:‬‬
‫‪ )۱‬اربارکا رکورا جاياا با فايل افزواه مي شوا ‪،‬بايا فايل‬
‫شاخص را اوباره مرتب کنيا ‪،‬حتي اار رکورا جايا با يک کليا‬
‫نانويا موجوا مربوط باشا‪.‬‬
‫‪ )۲‬اار کلياااا نانويا وجوا ااشتا باشا ‪،‬فيلا کليا نانويا براا‬
‫ار ورواا تررار مي شوا‪ .‬ايک کار بالث اار رفتک ف ا مي‬
‫شوا‪.‬‬
‫‪143‬‬

144.

‫ارسيستا فايلي کا طي ايک فصل طراحي کرايا ‪،‬‬
‫انقياا کلياااا اوليا با آارا ار زماک ايجاا شاک فايل‬
‫اا رخ مي ااا ولي کلياااا نانويا ار زماک استمااه‬
‫‪،‬با آارا خوا تيونا مي يابنا‪.‬‬
‫‪144‬‬

145.

‫ترااز‬
‫‪145‬‬
‫کمک ترتيبي و مرتب سازا فايل ااا بزرگ‬

146.

‫لمليات کمک ترتيبي شامل ترااز اماانگ او يا ينا‬
‫ليست ترتيبي براا ايجاا يک ليست خروجي است‪.‬‬
‫اااي ترااز منجر با ااغاا يا اتحاا اقالا موجوا ار‬
‫ليست ااا خروجي مي شوا ‪،‬اااي ااف ‪،‬تطابق يا‬
‫جايگهارا اقالا ار ليست اا است ‪،‬اااي نيز لمليات شامل‬
‫ترکيبي از تطابق و ااغاا مي شوا‪.‬‬
‫ايک نود لمليات روا ليست ااا ترتيبي ‪،‬مبناا‬
‫بسيارا از ترااز ااا فايل اا را تشريل مي اانا‪.‬‬
‫‪146‬‬

147.

‫اريا روال امخواني بسيار سااه با نظر مي رسا ‪،‬براا آک‬
‫کا ايک روال بهتر لمل کنا با ينا نرتا بايا توجا ااشت ‪:‬‬
‫‪ )۱‬آمااه سازا‬
‫‪ )۲‬استيابي با ل و بعاا ليست‬
‫‪ )۳‬امزماک سازا‬
‫‪ )۴‬کنترل شرايط تاياک فايل‬
‫‪ )۵‬تشخيص خطااا‬
‫‪147‬‬

148.

‫اار قرار باشا تعااا زيااا از ليست اا با اا ااغاا‬
‫شونا ‪،‬مي تواک با جاا حلقا مقايسا اا از ارخت‬
‫انتخاب استمااه کرا‪.‬‬
‫‪148‬‬

149.

‫مرتب سازا ار حافظا شامل سا مرحلا است ‪:‬‬
‫‪ )۱‬خواناک کل فايل از روا ايسک با حافظا‬
‫‪ )۲‬مرتب سازا رکورااا با استمااه از يک روال‬
‫مرتب سازا استاناارا ‪،‬منل مرتب سازا ‪shell‬‬
‫‪ )۳‬نوشتک اوباره فايل روا ايسک‬
‫‪149‬‬

150.

‫آيا يک الگوريتا مرتب سازا ااخلي وجوا اارا کا با‬
‫قار کافي سري باشا و بتوانا مرتب سازا الااا را‬
‫بالفاصلا تا از خواناه شاک آنها آغاز کنا و منتظر قرار‬
‫ارفتک کل فايل ار حافظا نشوا؟‬
‫بلا ‪،‬ناا آک مرتب سازا ارمي (‪ )heapsort‬است و‬
‫مبتني بر اماک اصل ارخت انتخاب است‪.‬‬
‫‪150‬‬

151.

‫ارا ارختي اواويي با ويتاي ااا زير است ‪:‬‬
‫‪ )۱‬ار اره ااراا کلياا است کا آک کليا بزاتر يا‬
‫مساوا کليا واق ار اره تار است‪.‬‬
‫‪ )۲‬يک ارخت اواويي کامل است‪.‬‬
‫‪ )۳‬با خاطر ويتايهاا ‪ ۱‬و ‪، ۲‬ار نگهاارا ارخت مي‬
‫تواک آرايا اا اختصاص ااا کا ار آک ‪،‬اره ريشا‬
‫‪،‬انايا ‪ ۱‬و انايسهاا فرزنااک يپ و راست اره ‪، i‬با‬
‫ترتيب برابر با‬
‫‪ ۲i‬و ‪ ۲i + ۱‬باشنا‪.‬‬
‫‪151‬‬

152.

152

153.

‫الگوريتا مرتب سازا ارمي او بخ‬
‫اارا‪:‬‬
‫ابتاا اارا را ايجااا ماي کنايا ساتا کلياااا را باا‬
‫صورت مرتب شاه ار خروجي قرار مي اايا‪.‬‬
‫‪153‬‬

154.

‫بازيابي ترتيبي کليااا با صورت زير انجاا مي شوا ‪:‬‬
‫‪ )۱‬تعييک مقاار کليا موجوا ار اوليک موقعيت ارا ‪ .‬ايک‬
‫مقاار کويرتريک مقاار ارا است‪.‬‬
‫‪ )۲‬انتقال بزراتريک مقاار ارا با اوليک محل آک و کا کراک‬
‫يک واحا از تعااا لناصر‪.‬‬
‫‪ )۳‬ترتيب اوباره ارا‪ .‬با اينرار بزراتريک لنصر با فرزنا‬
‫کوير جابجا مي شوا‪.‬‬
‫ار بار کا ايک سا مرحلا اجرا مي شوا ‪،‬کويرترا مقاار‬
‫بازيابي شاه از ارا حهف مي اراا‪.‬‬
‫‪154‬‬

155.

‫مرتب سازا کلياا او نارسايي اارا ‪:‬‬
‫‪ )۱‬انگاميرا کليااا مرتب سازيمي شونا ‪،‬بايا زماک زيااا‬
‫صرف ايک موارا شوا‪ .‬تيگرا ار رکورا ار رکوراااا مرتب‬
‫شاه ‪،‬خواناک ار رکورا با حافظا و نوشتک آک روا فايل‬
‫مرتب شاه جايا شوا‪.‬‬
‫‪ )۲‬ار مرتب سازا کلياا ‪،‬اناازه فايلي کا قابل مرتب‬
‫سازا است با تعااا جمت کليا‪/‬اشاره ارا کا ار حافظا جا‬
‫شوا ‪،‬محاوا مي شوا‪ .‬ار نتيجا انوز نمي توانيا فايل ااا‬
‫واقعا ً بزرگ را مرتب سازا کنيا‪.‬‬
‫‪155‬‬

156.

‫ران‬
‫ااراا ويتاي ااا زير است ‪:‬‬
‫‪ )۱‬واقعا ً قاار با مرتب سازا فايل ااا بزرگ است و با فايل‬
‫اايي با ار اناازه قابل بسط است‪.‬‬
‫‪ )۲‬خواناک فايل ورواا ار مرحلا ايجاا ران ‪،‬ترتيبي است و لها‬
‫بسيار سرلتر از ورواا است ‪،‬زيرا ورواا با ازاا ار رکورا نياز‬
‫با تيگرا اارا‪.‬‬
‫‪ )۳‬خواناک ار ران‬
‫شاه نيز ترتيبي است‪.‬‬
‫طي مرحلا ااغاا و نوشتک رکوراااا مرتب‬
‫‪ )۴‬اار براا بخشي از ااغاا کا ار حافظا انجاا مي شوا از مرتب‬
‫سازا ارمي استمااه شوا مي توانيا ايک لمليات را با ‪I/O‬‬
‫امتوشاني کنيا تا زماک ااغاا افزاي تياا نرنا‪.‬‬
‫‪ )۵‬يوک ‪ I/O‬تا حا زيااا ترتيبي است ‪،‬ار صورت نياز مي تواک‬
‫براا ار او لمليات ورواا و خروجي از نوار نيز استمااه کرا‪.‬‬
‫‪156‬‬

157.

‫‪ I/O‬يهار بار اجرا مي اراا‪.‬‬
‫ار مرحلا مرتب سازا ‪:‬‬
‫‪ )۱‬خواناک اما رکورااا با حافظا براا مرتب سازا و‬
‫تشريل ران اا‬
‫‪ )۲‬نوشتک ران ااا مرتب شاه روا ايسک‪.‬‬
‫ار مرحلا ااغاا ‪:‬‬
‫‪ )۱‬خواناک ران ااا مرتب شاه با حافظا براا ااغاا‬
‫‪ )۲‬نوشتک فايل مرتب شاه روا ايسک‬
‫‪157‬‬

158.

‫• ادامه مبحث پردازش کمک ترتيبي و مرتب‬
‫سازي فايل هاي بزرگ‬
‫‪158‬‬

159.

‫ياااک اخاااتالف لمااااه ميااااک مرحلاااا مرتاااب ساااازا و‬
‫مرحلاااا ااغااااا ‪،‬ار تعاااااا اساااتيابي ترتيباااي (ار مقابااال‬
‫استيابي مستقيا) است‪.‬‬
‫با استمااه از مرتب سازا ارمي براا ايجاا ران‬
‫اايي ار مرحلا مرتب ساازا ‪،‬ماي تاواک ت اميک نماوا‬
‫کا اما ‪ I/O‬اا از يک لحاظ ترتيبي است‪.‬‬
‫‪159‬‬

160.

‫با طور خالصا يوک مرحلا ااغاا تنهاا مرحلاا اا اسات‬
‫کا ار آک مي تواک بازااي را باا بهباوا بخشاياک باا رو‬
‫کار ‪،‬افزاي ااا بنابر ايک بر آک بيشتر تأکيا ااريا‪.‬‬
‫‪160‬‬

161.

‫با بزرگ شاک فايل اا زماک بزا براا مرتب سازا ااغامي با‬
‫سرلت افزاي مي يابا‪ .‬براا کاا ايک زماک ينا راه وجوا‬
‫اارا ‪:‬‬
‫‪ )۱‬تخصيص سخت افزار بيشتر نظير ايسک ارااک ‪،‬حافظا‬
‫و کانال ااا ‪I/O‬‬
‫‪ )۲‬اجراا ااغاا ار بي از يک مرحلا ‪،‬کاا‬
‫ار ااغاا و افزاي اااک اناازه بافر براا ار ران‬
‫‪ )۳‬افزاي‬
‫طول ران‬
‫ااا مرتب شاه از لحاظ الگوريتمي‬
‫‪ )۴‬يافتک رااهايي براا امتوشاني لمليات ‪I/O‬‬
‫‪161‬‬
‫اااک مرتبا‬

162.

‫ار ايک بخ سا تنيير ممرک ار تيرربناا سيستا‬
‫را ار نظر مي ايريا کا مي توانا زماک مرتب سازا‬
‫را با طور يشمگيرا کاا ااا ‪:‬‬
‫‪162‬‬
‫‪ )۱‬افزاي‬
‫مقاار حافظا‬
‫‪ )۲‬افزاي‬
‫تعااا ايسک ارااک اا‬
‫‪ )۳‬افزاي‬
‫تعااا کانال ااا ‪I/O‬‬

163.

163

164.

‫ااف اصلي ايک مرتب سازا ااغامي آک اسات کاا قااار‬
‫باشيا فايلهايي را مرتب سازا کنيا کا ار حافظا جا نمي‬
‫شونا‪.‬‬
‫‪164‬‬

165.

‫ار ااغاا ينا مرحلا اا‪ ،‬سعي نمي کنايا اماا رانا ااا‬
‫را بااا يرباااره ااغاااا کناايا‪ .‬بلرااا ران ا ااااا اوليااا را بااا‬
‫ارواهاا کويک تقسيا کراه ‪،‬ران ااا موجاوا ار اياک‬
‫اروه اا را جاااانا ااغاا مي کنيا‪.‬‬
‫‪165‬‬

166.

‫اساا انتخاب جايگزيني ‪،‬ايک اياه است ‪:‬‬
‫انتخاب اميشگي کلياا از حافظا کا ااراا کمتريک مقاار‬
‫باشا ‪،‬قرار اااک آک کليا ار خروجي ‪،‬و ستا تعويض آک با‬
‫يک کليا جايا از ليست ورواا‪.‬‬
‫‪166‬‬

167.

‫الگوريتا انتخاب جايگزيني را مي تواک با طريق زير تيااه سازا‬
‫نموا ‪:‬‬
‫‪ )۱‬خواناک مجمولا اا از رکورااا و مرتب سازا آنها با‬
‫استمااه از مرتب سازا ارمي‬
‫‪ )۲‬با جاا نوشتک کل ارا اوليا با شرل مرتب شاه فقط‬
‫رکوراا را مي نويسيا کا کليا آک ااراا کمتريک مقاار است‪.‬‬
‫‪167‬‬

168.

‫‪ )۳‬آوراک يک رکورا جايا و مقايسا مقاار کليا آک با مقاار‬
‫کلياا کا با تازاي ار خروجي قرار امتا است‪.‬‬
‫الف) اار مقاار کليا جايا بزراتر باشا رکورا جايا را ار‬
‫محل مناسب آک ار ارا اوليا ‪،‬با امراه رکورااايي قرار مي اايا کا‬
‫از خروجي ازين مي شونا‪.‬‬
‫ب) اار مقاار کليا رکورا جايا کمتر باشا ‪،‬رکورا را ار يک‬
‫ارا نانويا از رکورااا با مقااير کلياا کمتر از آنهايي کا تي از‬
‫ايک نوشتا شاه انا قرار مي اايا‪.‬‬
‫‪ )۴‬تا انگاميرا رکوراا ار ارا اوليا باقي باشا و رکورااايي‬
‫براا خواناک وجوا ااشتا باشا مرحلا ‪ ۳‬را تررار مي کنيا‪.‬‬
‫‪168‬‬

169.

‫ازين جايگزيني ابزارا ساوامنا باراا فايال اااا ورواا‬
‫اساات کااا قااارا مرتااب اسااتنا و ايااک ااازين فرصااتي بااراا‬
‫صرفا جويي ار زمانهاا انتقاال و تيگارا فارااا ماي آورا کاا‬
‫روشهاا مرتب سازا حافظا اا فاقا آک است‪.‬‬
‫‪169‬‬

170.

‫ار ازين جايگزيني اار او ايسک ار اختيار ااشتا‬
‫باشيا ‪،‬بايا حافظا را نيز طورا تيرربناا کنيا کا از آنها‬
‫بهره براارا شوا‪ .‬حافظا را ينيک تيرربناا مي کنيا ‪:‬‬
‫يک بافر ورواا و يک بافر خروجي اختصاص مي اايا‬
‫تا بافرااي اواانا امراک تهير اراا و بقيا حافظا را با‬
‫تشريل ارخت انتخاب اختصاص اايا‪.‬‬
‫‪170‬‬

171.

‫اختصاص اااک بي‬
‫امراک تهير است ‪:‬‬
‫از يک تراازناه با يک کار امرا است متااول کا با حابت زير‬
‫‪ )۱‬کامتيوترااا بزرگ کا بسيارا از آنها مقاار زيااا از وقت خوا را صرف‬
‫مرتب سازا مي کننا ‪،‬معموبً ااراا او يا ينا تراازناه استنا کا امزماک روا‬
‫بخ ااا متماوت يک مسئلا کار مي کننا‪.‬‬
‫‪ )۲‬تراازناه ااا براارا و آرايا اا را مي تواک طورا برناما ريزا کرا کا‬
‫انواد اونااوک الگوريتا مرتب سازا را سريعتر از تراازناه ااا اسرالر اجرا کنا‪.‬‬
‫‪ )۳‬ماشيک ااا موازا انبوه ‪،‬ازاراک و شايا ميليونها تراازناه اارنا کا مي‬
‫تواننا مستقل از اا کار کننا و ار ليک حال با شيوه ااا تييياه با اا ارتباط‬
‫برقرار کننا‪.‬‬
‫‪ )۴‬شبرا ااا محلي بسيار سري و نرا افزارااا ارتباطي ‪،‬ارسال بخ‬
‫متماوتي از يک فراينا با ينا ماشيک متماوت را امراک تهير مي سازا‪.‬‬
‫‪171‬‬
‫ااا‬

172.

‫اار ار سيستمي برناما نويسي ينااانا امراک‬
‫تهير باشا زماک کل براا ‪ I/O‬ممرک است طوبني تر‬
‫باشا ‪،‬زيرا کارما بايا منتظر بمانا تا کارااا ايگر‬
‫نيز ‪ I/O‬خوا را انجاا اانا‪.‬‬
‫‪172‬‬

173.

‫يري از ابيل برناما ريزا ينااانا آک است کا با‬
‫سيستا لامل امراک اايا تا رااهايي براا افزاي‬
‫بازااي کل سيستا ‪،‬با اا توشاني ترااز و ‪I/O‬‬
‫ار مياک امور متماوت بيابا‪.‬‬
‫‪173‬‬

174.

‫• ادامه مبحث پردازش کمک ترتيبي و مرتب‬
‫سازي فايل هاي بزرگ‬
‫• شاخص بندي چند سطحي و درختهاي ‪B‬‬
‫‪174‬‬

175.

‫ليست کاملي از مجمولا جايا ابزااايي کا کارايي مرتب سازا خارجي را بهبوا مي‬
‫بخشنا شامل موارا زيراست ‪:‬‬
‫‪ )۱‬براا مرتب سازا اروک حافظا اا ‪،‬از مرتب سازا ارمي براا تشريل‬
‫ليست اوليا لناصر مرتب شاه ار يک ران استمااه مي کنيا‪.‬‬
‫‪ )۲‬استمااه از حااکنر حافظا ممرک‬
‫‪ )۳‬اار تعااا ران ااا اوليا يناک بزرگ باشا کا زماک کل تيگرا و يرخ‬
‫‪،‬بسيار بزاتر از زماک انتقال کل باشا از ااغاا ينامرحلا اا استمااه مي کنيا‪.‬‬
‫‪ )۴‬استمااه از ازين‬
‫بگيريا‪.‬‬
‫‪ )۵‬از بي‬
‫جايگزيني براا تشريل ران‬
‫ااا اوليا را ار نظر‬
‫از يک ايسک ارااک و کانال ‪ I/O‬استمااه مي کنيا‪.‬‬
‫‪ )۶‬لناصر بنيااا مرتب سازا خارجي و ازينا ااا نسبي آنها را با خاطر مي‬
‫ستاريا و با انبال راه اايي براا بهره براک از معمارا اا و سيستمهاا جايا‬
‫‪،‬نظير ترااز موازا مي ارايا‪.‬‬
‫‪175‬‬

176.

‫ارااغاا موازنا شاه اوجانبا ‪،‬توزي اوليا بايا روا او‬
‫نوارارااک صورت تهيرا و ار ار مرحلا از ااغاا ‪،‬با جز‬
‫آخرا خروجي بايا روا او نوارارااک صورت ايرا‪.‬‬
‫ايک ااغاا سااه تريک الگوريتا ااغاا نوارا است‪.‬‬
‫‪176‬‬

177.

‫اياه ااا استمااه از الگوريتا ااا ااغاا مرتبا بابتر و ااغاا‬
‫ران اا از روا يک نوار ار ينا مرحلا مبناا او رو معروف‬
‫براا ااغاا ‪،‬موسوا با ااغاا ينا مرحلا اا يا ااغاا آبشارا‬
‫است‪.‬‬
‫با طور کلي ايک ااغاا اا ار ويتاي ااا زير با اا مشترکنا ‪:‬‬
‫‪ )۱‬توزي اوليا ران اا يناک است حااقل ااغاا اوليا يک ااغاا‬
‫‪ j -1‬جانبا است کا ار آک ‪ j‬تعااا نوارارااک اا است‪.‬‬
‫‪ )۲‬توزي ران اا ار مياک نواراا يناک است کا نواراا غالبا ً‬
‫حاوا تعااا متماوتي از ران اا استنا‪.‬‬
‫‪177‬‬

178.

‫يوک ايسک اا استگااهاا استيابي مستقيا استنا‬
‫ااغاا ااا با مرتبا بسيار بزرگ را مي تواک انجاا ااا‬
‫‪،‬حتي اار فقط يک ايسک ارااک وجوا ااشتا باشا‪.‬‬
‫يوک نواراا استگاه ااا استيابي مستقيا نيستنا براا‬
‫ار ران ا افي کا بخواايا ااغاا کنيا با يک نوارارااک‬
‫ا افي نياز ااريا‪.‬‬
‫بنابر ايک ايسک اا بهترنا‪.‬‬
‫‪178‬‬

179.

‫شاخص بناا ينا سطحي و ارختهاا ‪B‬‬
‫‪179‬‬

180.

‫مشرل اصلي نگهااشتک شاخص ار حافظا جانبي ايک‬
‫است کا استيابي با حافظا جانبي کنا است‪.‬‬
‫ايک مشرل مي توانا با او مشرل ويته تقسيا شوا ‪:‬‬
‫‪ )۱‬جستجو بر حسب شاخص بايا سريعتر از جستجوا‬
‫اواويي باشا‪.‬‬
‫‪ )۲‬ارج وحهف بايا با سرلت جستجو کراک انجاا شوا‪.‬‬
‫‪180‬‬

181.

‫ارخت جستجوا اواويي يا اشرالي اارا؟‬
‫‪ )۱‬براا شاخص بناا روا ايسک سرلت بزا را‬
‫ناارا‪.‬‬
‫‪ )۲‬يک راابرا مؤنر براا موازنا کراک ارخت وجوا‬
‫ناارا‪.‬‬
‫‪181‬‬

182.

‫تالشهايي براا حل مشرالت ارخت جستجوا اواويي‬
‫انجاا ارفت کا او تا از آنها لبارتنا از ‪:‬‬
‫‪ )۱‬ارخت ااا ‪AVL‬‬
‫‪ )۲‬ارخت ااا اواويي صمحا صمحا‬
‫‪182‬‬

183.

‫ارخت ‪ AVL‬ارختي با ارتماد موازنا شاه است‪.‬‬
‫يعني اينرا ‪،‬اختالف مجاز مياک ار او زيرارخت‬
‫کا ريشا مشترکي اارنا محاوايت اارا و حااکنر‬
‫تماوت مجاز ‪ ۱‬است‪.‬‬
‫‪183‬‬

184.

184

185.

‫او مزيت کا ارخت ااا ‪ AVL‬را با ااميت مي کننا لبارتنا از ‪:‬‬
‫‪ )۱‬با تعييک کراک حااکنر تماوت مجاز ار ارتماد ار او‬
‫زيرارخت ‪،‬ارخت ااا ‪ AVL‬حااقل کارايي را ار جستجو‬
‫ت ميک مي کننا‪.‬‬
‫‪ )۲‬براا اينرا انگاا ارج ار ارخت ‪، AVL‬ويتاي خوا را‬
‫حمظ کنا ‪،‬مستلزا يهار نود يرخ است‪.‬‬
‫‪185‬‬

186.

‫ارخت اواويي صمحا اا ‪،‬سعي مي کنا با قرار اااک‬
‫ينايک اره اواويي ار يک صمحا ايسک ‪،‬مشرل را حل‬
‫کنا‪.‬‬
‫‪186‬‬

187.

187

188.

‫وا ح است کا تقسيا کراک ارخت با ينايک صمحا‬
‫امراک جستجوا سريعتر ار حافظا جانبي را فرااا مي‬
‫کنا وبا است آوراک اطاللات را سريعتر از ار رو‬
‫ايگر استيابي با استمااه از کليا امراک تهير مي کنا‪.‬‬
‫‪188‬‬

189.

‫مشرل اصلي ارخت ااا صمحا اا انوز اا استمااه‬
‫از ايسک است‪.‬‬
‫‪189‬‬

190.

‫ارخت ااا ‪ B‬شاخص ااا ينا سطحي استناکا‬
‫مشرل ازينا خطي ارج و حهف کراک را حل مي کننا‪.‬‬
‫ايک ويتاي بالث جهابيت ارخت ‪ B‬مي شوا ‪،‬زيرا‬
‫اکنوک ارخت ااا ‪ B‬رو استاناارا شاخص سازا‬
‫استنا و از تاييک با باب ساختا مي شونا و لملياتي نظي‬
‫ارج و حهف ‪،‬ار حافظا روا اره ااا ارخت ‪ B‬المال‬
‫مي شوا‪.‬‬
‫‪190‬‬

191.

‫• ادامه مبحث شاخص بندي چند سطحي و درختهاي ‪B‬‬
‫‪191‬‬

192.

‫جستجو ار ارخت ‪: B‬‬
‫‪ )۱‬با صورت تررارا لمل مي کننا‪.‬‬
‫‪ )۲‬ار او مرحلا لمل مي کننا ‪:‬‬
‫الف) با صورت يک ارمياک روا کل صمحات‬
‫ب) ار ااخل صمحات‬
‫‪192‬‬

193.

‫ار مورا فراينا ارج کراک ‪،‬تقسيا کراک و ارتقات مالحظات‬
‫زير را ار نظر مي ايريا ‪:‬‬
‫‪ )۱‬با جستجويي کا تا سطح برگ تي‬
‫مي شوا‪.‬‬
‫مي روا شرود‬
‫‪ )۲‬بعا از تياا کراک محل ارج ار سطح برگ ‪،‬کار ارج‬
‫‪،‬تشخيص سر ريز و تقسيا کراک از تاييک با سمت باب‬
‫تي مي روا‪.‬‬
‫‪193‬‬

194.

‫از مرتبا ارخت ‪ B‬با لنواک حااقل تعااا کليااايي‬
‫کا مي توانا ار يک صمحا ارخت وجوا ااشتا باشا‬
‫تعريف مي شوا‪.‬‬
‫‪194‬‬

195.

‫تاييک تريک سطح کليااا ار ارخت ‪ B‬را برگ مي نامنا‪.‬‬
‫‪195‬‬

196.

‫با استمااه از تعاريف ارائا شاه از مرتبا و برگ ‪،‬مي توانيا خواص‬
‫يک ارخت ‪ B‬از مرتبا ‪ m‬را اقيقا ً بياک کنيا ‪:‬‬
‫‪ )۱‬ار صمحا حا اکنر ‪ m‬فرزنا اارا‪.‬‬
‫‪m‬‬
‫‪ )۲‬ار صمحا ‪،‬با جز ريشا و برگ اا ‪،‬حااقل] ‪ [ 2‬فرزنا‬
‫اارا‪.‬‬
‫‪ )۳‬ريشا حااقل او فرزنا اارا‪.‬‬
‫‪ )۴‬تماا برگ اا ار يک سطح قرار اارا‪.‬‬
‫‪ )۵‬سطح برگ اا ‪،‬يک شاخص کامل و مرتب شاه از فايل‬
‫اااه ااا مربوط با ارخت را ايجاا مي کنا‪.‬‬
‫‪196‬‬

197.

‫ت ميک ايک کا ارخت تهک و کا لمق باشا ‪،‬نا باريک و‬
‫لميق ‪،‬مربوط با ايک قوانيک است ‪:‬‬
‫‪m‬‬
‫[‬
‫‪ )۱‬ار صمحا با جز ريشا و برگ اا حااقل ]‬
‫‪2‬‬
‫فرزنا اارا‪.‬‬
‫‪ )۲‬ار صمحا حاوا حااقل]‬
‫است‪.‬‬
‫‪197‬‬
‫‪m‬‬
‫‪[2‬‬
‫و حاااکنر ‪ m‬کلياا‬

198.

‫قوانيک حهف کليا ‪ k‬از اره ‪ n‬ار يک ارخت ‪ B‬با ايک ترتيبنا ‪:‬‬
‫‪ )۱‬اار تعااا کلياااا ‪ n‬بيشتر از حا اقل کلياااا مجاز است و ‪ k‬بزراتريک کليا‬
‫ار ‪ n‬نيست ‪،‬کافي است ‪ k‬را از ‪ n‬حهف کنيا‪.‬‬
‫‪ )۲‬اار تعااا کلياااا ‪ n‬بيشتر از حا اقل کلياااا مجاز است و ‪ k‬بزراتريک کليا‬
‫ار ‪ n‬است ‪ k،‬را حهف کنيا و شاخص ااا سطح بابتر را متناسب با بزراتريک‬
‫کليا جايا ار ‪ n‬تنيير اايا‪.‬‬
‫‪ )۳‬اار تعااا کلياااا ‪ n‬اقيقا ً برابر حااقل کلياااا مجاز است و يري از‬
‫براارااا ‪ n‬با اناازه کافي خالي است ‪ n‬را ار برابر ااغاا کنيا و يک کليا را‬
‫از اره ماار حهف کنيا‪.‬‬
‫‪ )۴‬اار تعااا کلياااا ‪ n‬اقيقا ً برابر حااقل کلياااا مجاز است و يري از‬
‫براارااا ‪ n‬کلياااا زيااا اارا ‪،‬با انتقال اااک بع ي از کليااا از يک براار با‬
‫‪، n‬کليااا را اوباره توزي کنيا و شاخص ااا سطح بابتر را متناسب با‬
‫بزراتريک کلياااا جايا اره ااا استرارا شاه تنيير اايا‪.‬‬
‫‪198‬‬

199.

‫توزي اوباره ار انگاا ارج ‪،‬رااي براا جلوايرا يا‬
‫حااقل با تعويق انااختک ايجاا صمحات جايا است‪.‬‬
‫‪199‬‬

200.

‫با جاا تقسيا کراک يک صمحا تر و ايجاا او صمحا‬
‫نيما تر‪ ،‬توزي اوباره ايک امراک را با ما مي ااا کا‬
‫تعاااا از کلياااا سرريز شاه را با صمحا ايگرا انتقال‬
‫اايا‪.‬‬
‫بنابرايک استمااه از توزي اوباره با جاا تقسيا کراک‬
‫بالث مي شوا کا ارخت ‪ B‬از ف اا حافظا جانبي با طور‬
‫مؤنرتر استمااه کنا‪.‬‬
‫‪200‬‬

201.

‫يک نود جايا از ارخت ‪ B‬را با لنواک ارخت *‪ B‬تعريف‬
‫مي کنيا کا خواص آک با ايک ترتيب است ‪:‬‬
‫‪ )۱‬ار صمحا حااکنر ‪ m‬فرزنا اارا‪.‬‬
‫‪2m 1‬‬
‫‪ )۲‬ار صمحا با جزريشا حااقل ] ‪ [ 3‬فرزنا اارا‪.‬‬
‫‪ )۳‬ريشا حااقل او فرزنا اارا‪.‬‬
‫‪ )۴‬تماا برگ اا ار يک سطح قرار اارنا‪.‬‬
‫‪201‬‬

202.

‫فراينا استيابي با ايسک براا خواناک صمحا اا کا ار‬
‫بافر وجوا ناارا‪ ،‬نقص صمحا اا (‪ )page fault‬نامياه‬
‫مي شوا‪.‬‬
‫‪202‬‬

203.

‫او للت براا نقص صمحا وجوا اارا ‪:‬‬
‫‪ )۱‬اييگاه تا کنوک از آک صمحا استمااه نرراه ايا‪.‬‬
‫‪ )۲‬آک صمحا قبالً ار بافر بواه است اما صمحا‬
‫جاياا جايگزيک آک شاه است‪.‬‬
‫‪203‬‬

204.

‫يک راه براا مورا اوا صمحا قبل ايک است کا‬
‫صمحا اا را کا زواتر از اما مورا استمااه قرار ارفتا‬
‫جايگزيني ‪LRU،‬‬
‫است جايگزيک کنيا ‪،‬ايک رو‬
‫(‪ )List Recently Used‬نامياه مي شوا‪.‬‬
‫‪204‬‬

205.

‫استمااه از رکوراااا با طول متنير بالث صرفا جويي‬
‫ار ف ا و ار نتيجا کاا ارتماد ارخت ‪ B‬مي شوا‪.‬‬
‫‪205‬‬

206.

‫• دستيابي به فايلهاي ترتيبي شاخصدار و درختهاي ‪B+‬‬
‫‪206‬‬

207.

‫دستيابي به فايل هاي ترتيبي شاخص دار و درخت هاي ‪B ‬‬
‫‪207‬‬

208.

‫ساختارااا فايل ترتيبي انايا اار ‪،‬امراک انتخاب از مياک‬
‫او اياااه متماوت نسبت با فايل را فرااا مي آورنا ‪:‬‬
‫‪ )۱‬شاخص اار ‪ :‬فايل را مي تواک با لنواک مجمولا‬
‫اا از کليااا ار نظر ارفت کا توسط کليا ‪،‬شاخص بناا‬
‫شاه انا‪.‬‬
‫‪ )۲‬ترتيبي ‪ :‬با فايل مي تواک استيابي ترتيبي ااشت و‬
‫رکورااا را با ترتيب توسط کليا بازاراانا‪.‬‬
‫‪208‬‬

209.

‫مجمولا اا از رکورااا کا با طور فيزيري توسط‬
‫کليااا مرتب شاه انا و رکورااايي با آک ا افا و يا‬
‫از آک حهف مي شونا‪ .‬ينيک مجمولا اا از رکورااا‬
‫را مجمولا ترتيبي مي ناميا‪.‬‬
‫‪209‬‬

210.

‫انگاميرا رکورااا را بلوک بناا مي کنيا ‪ ،‬بلوک واحا‬
‫اصلي ورواا و خروجي مي شوا‪.‬‬
‫‪210‬‬

211.

‫اماننا ارخت ااا ‪، B‬ارج رکوراااا جايا ار يک‬
‫بلوک مي توانا بالث سرريز شاک بلوک شوا‪.‬‬
‫‪211‬‬

212.

‫مشرل سرريز شاک را مي تواک توسط يک فراينا‬
‫شرستک بلوک اا کنترل کرا کا شبيا فراينا شرستک بلوک‬
‫اا ار ارخت ااا ‪ B‬است ‪،‬ولي نا اقيقا ً اماک فراينا‪.‬‬
‫‪212‬‬

213.

‫تا ريز شاک ار ارخت ‪ B‬مي توانا منجر با يري از او راه‬
‫حل زير شوا ‪:‬‬
‫‪ )۱‬اار يک اره مجاور نيز نيما تر باشا ‪،‬مي تواک او اره‬
‫را ار اا ااغاا کرا و يري از آنها را براا استمااه اوباره‬
‫آزاا ساخت‪.‬‬
‫‪ )۲‬اار اره ااا مجاور بي از نيما تر باشنا ‪،‬مي تواک‬
‫رکورااا را اوباره مياک اره اا توزي کرا تا توزي تقريبا ً‬
‫متعاال اراا‪.‬‬
‫‪213‬‬

214.

‫مسئلا اناازه بلوک با تعييک حاوا (‪ )limits‬اناازه‬
‫بلوک تبايل مي شوا‪.‬‬
‫‪214‬‬

215.

‫او شرطي کا ار رابطا با حا بابيي اناازه بلوک ار نظر مي‬
‫ايريا لبارت است از ‪:‬‬
‫‪ )۱‬اناازه بلوک بايا يناک باشا کا بتوانيا ينايک رکورا‬
‫را با يرباره ار حافظا نگا ااريا‪.‬‬
‫‪ )۲‬خواناک يا نوشتک يک بلوک نبايا زماک زيااا را‬
‫صرف کنا‪.‬‬
‫‪215‬‬

216.

‫ساااختار مخااتلط يااک شاااخص ‪ B‬بعااالوه يااک مجمول اا‬
‫‪ ‬‬
‫ترتيبااااي کااااا رکورااااااا را نگااااا مااااي اارا ارخاااات ‪ B‬را‬
‫تشريل مي ااا‪.‬‬
‫‪216‬‬

217.

‫ااف از ساختک شاخص آک است کا انگاا جستجوا‬
‫رکوراا با يک کليا مشخص ‪،‬با ما کمک نمايا‪.‬‬
‫شاخص بايا ما را با بلوکي از مجمولا ترتيبي ااايت‬
‫کنا کا حاوا ايک رکورا است‪.‬‬
‫شاخص با لنواک نقشا راانمايي براا مجمولا ترتيبي‬
‫لمل مي کنا‪.‬‬
‫‪217‬‬

218.

‫محتويات شاخص فقط تا آک حا مورا لالقا ما استنا کا‬
‫بتواننا ما را ار رسياک با بلوک ارست ار مجمولا‬
‫ترتيبي رانموک باشنا‪.‬‬
‫‪218‬‬

219.

‫با ار نظر ارفتک مجمولا شاخص با لنواک يک نقشا‬
‫راانما مي توانيا ايک ااا بسيار مها را برااريا کا ‪:‬‬
‫بزا نيست کليااا ار شاخص نگهاارا شونا‪ .‬آنيا کا‬
‫واقعا ً نياز ااريا ‪،‬جااکنناه اا استنا‪.‬‬
‫‪219‬‬

220.

‫شاخص ارخت ‪ B‬را مجمولا شاخص مي نامنا‪.‬‬
‫ايک شاخص با امراه مجمولا ترتيبي ‪،‬ساختار فايلي‬
‫‪ ‬‬
‫‪B‬‬
‫تيشوناا سااه ناا اارا‪.‬‬
‫را تشريل مي ااا کا ارخت‬
‫‪220‬‬

221.

‫لبارت تيشوناا سااه (‪ )simple prefix‬نشانگر آک‬
‫است کا مجمولا شاخص حاوا کوتااتريک جااکنناه اا يا‬
‫تيشوناااا کليااا است نا يک کتي از روا خوا کلياااا‬
‫واقعي‪.‬‬
‫‪221‬‬

222.

‫اار حهف رکورااا از مجمولا ترتيبي و ا افا کراک‬
‫رکورااا با آک ‪،‬تعااا رکورااا را ار مجمولا ترتيبي تنيير ااا‬
‫‪،‬يا تي مي آيا؟‬
‫وا ح است کا اار تعااا بلوک ااا بيشترا ااشتا باشيا‬
‫‪ ،‬با تعااا جااکنناه ااا کمترا نياز خواايا ااشت‪ .‬تنيير‬
‫اااک تعااا جااکنناه اا قطعا ً بر مجمولا شاخص تأنير‬
‫خوااا ااشت ‪ ،‬زيرا جااکنناه اا ار آنجا نگهاارا مي شونا‪.‬‬
‫‪222‬‬

223.

‫• ادامه مبحث دستيابي به فايل هاي ترتيبي‬
‫شاخص دار و درخت هاي ‪B+‬‬
‫• درهم سازي‬
‫‪223‬‬

224.

‫ارج و حهف رکورااا امواره ار مجمولا ترتيبي‬
‫رخ مي ااا ‪،‬زيرا رکورااا ار آنجا قرار اارنا‪.‬‬
‫‪224‬‬

225.

‫اار شرافتگي ‪،‬ااغاا يا توزي اوباره مورا نياز باشا ‪،‬‬
‫لمليات را ارست طورا انجاا مي اايا کا ار صورت نبوا‬
‫مجمولا شاخص انجاا مي ااايا‪.‬‬
‫‪225‬‬

226.

‫تا از کامل شاک لمليات مربوط با رکورا ار مجمولا ترتيبي‬
‫تنييرات مورا نياز ار مجمولا شاخص را المال کنيا ‪:‬‬
‫‪ )۱‬اار بلوک اا ار مجمولا ترتيبي شرافتا شونا ‪،‬يک خط‬
‫جااکنناه جايا بايا ار مجمولا شاخص ارج اراا‪.‬‬
‫‪ )۲‬اار بلوک اا ار مجمولا ترتيبي ااغاا شونا ‪،‬يک‬
‫جااکنناه بايا از مجمولا شاخص حهف ارانا‪.‬‬
‫‪ )۳‬اار رکورااا بيک بلوک اا ار مجمولا ترتيبي اوباره‬
‫توزي شونا ‪،‬مقاار يک جااکنناه ار مجمولا شاخص بايا‬
‫تنيير يابا‪.‬‬
‫‪226‬‬

227.

‫ينا اليل براا استمااه از ا ناازه بلوک مشترک مياک مجمولا ااا‬
‫ترتيبي و انايسي وجوا اارا ‪:‬‬
‫‪ )۱‬معموب از آک رو براا مجمولا شاخص از اناازه بلوک‬
‫مجمولا ترتيبي استمااه مي شوا کا تطابق خوبي مياک اناازه بلوک‬
‫‪،‬ويتايهاا ايسک ارااک ‪،‬ومقاار حافظا ار استرا وجوا اارا‪.‬‬
‫‪ )۲‬با اناازه بلوک مشترک تيااه سازا يک الگوا بافرااي براا‬
‫‪ ‬‬
‫‪B‬‬
‫تيشوناا سااه مجازا ‪،‬مشابا ارختهاا ‪ B‬مجازا‬
‫ايجاا ارخت‬
‫آساک تر مي اراا‪.‬‬
‫‪ )۳‬بلوک ااا مجمولا ترتيبي و بلوک ااا مجمولا شاخص‬
‫غالبا ً ار يک فايل قرار اااه مي شونا تا از جستجو مياک او فايل‬
‫جاااانا ار انگاا استيابي با ارخت ‪ B ‬تيشوناا سااه ترايز شوا‪.‬‬
‫‪227‬‬

228.

‫لالوه بر براار جااکنناه اا ‪،‬شاخص ايک جااکنناه اا و‬
‫ليست شماره ااا بلوک مربوط ‪،‬ساختار بلوک مجمولا‬
‫شاخص شامل موارا زير مي شوا ‪:‬‬
‫‪ )۱‬تعااا جااکنناه اا‬
‫‪ )۲‬طول کل جااکنناه اا‬
‫‪228‬‬

229.

‫فراينا باراهارا بسيار سري تي‬
‫مي روا زيرا ‪:‬‬
‫‪ )۱‬خروجي را مي تواک با طور ترتيبي نوشت‪.‬‬
‫‪ )۲‬بجاا ينايک بار اهر مربوط با لمليات ارج ‪،‬فقط يک‬
‫بار از اااه اا اهر مي کنيا‪.‬‬
‫‪ )۳‬با تيشرفت کار نيازا با سازمانااي اوباره بلوک اا‬
‫نيست‪.‬‬
‫‪229‬‬

230.

‫‪ ‬‬
‫‪ ‬‬
‫‪B‬‬
‫تماوت مياک ارخت ‪ B‬تيشوناا سااه و ارخت آک است‬
‫کا ‪ B ‬از تيشونااايي با لنواک جااکنناه استمااه نمي کنا‪.‬‬
‫ار لوض جااکنناه اا ار مجمولا انايا ‪،‬صرفا ً يک کتي‬
‫از کلياااا واقعي انا‪.‬‬
‫‪230‬‬

231.

‫‪ ‬‬
‫‪ ‬‬
‫ار او نود ارخت ‪ B‬تيشوناا سااه و ارخت ‪ ، B‬از‬
‫يک مجمولا رکورا تشريل مي شوا کا ار يک مجمولا‬
‫ترتيبي بر حسب کليا مرتب شاه اک و با يک مجمولا‬
‫انايا جمت شاه انا کا استيابي سري با بلوک حاوا‬
‫اراونا ترکيب رکوراا خاص را فرااا مي آورا‪ .‬تنها‬
‫‪ ‬‬
‫اختالف ار آک است کا ارخت ‪ B‬تيشوناا سااه اا کا‬
‫ساختا ايا ‪ ،‬با استمااه از تيشوناااا کليا مجمولا‬
‫انايسي از کوتااتريک جااکنناه اا ‪،‬تشريل مي شوا‪.‬‬
‫‪231‬‬

232.

‫ارخت‪B ‬‬
‫او لامل وجوا اارا کا ممرک است و عيت را با نم‬
‫کا ار آک ‪،‬کتي کاملي از کليااا با لنواک جاا کنناه برار ارفتا مي‬
‫شوا ‪،‬تنيير ااا ‪:‬‬
‫‪ )۱‬اليل استمااه از کوتااتريک جااکنناه اا ‪،‬فشراه سازا‬
‫اريا بيشتر آنها ار يک بلوک از مجمولا شاخص است‪.‬‬
‫‪ )۲‬برخي مجمولا ااا کلياا ‪،‬انگاا استمااه از رو‬
‫تيشوناا سااه براا ايجاا جااکنناه اا ‪،‬فشراه سازا ينااني‬
‫از خوا نشاک نمي اانا‪.‬‬
‫‪232‬‬

233.

‫ارخت ‪ ،B‬ارخت ‪ B ‬تيشوناا سااه و ارخت ‪ B ‬ار خصوصيات زير مشترکنا ‪:‬‬
‫‪ )۱‬امگي ساختارااا شاخص صمحا اا استنا ‪،‬يعني کل اطاللات موجوا ار‬
‫بلوک را يرباره با حافظا منتقل مي کننا‪.‬‬
‫‪ )۲‬ار ار سا رو‬
‫‪ ،‬ارختهايي نگهاارا مي شوا کا ارتماد آنها وازنا است‪.‬‬
‫‪ )۳‬ار اما موارا ‪،‬ارختها از تاييک با باب رشا مي کننا و موازنا از طريق‬
‫شرستک بلوک ‪،‬ااغاا و توزي اوباره حمظ مي شوا‪.‬‬
‫‪ )۴‬با ار سا ساختار مي تواک از طريق استمااه از شرافتگي او با سا و ار‬
‫صورت امراک ‪،‬توزي اوباره با جاا شرستک بلوک ‪،‬بازااي را باب برا‪.‬‬
‫‪ )۵‬ار سا رو را مي تواک با لنواک ساختارااا ارختي مجازا تيااه سازا‬
‫کرا کا ار آک ‪،‬آخريک بلوک ااا استمااه شاه ‪،‬ار حافظا نگهاارا مي شونا‪.‬‬
‫‪ )۶‬ار يک از ايک سا رو را مي تواک با استمااه از ساختارااا موجوا ار‬
‫بلوک با رکوراااا طول متنير با کار برا‪.‬‬
‫‪233‬‬

234.

‫‪ ‬‬
‫ساختار ارخت ‪ B‬سا مزيت مها ير ارخت ‪ B‬اارا‪:‬‬
‫‪ )۱‬مجمولا ترتيبي را مي تواک با شيوه اا واقعا ً خطي‬
‫و ترتيبي ترااز کرا و ار نتيجا با ترتيب کليااا با‬
‫رکورااا استيابي مؤنرا ااشت‪.‬‬
‫‪ )۲‬شاخص با يک کليا منمرا يا جااکنناه با ازاا ار‬
‫بلوک از رکوراااا اااه اا با جاا يک کليا (با ازاا ار‬
‫رکورا از اااه اا) ساختا مي شوا‪.‬‬
‫‪234‬‬

235.

‫درهم سازي‬
‫‪235‬‬

236.

‫استيابي )‪ O(1‬با فايل با ايک معنا است کا مها نيست‬
‫فايل تا يا اناازه بزرگ مي شوا ‪،‬بلرا استيابي با يک‬
‫رکورا اميشا با تعااا کا و نابتي تيگرا نياز اارا‪.‬‬
‫ار مقابل ايک نود استيابي ‪ ،‬استيابي )‪ O(N‬قرار اارا کا‬
‫از جستجوااا ترتيبي حاصل مي شوا و اريا اناازه فايل‬
‫بزراتر شوا تعااا تيگرااا نيز بيشتر مي شوا‪.‬‬
‫‪236‬‬

237.

‫تاب اراا سازا ماننا يک جعبا سياه است کا ارااه‬
‫کلياا ار ااخل آک انااختا مي شوا ‪،‬يک آارا ارئا مي‬
‫ااا‪ .‬با بياک رسمي تر ‪،‬اراا سازا ‪،‬تاب )‪ h(K‬است کا‬
‫کليا ‪ k‬را با يک آارا انتقال مي ااا‪.‬‬
‫‪237‬‬

238.

‫اراا سازا را تصاافي کراک نيز مي اوينا‪.‬‬
‫اراا سازا ‪،‬از ايک نظر کا يک کليا با يک آارا‬
‫وابستا مي شوا ‪،‬شبيا انايا سازا است‪.‬‬
‫‪238‬‬

239.

‫اراا سازا و انايا سازا از او جهت با اا تماوت اارنا ‪:‬‬
‫‪ )۱‬آارا اايي کا از اراا سازا با است مي آينا با‬
‫صورت تصاافي انا‪.‬‬
‫‪ )۲‬با اراا سازا ‪،‬او کليا مختلف ممرک است با يک‬
‫آارا انتقال اااه شونا‪.‬‬
‫‪239‬‬

240.

‫• ادامه مبحث درهم سازي‬
‫‪240‬‬

241.

‫اار او رکورا با يک مراک ار فايل انتقال يابنا با آک‬
‫برخورا مي اوينا‪.‬‬
‫‪241‬‬

242.

‫رو اياه آل مقابلا با برخورااا ايک است کا بتواک‬
‫الگوريتا تبايلي تياا کرا کا با طور کلي از برخورااا‬
‫جلوايرا کنا‪ .‬با ينيک الگوريتمي الگوريتا اراا سازا‬
‫کامل امتا مي شوا‪.‬‬
‫‪242‬‬

243.

‫ينايک راه مختلف براا کاا‬
‫کا بع ي از آنها لبارتنا از ‪:‬‬
‫تعااا برخورااا وجوا اارا‬
‫‪ )۱‬تراکناه کراک رکورااا‬
‫‪ )۲‬استمااه از حافظا ا افي‬
‫‪ )۳‬قرار اااک بي‬
‫‪243‬‬
‫از يک رکورا ار يک آارا‬

244.

‫با آارا اايي کا مي تواننا ينايک رکورا را نگهاارا‬
‫کننا باکت مي اوينا‪.‬‬
‫‪244‬‬

245.

‫ار ايک فصل يک الگوريتا اراا سازا سااه نوشتا تا انواد‬
‫المالي را کا ار الگوريتا اراا سازا انجاا مي شونا نشاک‬
‫ااا کا ايک الگوريا سا مرحلا اارا کا لبارتنا از ‪:‬‬
‫‪ )۱‬نماي‬
‫کليا با شرل لااا‬
‫‪ )۲‬تا کراک و ا افا کراک‬
‫‪ )۳‬تقسيا کراک بر يک لاا اول و استمااه از باقيماناه با‬
‫لنواک آارا‬
‫‪245‬‬

246.

‫ار حالت اياه آل تاب اراا سازا ‪،‬رکورااا را با اونا‬
‫اا توزي مي کنا کا ايچ برخوراا وجوا نااشتا باشا‪.‬‬
‫ينيک توزيعي را توزي يرنواخت اوينا زيرا رکورااا را با‬
‫صورت يرنواخت بيک آارا اا توزي کراه است‪.‬‬
‫‪246‬‬

247.

247

248.

‫بع ي از روشهايي کا با صورت بالقوه بهتر از اراا‬
‫سازا استنا ناا مي بريا‪:‬‬
‫‪ )۱‬جستجو ار کليااا براا يافتک يک الگو‬
‫‪ )۲‬تا کراک قسمتهايي از کليا‬
‫‪ )۳‬تقسيا يک کليا بر يک لاا‬
‫‪ )۴‬مجهور کراک کليا و ارفتک لاا مياني‬
‫‪248‬‬
‫‪ )۵‬تبايل مبنا‬

249.

‫توزي توآسوک ابزارا ريا ي را براا بررسي انرات‬
‫توزي تصاافي ارائا مي کنا‪.‬‬
‫از تواب توآسوک مي تواک براا تي بيني تعااا آارا‬
‫اايي کا ممرک است با رکوراااا ‪ 0‬و‪ 1‬و‪ 2‬وغيره نسبت‬
‫اااه شونا استمااه کرا‪.‬‬
‫‪249‬‬

250.

‫اريا مي توانيا تعااا برخورااا را کا کنيا ‪،‬بايا‬
‫ابزاراايي ااشتا باشيا کا ار صورت وقود برخورا ‪،‬با‬
‫آنها مبارزه کنيا‪ .‬رو سرريز فزايناه را براا ايک کار‬
‫انتخاب مي کنيا‪.‬‬
‫‪250‬‬

251.

‫اار جستجو براا يافتک رکورا آغاز شوا اما رکورا ار فايل هخيره نشاه‬
‫باشا يا اتماقي مي افتا؟‬
‫جستجو از آارا خانگي رکورا آغاز مي شوا و ايک جستجو ار‬
‫آارا ااا بعاا نيز اااما تياا مي کنا‪.‬‬
‫او اتماق ممرک است رخ ااا ‪:‬‬
‫‪ )۱‬اار با يک ف اا خالي مواجا شوا ‪،‬جستجوار ممرک است فرض‬
‫کنا کا ف اا خالي با ايک معنا است کا رکورا ار فايل موجوا نيست‪.‬‬
‫‪ )۲‬اار فايل تر باشا ‪،‬جستجو اااما تياا مي کنا تا با جايي مي رسا‬
‫کا جستجو ‪،‬از آنجا شرود شاه بوا و مشخص مي شوا کا رکورا ار‬
‫فايل موجوا نيست‪.‬‬
‫‪251‬‬

252.

‫منظور از طول جستجو ‪،‬تعااا استيابي ااا بزا براا‬
‫بازيابي يک رکورا از حافظا نانويا است‪.‬‬
‫‪252‬‬

253.

253

254.

‫انگاميرا قرار است کا يک رکورا هخيره يا بازيابي شوا‬
‫‪،‬آارا باکت خانگي ‪،‬توسط اراا سازا مشخص مي شوا‪.‬‬
‫کل باکت ار حافظا قرار مي ايرا‪.‬‬
‫براا تياا کراک رکورا مورا نظر ‪،‬رکوراااا موجوا ار‬
‫باکت جستجو مي شونا‪.‬‬
‫‪254‬‬

255.

‫براا محاسبا اانسيتا فشرااي فايل بايا اا با تعااا‬
‫آارا اا (باکت اا) و اا با تعااا رکورااايي کا مي‬
‫تواک ار ار آارا قرار ااا توجا کرا(اناازه باکت)‪.‬‬
‫‪255‬‬

256.

‫• ادامه مبحث درهم‬
‫سازي‬
‫• درهم سازي قابل‬
‫توسعه‬
‫‪256‬‬

257.

‫با لنواک يک اصل معموبً استمااه از باکت ااا‬
‫بزراتر از شيار ‪،‬اياه خوبي نيست(مگر ار مواراا کا‬
‫رکورااا خيلي بزرگ باشنا)‪.‬‬
‫‪257‬‬

258.

‫فايلهاا اراا سازا با او رو‬
‫بررسي قرار ارفتا اک متماوتنا ‪:‬‬
‫با فايلهايي کا تا کنوک مورا‬
‫‪ )۱‬يوت تاب اراا سازا ‪،‬بر اساا تعااا نابتي از آارا ااا‬
‫موجوا بنا نهااه شاه است ‪،‬اناازه منطقي فايل اراا سازا شاه‬
‫بايا از قبل مشخص باشا و امينيک ‪،‬وقتي ايک تاب بر روا فايل‬
‫لمل مي کنا ‪،‬طول فايل نابت باقي بمانا‪.‬‬
‫‪ )۲‬يوک شماره رکورا نسبي (‪ )RRN‬خانگي ار رکورا ار فايل‬
‫اراا سازا شاه ‪،‬نسبت با کليا منحصر با فرا است ‪،‬ار‬
‫روالي کا يک رکورا را ا افا يا حهف کنا و يا تنيير ااا ‪،‬بايا‬
‫طورا لمل کنا کا تيونا بيک رکورا و آارا خانگي آک را از بيک‬
‫نبرا‪.‬‬
‫‪258‬‬

259.

‫تنها تماوت بيک فايل اايي کا باکت اارنا و فايل اايي‬
‫کا تنها مي تواننا يک رکورا را ار خوا جاا اانا ايک‬
‫است کا ار فايل ااا باکت اار ‪ ،‬ار آارا ‪،‬ف اا کافي‬
‫براا هخيره سازا بي از يک رکورا منطقي را اارا‪.‬‬
‫‪259‬‬

260.

‫با او اليل حهف کراک يک رکورا از فايل اراا سازا‬
‫شاه تييياه تر از ا افا کراک رکورا است ‪:‬‬
‫‪ )۱‬محلي از فايل کا ار انر حهف کراک آزاا شاه است‬
‫‪،‬نبايا مان جستجوااا بعاا شوا‪.‬‬
‫‪ )۲‬بايا امراک استمااه مجاا از ف اااا آزاا شاه ‪،‬ار‬
‫ا افا کراک ااا بعاا وجوا ااشتا باشا‪.‬‬
‫‪260‬‬

261.

‫خوبي لالئا ويته ايک است کا ‪،‬او مشرلي را کا‬
‫ارقبل آک اشاره شا حل مي کنا ‪:‬‬
‫‪ )۱‬ف اا آزاا شاه مان جستجوا متوالي رکورا نمي‬
‫شوا‪.‬‬
‫‪ )۲‬مسلما ً مي تواک از ايک ف اا آزاا شاه براا هخيره‬
‫رکوراااا بعاا استمااه کرا‪.‬‬
‫‪261‬‬

262.

‫يوک رکوراااا سرريز ‪،‬تأنير بسزايي ار کارايي اارنا‬
‫ترنيک ااا زيااا براا جلوايرا از برخورااا تيشنهاا شاه‬
‫انا‪:‬‬
‫‪ )۱‬اراا سازا اواانا‬
‫‪ )۲‬سرريز فزايناه زنجيره اا‬
‫‪ )۳‬تيونا با ناحيا سرريز ايگر‬
‫‪ )۴‬جاول ااا تراکنااي‬
‫‪262‬‬

263.

‫اراا سازا قابل توسعا‬
‫‪263‬‬

264.

‫ويتاي مها ار ارخت ‪ AVL‬و ارخت ‪ B‬آک است کا‬
‫ايک ساختاراا خوا تنظيا استنا و شامل مرانيسا اايي انا‬
‫کا خوا را نگهاارا مي کننا‪.‬‬
‫‪264‬‬

265.

‫اياه کلياا ار فراينا اراا سازا قابل توسعا ‪،‬ترکيب‬
‫کراک اراا سازا معمولي با يک رو بازيابي ايگر‬
‫موسوا با تراا )‪ )trie‬است‪.‬‬
‫تراا اا را جستجوا مبنا نيز مي نامنا زيرا ريب‬
‫انشعاب ارخت جستجو برابر با تعااا نماااا مختلف‬
‫است کا ممرک است ار ار موقعيت از کليا ظاار شونا‪.‬‬
‫‪265‬‬

266.

‫اار رکوراا ا افا کنيا وجايي براا آک ار باکت‬
‫وجوا نااشتا باشا ‪،‬باکت را مي شرافيا‪.‬‬
‫‪266‬‬

267.

‫ااف از سيستا اراا سازا قابل توسعا ‪،‬يافتک رااي‬
‫براا افزاي ف اا آارا ‪،‬ار تاسخ با سرريز شاک‬
‫است نا تاسخ ااي با ايجاا رشتا اا بلنا از رکوراااا‬
‫سرريز و باکت اايي کا بايا با طور خطي جستجو شونا‪.‬‬
‫‪267‬‬

268.

‫لمليات اصلي روا باکت اا اقيقا ً اماننا لمليات‬
‫رکوراااا شاخص است ‪:‬‬
‫افزواک يک جمت کليا‪ -‬آارا با باکت ‪،‬جستجو با انبال‬
‫يک کليا و بازارااناک آارا آک ‪،‬و حهف يک کليا‪.‬‬
‫‪268‬‬

269.

‫حهف ‪،‬لرا فراينا ا افا کراک است ‪،‬با هکر ايک‬
‫نرتا کا فقط ار صورتي مي تواک رکوراااا او باکت‬
‫را با اا ترکيب کرا کا او باکت با اا اوست باشنا‬
‫يعني ايک او باکت از شرافتک يک باکت نتيجا شاه‬
‫باشنا‪.‬‬
‫‪269‬‬

270.

‫لمل تنزل شامل تخصيص ف ا با آرايا جاياا از‬
‫آارا ااا باکت است کا اناازه آک نصف اناازه اوليا‬
‫است و ستا آارا ااا باکت مشترک ار ار جمت‬
‫سلول را با يک سلول واحا ار فهرست راانماا جايا‬
‫کتي مي کنا‪.‬‬
‫‪270‬‬

271.

‫اراا سازا تويا و اراا سازا قابل توسعا از نظر‬
‫لملررا شباات بسيار اارنا‪.‬‬
‫ار او از يک فهرست راانما براا فقط آارا باکت اا‬
‫استمااه مي کننا و ار او فهرست راانما را از طريق‬
‫استمااه از تراا اا توسعا مي اانا و ار او تاب اراا‬
‫سازا را با طور محلي با صورت يک تراا جستجوا‬
‫اواويي توسعا مي اانا تا سرريز شاک قابل کنترل باشا‪.‬‬
‫‪271‬‬

272.

‫اراا سازا تويا وار اا‬
‫اختالف اصلي مياک او رو‬
‫سازا قابل توسعا آک است کا ار اا سازا تويا ‪،‬رشا‬
‫تاريجي و آاستا فهرست راانما را امراک تهير مي سازا‬
‫حال آنرا اراا سازا قابل توسعا فهرست راانما را با‬
‫او برابر کراک آک بزرگ مي کنا‪.‬‬
‫اراا سازا تويا فهرست راانماا توسعا يافتا را با‬
‫لنواک يک ساختار متصل بياک مي کنا کا با نوبا خوا با‬
‫لنواک يک آرايا قابل بياک است‪.‬‬
‫‪272‬‬
English     Русский Rules