Lecture 9 بازیابی سریع داده ها – مرتب سازی Finding data quickly – Sorting
(Sections 6.3, 6.4 , 7.1, 7.2)
In the Name of God
File Structure
بازیابی سریع داده ها – مرتب سازی (Finding data quickly – Sorting)
روشهای بازیابی سریع داده ها چگونه میباشند؟
یادآوری جستجوی دودویی (Binary Searching)؟
مقایسه با جست وجوی سری(sequential)؟
محدودیت ها یا معایب جست و جوی دودویی کدامند؟
مرتب سازی کلیدها (key sorting) چگونه است؟
روش Indexing چیست؟
مزایای Indexing کدامند؟
File Structure
بازیابی سریع داده ها
روشهای بازیابی سریع داده ها چگونه میباشند؟
یادآوری جستجوی دودویی (Binary Searching)؟
مثال:
یک فایل با رکورد های به طول ثابت را در نظر میگیریم.
فرض کنیم که در جست و جوی رکوردی با مقدار کلیدی مشخصی میباشیم.
حالت اول: اگر فایل مرتب نشده باشد:
بایستی رکورد های آنرا یک به یک خوانده و کلید آنها را با مقدار مورد نظر مقایسه کنیم.
این کار ممکن است به خواندن کلیه رکورد ها منتهی شود. (چرا؟)
حالت دوم: اگر فایل بر حسب کلید مورد نظر مرتب شده باشد:
روش بهینه همان جست و جوی دودویی میباشد. (چرا؟)
الگوریتم آن در شکل 13-6 کتاب موجود است. (با اشتباه چاپی!)
File Structure
بازیابی سریع داده ها
یادآوری الگوریتم جستجوی دودویی :
int BinarySearch
(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;
}
File Structure
بازیابی سریع داده ها
مقایسه با جست وجوی سری(sequential)؟
مثال:
جستجوی کلید در یک فایل با تعداد 2000=n رکورد.
حالت اول: جست و جوی سری:
تعداد ماکزیمم رکورد های خوانده شده برابر با تعداد کل رکورد ها خواهد بود.
ممکن است تا 2000 رکورد خوانده شود.
اگر تعداد رکورد ها دوبل شود، تعداد خواندن رکورد نیز دوبل خواهد شد. (چرا؟)
حالت دوم: جست و جوی دودویی:
تعداد ماکزیمم رکورد های خونده شده برابر با 1+log(n) خواهد بود.
ممکن است تا1+log(2000) یعنی 11رکورد خوانده شود.
اگر تعداد رکورد ها دوبل شود، فقط یک خواندن رکورد اضافه می گردد.
برای جست و جوی دودویی بایستی طول رکورد ها ثابت باشد. (چرا؟)
File Structure
بازیابی سریع داده ها
محدودیت ها یا معایب جست و جوی دودویی کدامند؟
جست و جوی یک کلید مشخص معمولا بیش از یک یا دو دسترسی به دیسک نیاز دارد. (چرا؟)
مثلا در یک فایل با 10000رکورد، 16 یا 17 دسترسی به دیسک لازم خواهد بود.
نگهداری یک فایل بطور مرتب شده هزینه بالایی خواهد داشت. (کدام؟)
هزینه ها؟ ( CPU ، I/O ، متد برنامه نویسی، … )
انجام مرتب سازی فایل در حافظه اصلی (RAM) فقط در مورد فایل های کوچک عملی میباشد.
در مورد فایل های بزرگتر بایستی تعداد زیادی دسترسی به دیسک پیش بینی شود. (چرا؟)
استفاده از RRN برای فایل های حاوی رکورد متغیر عملی نخواهد بود.
File Structure
بازیابی سریع داده ها
روش مرتب سازی کلیدها (key sorting) چگونه است؟
روشی برای مرتب سازی فایل های بزرگ که در حافظه RAM جا نمیگیرند.
هنگام مرتب سازی، از آوردن کل رکورد ها به حافظه خودداری میگردد.
برای مرتب سازی کافیست فقط مقادیر کلید رکوردها در حافظه موجود باشد.
همراه با RRN رکوردها! (چرا؟)
دراینصورت مرتب سازی کل کلید ها در حافظه انجام میشود. (Internal Sort)
سپس بترتیب کلیدها، رکوردها را خوانده و در فایل جدیدی مینویسیم.
File Structure
مرتب سازی کلیدها (key sorting)
مرتب سازی کلیدها (key sorting) چگونه است؟
مثال:
File Structure
مرتب سازی کلیدها (key sorting)
چه تعداد دسترسی به دیسک نیاز خواهد بود؟
در مرحله اول: کل رکوردهای فایل بایستی بطور سری (sequential) خوانده شوند.
در مرحله دوم: تک تک رکوردها بطور Random با استفاده از RRN خوانده شده و در فایل جدید نوشته خواهند شد. ( نوشتن بطور سری ؟)
چه احتیاجی به دوباره نویسی فایل وجود دارد؟
آیا کافی نیست که لیست مرتب شده کلید ها را حفظ کنیم؟
File Structure
بازیابی سریع داده ها – Indexing
روش Indexing چیست؟
کلیدهای مرتب شده یک فایل را در جایی مثلا یک فایل دیگر حفظ میکنیم.
این فایل را index مینامیم.
برای دسترسی سریع به یک رکورد با کلید مشخص، از آن استفاده میکنیم. (چگونه؟)
File Structure
بازیابی سریع داده ها – Indexing
مزایای Indexing کدامند؟
امکان مرتب سازی داده ها بدون نیاز به جابجایی رکوردها در فایل. (چرا؟)
امکان تعریف مسیرهای مختلف برای بازیابی سریع داده ها. (چگونه؟)
امکان دسترسی سریع به فایل های با رکورد متغیر بر حسب کلید.
امکان استفاده بهینه از حافظه RAM برای جست و جوی کلید ها. (چرا؟)
امکان انجام عمل جست و جوی دودویی در حافظه RAM.
جلوگیری از ایجاد اشاره گرهای سرگردان (dangling pointers) در داخل فایل. (چگونه؟)
File Structure
بازیابی سریع داده ها – Indexing
اشاره گرهای سرگردان (dangling pointers) چیست؟
در روشهای بازیابی فضای فایل ها و استفاده از Avail List دیدیم که رکوردها بوسیله نوعی اشاره گر (مثل RRN یا Byte Offset) به یکدیگر مرتبط میباشند.
این رکوردها را Pinned Record میخوانیم
تغییر محل فیزیکی آنها باعث ایجاداشاره گرهای سرگردان (dangling pointers) میشود.
استفاده از indexing مانع ایجاد این مشکل خواهد شد. (چرا؟)
File Structure
بازیابی سریع داده ها – Indexing
نگهداری index ها در خارج از حافظه RAM چگونه خواهد بود؟
حفظ صحت اطلاعات در index ها چگونه خواهد بود؟