ИнформатикаПохожие презентации:
ذخیره و بازیابی اطلاعات(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.
2627.
ايسک ارااک اا معموبً ينا صمحا اارنا .شياراايي کاامستقيما ً ار باب و تاييک يرايگر قرار اارنا ،يک سايلنار را
تشااريل مااي اانااا .اامياات ساايلنار ار آک اساات کااا بااا ام اا
اطاللاااات روا ياااک سااايلنار ماااي تاااواک بااااوک حرکااات اااک
بااازوا نگهاارناااه اااا ( )headخواناااک/نوشااتک اسااتيابي
ااشت .حرکت ايک بازو تيگرا ( )seekingناا اارا.
27
28.
2829.
ظرفياات ايسااک تااابعي از تعااااا ساايلناراا ،تعاااا شااياراا ب ااازاا ار سيلنار و ظرفيت ار شيار است.
29
30.
او روبراا سازمانااي اااه اا بر روا ايسک وجوا اارا :
)۱بر اساا سرتور
)۲بر اساا بلوک ااا تعريف شاه توسط کاربر
30
31.
کالستر لبارت از تعااا نابتي از سرتورااا تيوستااست.
مايريت فايل براا ار نظر ارفتک فايل با لنواک
مجمولا اا از کالستراا و ار ليک حال حمظ حالت
سرتورا ،سرتورااا منطقي را با کالسترااا
فيزيري کا با آنها تعلق اارا ،با وسيلا جاول
تخصيص فايل ( )FATارتباط مي ااا.
31
32.
اااار ف اااا زيااااا روا ايسااک باشااا ،ممرااک اسااتبتااواک کااارا کاارا کااا فاياال بااا طااور کاماال از کالسااترااا
تيوستا تشريل شوا .ار ينيک موراا امتا ماي شاوا کاا
فايل حاوا يک حا ( )extentاست.
32
33.
3334.
اتالف ف ا ار ااخل ياک سارتور را تراکناااي ااخلايماااي نامناااا .ساااازمانااي بلاااوک ااااا مشااارالت توشاااايي
ساارتوراا و تراکنااااي را ناااارا ،زياارا اناااازه بااالک ااا
ماااي تواناااا تنييااار کناااا تاااا ساااازمانااي منطقاااي اااه ااااا
امراک تهير شوا.
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.
4748.
بافر I/Oسيستا ،با مايريت فايل ايک امراک را ميااااا تااا اااه اااا را ار واحااااايي بااا اناااازه ساارتور يااا
بلوک بخوانا يا بنويسا.
48
49.
لمل کنترل لمليات ايسک توسط اساتگااي انجااامي شوا کا کنترلگر ايسک نامياه مي شوا.
49
50.
سيساتا اااا I/Oتقريباا ً اميشااا حاااقل او باافر اارناا.يرااااي بااااراا ورواا و ايگاااارا بااااراا خروجااااي .برخااااي
سيستا ااا فايل از يک طرح بافرااي موسوا باا اساتخر
بافرا ( )buffer spoolingاستمااه مي کننا.
50
51.
با تراکن ورواا ،با يک بار خواناک ،نا يک بار بافربلرا مجمولا اا از بافراايي کا اااه ااا يک بلوک بايا
ار آک اا تخ شوا شناسايي مي شوا.
با تمرکز خروجي ،ينا بافر را مي تواک ارااا آورا و
يرباره بر روا اما آنها نوشت ،بايک ترتيب بزا نيست
آنها را ار يک بافر خروجي کتي کرا.
51
52.
استا با نوبت با ايک يهار جاول زير مراجعا مي کنا تااطاللاتي را کا براا نوشتک ار فايل موجوا ار ايسک نياز اارا
با است آورا :
)۱جاول توصيف ار فايل
)۲جاول فايل ااا باز
)۳جاول تخصيص فايل
)۴جاول اره ااا انايسي
52
53.
5354.
اشاره ارا از يک فهرست با ايناوا فايال را اتصاالسخت ( )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.
6768.
مايريت فايلهايي از رکورااا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.
152153.
الگوريتا مرتب سازا ارمي او بخاارا:
ابتاا اارا را ايجااا ماي کنايا ساتا کلياااا را باا
صورت مرتب شاه ار خروجي قرار مي اايا.
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.
163164.
ااف اصلي ايک مرتب سازا ااغامي آک اسات کاا قااارباشيا فايلهايي را مرتب سازا کنيا کا ار حافظا جا نمي
شونا.
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.
شاخص بناا ينا سطحي و ارختهاا B179
180.
مشرل اصلي نگهااشتک شاخص ار حافظا جانبي ايکاست کا استيابي با حافظا جانبي کنا است.
ايک مشرل مي توانا با او مشرل ويته تقسيا شوا :
)۱جستجو بر حسب شاخص بايا سريعتر از جستجوا
اواويي باشا.
)۲ارج وحهف بايا با سرلت جستجو کراک انجاا شوا.
180
181.
ارخت جستجوا اواويي يا اشرالي اارا؟ )۱براا شاخص بناا روا ايسک سرلت بزا را
ناارا.
)۲يک راابرا مؤنر براا موازنا کراک ارخت وجوا
ناارا.
181
182.
تالشهايي براا حل مشرالت ارخت جستجوا اواوييانجاا ارفت کا او تا از آنها لبارتنا از :
)۱ارخت ااا AVL
)۲ارخت ااا اواويي صمحا صمحا
182
183.
ارخت AVLارختي با ارتماد موازنا شاه است.يعني اينرا ،اختالف مجاز مياک ار او زيرارخت
کا ريشا مشترکي اارنا محاوايت اارا و حااکنر
تماوت مجاز ۱است.
183
184.
184185.
او مزيت کا ارخت ااا AVLرا با ااميت مي کننا لبارتنا از : )۱با تعييک کراک حااکنر تماوت مجاز ار ارتماد ار او
زيرارخت ،ارخت ااا AVLحااقل کارايي را ار جستجو
ت ميک مي کننا.
)۲براا اينرا انگاا ارج ار ارخت ، AVLويتاي خوا را
حمظ کنا ،مستلزا يهار نود يرخ است.
185
186.
ارخت اواويي صمحا اا ،سعي مي کنا با قرار اااکينايک اره اواويي ار يک صمحا ايسک ،مشرل را حل
کنا.
186
187.
187188.
وا ح است کا تقسيا کراک ارخت با ينايک صمحاامراک جستجوا سريعتر ار حافظا جانبي را فرااا مي
کنا وبا است آوراک اطاللات را سريعتر از ار رو
ايگر استيابي با استمااه از کليا امراک تهير مي کنا.
188
189.
مشرل اصلي ارخت ااا صمحا اا انوز اا استمااهاز ايسک است.
189
190.
ارخت ااا Bشاخص ااا ينا سطحي استناکامشرل ازينا خطي ارج و حهف کراک را حل مي کننا.
ايک ويتاي بالث جهابيت ارخت Bمي شوا ،زيرا
اکنوک ارخت ااا Bرو استاناارا شاخص سازا
استنا و از تاييک با باب ساختا مي شونا و لملياتي نظي
ارج و حهف ،ار حافظا روا اره ااا ارخت Bالمال
مي شوا.
190
191.
• ادامه مبحث شاخص بندي چند سطحي و درختهاي B191
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.
247248.
بع ي از روشهايي کا با صورت بالقوه بهتر از ارااسازا استنا ناا مي بريا:
)۱جستجو ار کليااا براا يافتک يک الگو
)۲تا کراک قسمتهايي از کليا
)۳تقسيا يک کليا بر يک لاا
)۴مجهور کراک کليا و ارفتک لاا مياني
248
)۵تبايل مبنا
249.
توزي توآسوک ابزارا ريا ي را براا بررسي انراتتوزي تصاافي ارائا مي کنا.
از تواب توآسوک مي تواک براا تي بيني تعااا آارا
اايي کا ممرک است با رکوراااا 0و 1و 2وغيره نسبت
اااه شونا استمااه کرا.
249
250.
اريا مي توانيا تعااا برخورااا را کا کنيا ،باياابزاراايي ااشتا باشيا کا ار صورت وقود برخورا ،با
آنها مبارزه کنيا .رو سرريز فزايناه را براا ايک کار
انتخاب مي کنيا.
250
251.
اار جستجو براا يافتک رکورا آغاز شوا اما رکورا ار فايل هخيره نشاهباشا يا اتماقي مي افتا؟
جستجو از آارا خانگي رکورا آغاز مي شوا و ايک جستجو ار
آارا ااا بعاا نيز اااما تياا مي کنا.
او اتماق ممرک است رخ ااا :
)۱اار با يک ف اا خالي مواجا شوا ،جستجوار ممرک است فرض
کنا کا ف اا خالي با ايک معنا است کا رکورا ار فايل موجوا نيست.
)۲اار فايل تر باشا ،جستجو اااما تياا مي کنا تا با جايي مي رسا
کا جستجو ،از آنجا شرود شاه بوا و مشخص مي شوا کا رکورا ار
فايل موجوا نيست.
251
252.
منظور از طول جستجو ،تعااا استيابي ااا بزا براابازيابي يک رکورا از حافظا نانويا است.
252
253.
253254.
انگاميرا قرار است کا يک رکورا هخيره يا بازيابي شوا،آارا باکت خانگي ،توسط اراا سازا مشخص مي شوا.
کل باکت ار حافظا قرار مي ايرا.
براا تياا کراک رکورا مورا نظر ،رکوراااا موجوا ار
باکت جستجو مي شونا.
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