بخشی از پاورپوینت
--- پاورپوینت شامل تصاویر میباشد ----
اسلاید 1 :
بازيابي سريع داده ها – مرتب سازي
(Finding data quickly – Sorting)
روشهايبازيابيسريع داده ها چگونه ميباشند؟
يادآوريجستجوي دودويي (Binary Searching)؟
مقايسه با جست وجوي سري(sequential)؟
محدوديت ها يا معايب جست و جوي دودويي کدامند؟
مرتب سازي کليدها (key sorting) چگونه است؟
روش Indexing چيست؟
مزايايIndexing کدامند؟
اسلاید 2 :
بازيابي سريع داده ها
روشهايبازيابيسريع داده ها چگونه ميباشند؟
يادآوريجستجوي دودويي (Binary Searching)؟
مثال:
يک فايل با رکورد هاي به طول ثابت را در نظر ميگيريم.
فرض کنيم که در جست و جوي رکوردي با مقدار کليدي مشخصي ميباشيم.
حالت اول: اگر فايل مرتب نشده باشد:
بايستي رکورد هاي آنرا يک به يکخوانده و کليد آنها را با مقدار مورد نظر مقايسه کنيم.
اين کار ممکن است به خواندن کليه رکورد ها منتهي شود. (چرا؟)
حالت دوم: اگر فايل بر حسب کليد مورد نظر مرتبشده باشد:
روش بهينه همان جست و جوي دودويي ميباشد. (چرا؟)
الگوريتم آن در شکل 13-6 کتاب موجود است. (با اشتباه چاپي!)
اسلاید 3 :
يادآوري الگوريتم جستجوي دودويي :
intBinarySearch
(FixedRecordFile & File, RecType & obj, KeyType & key)
{
int low = 0; int high = file.NumRecs()-1;
While (low <= high)
{
int guess = (high + low) / 2;
file.ReadByRRN (obj, guess);
if (obj.Key() == key) return 1;
if (obj.Key() < key ) low = guess +1;
else high = guess - 1;
return 0;
اسلاید 4 :
بازيابي سريع داده ها
مقايسه با جست وجوي سري(sequential)؟
مثال:
جستجوي کليد در يک فايل با تعداد 2000=n رکورد.
حالت اول: جست و جوي سري:
تعداد ماکزيمم رکورد هاي خوانده شده برابر با تعداد کل رکورد ها خواهد بود.
ممکن است تا 2000 رکورد خوانده شود.
اگر تعداد رکورد ها دوبل شود، تعداد خواندن رکورد نيز دوبل خواهد شد. (چرا؟)
حالت دوم: جست و جوي دودويي:
تعداد ماکزيمم رکورد هاي خونده شده برابر با 1+log(n) خواهد بود.
ممکن است تا1+log(2000) يعني 11رکورد خوانده شود.
اگر تعداد رکورد ها دوبل شود، فقط يک خواندن رکورد اضافه مي گردد.
براي جست و جوي دودويي بايستي طول رکورد ها ثابت باشد. (چرا؟)
اسلاید 5 :
بازيابي سريع داده ها
محدوديت ها يا معايب جست و جوي دودويي کدامند؟
جست و جوي يک کليد مشخص معمولا بيش از يک يا دو دسترسي به ديسک نياز دارد. (چرا؟)
مثلا در يک فايل با 10000رکورد، 16 يا 17دسترسي به ديسک لازم خواهد بود.
نگهداري يک فايلبطور مرتب شدههزينه بالايي خواهد داشت. (کدام؟)
هزينه ها؟ (CPU ، I/O ، متد برنامه نويسي، ... )
انجام مرتب سازي فايل در حافظه اصلي (RAM) فقط در مورد فايل هاي کوچکعملي ميباشد.
در مورد فايل هاي بزرگتر بايستي تعداد زيادي دسترسيبه ديسک پيش بيني شود. (چرا؟)
استفاده از RRN براي فايل هاي حاوي رکورد متغير عملي نخواهد بود.
اسلاید 6 :
روش مرتب سازي کليدها (key sorting) چگونه است؟
روشي برای مرتب سازيفايل هاي بزرگ که در حافظه RAM جا نميگيرند.
هنگام مرتب سازي، از آوردن کل رکورد ها به حافظه خودداري ميگردد.
برای مرتب سازی کافيست فقط مقادير کليد رکوردها در حافظه موجود باشد.
همراه با RRN رکوردها! (چرا؟)
دراينصورت مرتب سازي کل کليد ها در حافظه انجام ميشود. (Internal Sort)
سپس بترتيب کليدها، رکوردها را خوانده و در فايل جديدي مينويسيم.
اسلاید 7 :
چه تعداد دسترسي به ديسک نياز خواهد بود؟
در مرحله اول:کل رکوردهاي فايل بايستي بطور سري (sequential) خوانده شوند.
در مرحله دوم:تکتک رکوردها بطور Random با استفاده از RRN خوانده شده و در فايل جديد نوشته خواهند شد. ( نوشتن بطور سري ؟)
چه احتياجي به دوباره نويسي فايل وجود دارد؟
آيا کافي نيست که ليست مرتب شده کليد ها را حفظ کنيم؟
اسلاید 8 :
روش Indexing چيست؟
کليدهاي مرتب شده يک فايل را در جايي مثلا يک فايل ديگر حفظ ميکنيم.
اين فايل را indexميناميم.
براي دسترسي سريع به يک رکورد با کليد مشخص، از آن استفاده ميکنيم. (چگونه؟)
اسلاید 9 :
بازيابي سريع داده ها - Indexing
مزايايIndexing کدامند؟
امکان مرتب سازي داده ها بدون نياز به جابجايي رکوردها در فايل. (چرا؟)
امکان تعريفمسيرهاي مختلف براي بازيابي سريع داده ها. (چگونه؟)
امکان دسترسي سريع به فايل هاي با رکورد متغير بر حسب کليد.
امکان استفاده بهينه از حافظه RAM براي جست و جوی کليد ها. (چرا؟)
امکان انجام عمل جست و جويدودوييدر حافظه RAM.
جلوگيری از ايجاد اشاره گرهای سرگردان (dangling pointers) در داخل فايل. (چگونه؟)
اسلاید 10 :
اشاره گرهای سرگردان(dangling pointers)چيست؟
در روشهاي بازيابي فضاي فايل ها و استفاده از A ail List ديديم که رکوردها بوسيله نوعي اشاره گر (مثل RRN يا Byte Offset) به يکديگر مرتبط ميباشند.
اين رکوردها را Pinned Record ميخوانيم
تغيير محل فيزيکي آنها باعث ايجاداشاره گرهای سرگردان (dangling pointers) ميشود.
استفاده از indexingمانع ايجاد اين مشکل خواهد شد. (چرا؟)
