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

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

اسلاید 1: ساختار فایل ها (ذخیره و بازیابی اطلاعات) تهیه کننده : جعفر پورامینی منبع: سیستم و ساختار فایل مولف: زولیک تعداد واحد:3 www.darage1web.gigfa.com

اسلاید 2: فصل اولآشنایی با طراحی و مشخصات ساختار فایل ها

اسلاید 3: هدف کتابیافتن راههایی برای به حداقل رساندن دستیابی به دیسک، برای فایل هایی است که اندازه و محتویات آنها تغییر می کند.ساختار فایل ترکیبی از نحوه نمایش داده ها در فایل ها و عملیات لازم برای دستیابی به داده ها است در حالت ایده آل، کسب اطلاعات مورد نظر با یک دسترسیدر صورتی که امکان پذیر نیست با حداقل دسترسیبه حداکثر رساندن احتمال وجود اطلاعات مورد نظر در حافظه

اسلاید 4: عوامل موثر در طراحی ساختار فایلشرایط خاص دیسک ها این الزام را به وجود می آورد که ساختارهای ویژه ای برای ذخیره و بازیابی داده در آنها توسعه دهیم تا در حد امکان مشکل های کار با دیسک را کاهش دهیمزمان دستیابی نسبتا کم دیسک هاظرفیت بالای آنهاحفظ اطلاعات پس از قطع جریان برق

اسلاید 5: تاریخچه مختصری درباره طراحی ساختار فایلدستیابی ترتیبی (فایل ها بر روی نوار) (مرتبه زمانی n)درخت دودویی AVL (مرتبه زمانی log d)درخت Bدرخت B+:ترکیب درخت B و لیست پیوندیدستیابی مستقیم

اسلاید 6: کیت ابزار مفهومی: مواد ساختار فایلابزارهایی که برای حل مشکلات مشابه بکار گرفته می شوندبافرها، بلوکها و باکتها: کاهش تعداد دستیابی به دیسک

اسلاید 7: فصل دوم عملیات مهم پردازش فایل

اسلاید 8: فایلها همان مجموعه ای از بایت ها هستند که در یک دیسک به صورت فیزیکی در کنار یکدیگر قرار گرفته اند. از دیدگاه برنامه کاربردی ، فایل تعریف دیگری دارد . استفاده از فایلهای منطقی به برنامه این امکان را می دهد تا اعمال اجرا شده روی یک فایل را توصیف کند؛ بدون اینکه بداند چه فایل فیزیکی را مورد استفاده قرار می دهد. سپس میتوان برنامه را برای پردازش هر یک از چند فایل متفاوت که دارای ساختاری یکسان هستند به کار برد.فایلهای فیزیکی و منطقی

اسلاید 9: باز کردن فایل هامعرفی تابع OPEN FD=OPEN(FILENAME,FLAGS[,PMODE]) FD:توصیف کننده فایل.FILENAME:یک رشته کاراکتری حاوی نام فایل فیزیکی.FLAGS:عملکرد تابع OPEN را کنترل کرده وتععیین می کند که فایل موجود را برای خواندن یا نوشتن باز می کند یا خیر.PMODE:حالت محافظت فایل را بر می گرداند.

اسلاید 10:

اسلاید 11: بستن فایل هاهنگامی که برنامه ای به صورت عادی پایان می یابد، فایل ها معمولا به طور خودکار بسته می شوند.در نتیجه اجرای یک دستور بستن در داخل برنامه فقط برای محافظت آن در برابر اتلاف داده ها در صورت توقف برنامه و آزاد کردن نام فایل های منطقی برای استفاده مجدد می باشد.

اسلاید 12: خواندن و نوشتنREAD(SOURCE_FILE,DESTINATION_ADDR,SIZE)WRITE(DESTINATION_FILE,SOURCE_ADDR,SIZE)DESTINATION: نام فایل مقصدSOURCE: نام فایل منبعSIZE: تعداد بایتهایی که باید خوانده یا نوشته شود

اسلاید 13: پیگرد: عمل انتقال مستقیم به یک موقعیت معین در فایل را پیگرد می گویند.SEEK(SOURCE_FILE,OFFSET)SOURCE_FILE:نام فایل منطقی که در آن جستجو صورت می گیردOFFSET:میزان حرکت اشاره گر فایل را مشخص می کند

اسلاید 14: پیگرد با جریان های CPOS=FSEEK(FILE,BYTE_OFFSET,ORIGIN)POS: یک مقدار صحیح بزرگ که توسط FSEEK بر گردانده می شود که برابر با موقعیت فعلی اشاره گر است.FILE: توصیف کننده فایلی که FSEEK باید در آن اعمال شود.BYTE_OFFSET: تعداد بایتهایی که باید از مبدا حرکت داده شود.

اسلاید 15: #INCLUDE<STDIO.H>Main( ) {Char ch ;FILE *file ;Char filename [20] ;Printf ( enter the name of the file) ;//step 1Gets (filename) ;//step 2File = fopen (filename, r) ;//step 3While (fread(&ch, 1, 1, file) ! = 0) ;//step 4aFwrite (&ch, 1, 1, student) ;//step 4bFclose (file) ; //step 5}برنامه نمایش محتویات با استفاده از جریان

اسلاید 16: برنامه نمایش محتویات با استفاده از کلاسهای جریان ++ C: #include <fsream.h>main ( ) {char ch ;fstream file ;char file name [20] ;cout << enter the name of the file: ; //step 1cin >> filename;//step 2file . open (filename,ios::in); //step 3file . unsetf(ios::skipws);while (1) { file >> ch; //step 4a if (file.fail ()) break; cout << ch; //step 4b } file . close (); //step 5}

اسلاید 17: ساختار فهرست ها در یونیکسچون هر نام فایل در سیستم یونیکس بخشی از سیستم فایلی است که با ریشه آغاز می شود هر فایل را می توان انحصارا با دادن نام مسیر آن شناسایی کرد.هنگامی که فرمانهایی برای سیستم یونیکس صادر می شود این کار در داخل فهرستی انجام می شود که فهرست جاری نامیده می شود.

اسلاید 18: نمونه ای از فهرست ها در یونیکسBINUSRUSR6DEVADDBCCYACCBINLIBMYDIRLIBCONSOLEKBDTAPELIBS.ALIBM.AADDFDF

اسلاید 19: دستگاههای فیزیکی و فایل های منطقیدر یونیکس، فایل مجموعهای از بایتها استدر یونیکس چگونگی و محل ذخیره فایل ها مهم نیستدر یونیکس مهم نیست که فایل ها از کجا می آینددر یونیکس شکل فیزیکی فایل مهم نیست زیرا نمای منطقی فایل در یونیکس یکی است.

اسلاید 20: فصل سومحافظه جانبی و نرم افزار سیستم

اسلاید 21: تعريف حافظه هر دستگاهي که بتوان اطلاعات را در آن ذخيره نموده به نحوي که کاربرد در هر لحظه بتواند به اطلاعات مورد نظرش دستيابي پيدا کند حافظه ناميده مي شود.

اسلاید 22: حافظهانواع دستگاه ها از نظر نوع دستیابیدستیابی مستقیم (DASD): از طریق آدرس می‌توان به طور مستقیم به اطلاعات دسترسی داشت. زمان دسترسی در این حالت برای تمام اطلاعات تقریبا برابر است، مانند هارد دیسک‌هادستیابی سری: دستگاه‌هایی که دستیابی ترتیبی را پشتیبانی می‌کنند. در این حالت برای خواندن یا نوشتن یک قطعه داده‌ی خاص، باید از تمام داده‌های پیش از آن گذر کرد

اسلاید 23: دیسکهادیسک های مغناطیسی در اشکال مختلف وجود دارنددیسک های سخت ظرفیتی بالا با هزینه پایین به ازای هر بیت ارائه می دهند.دیسک های فلاپی ارزان هستند ولی سرعت آنها کم است و داده های نسبتا کمی را نگهداری می کنند.

اسلاید 24: انواع حافظه هاي برون ماشيني از نظر تكنولوژي ساخت چهار تكنولوژي وجود دارد:تكنولوژي الكترومكانيك الكترو مغناطيستكنولوژي الكترو اپتيكتكنولوژي الكترومغنااپتيك

اسلاید 25: سازمان دیسک هایک دیسک گردان معمولا از چند صفحه تشکیل شده است، که هر صفحه دو سطح داردهر صفحه شامل تعدادی شیار (TRACK) استاطلاعات در شیارهای دیسک نگهداری می شود هر شیار غالبا به چند سکتور (SECTOR) تقسیم می شود سکتور کوچکترین بخشی از دیسک است که قابل آدرس دهی است.

اسلاید 26: سازمان دیسک هاشیار‌هایی که مستقیما در بالا و پایین یکدیگر قرار دارند یک سیلندر را تشکیل می‌دهند.بودن حرکت بازو می‌توان به همه‌ی اطلاعات روی یک سیلندر دسترسی داشت‌حرکت بازو، معمولا کندترین بخش خواندن اطلاعات از روی دیسک است.

اسلاید 27: جایگاه سیلندروهدهای خواندن ونوشتن

اسلاید 28: برآورد نیازهای سرعت و ظرفیت هاظرفیت شیار=تعداد سکتورها *طول هر سکتور بر حسب بایتظرفیت سیلندر=تعداد شیار ها در هر سیلندر*ظرفیت شیارظرفیت دیسک=تعداد سیلندرها*ظرفیت سیلندر

اسلاید 29: سازماندهی شیارها به وسیله سکتورهاسازماندهی بر اساس سکتورسازماندهی بر اساس بلوک‌های سازماندهی شده توسط کاربر

اسلاید 30: روش های سازمان دهی داده ها بر روی دیسکبر اساس سکتوربر اساس بلوک های تعریف شده توسط کار بر

اسلاید 31: سازمان دهی سکتور ها بر روی یک شیارسکتور ها بخش های مجاور و با اندازه ثابت از یک شیار باشند(این روش راه خوبی برای در نظر گرفتن فایل به طور منطقی است اما راه خوبی برای نگه داشتن فیزیکی سکتور ها نیست.)فاصله گذاری میان سکتورها(یعنی بین سکتور هایی که از نظر منطقی مجاورند چند سکتور فاصله می گذارند.)

اسلاید 32: شیار سکتوروگپ

اسلاید 33: کلاستر:کلاستر عبارت از تعداد ثابتی از سکتور های پیوسته استکلاستر های بزرگ تعداد زیادی از سکتور ها را بدون پیگرد می خوانند.استفاده از کلاستر های بزرگ در هنگام پردازش ترتیبی فایل به کارایی بیشتر منجر می شود.

اسلاید 34: پراکندگی طول تمام سکتور های موجود در یک دیسک باید یکسان باشد اما همیشه این تناسب بر قرار نیست .دو شیوه برای مقابله با این روش وجود دارد:نگهداری یک رکورد در هر سکتور.قرار دادن رکورد ها به طور متوالی به طوری که بخشی از رکورد در یک سکتور و بخش دیگر آن در سکتور دیگر قرار گیرد.

اسلاید 35: سازمان دهی شیار ها به کمک بلوکگاهی شیار ها به سکتور تقسیم نمی شوند بلکه به تعدادی از بلوک ها تقسیم می شوند.همانند سکتور ها بلوکها را غالبا رکورد های فیزیکی می دانند.سازمان دهی بلوکها مشکلات پوشایی سکتورها و پراکندگی را ندارد.

اسلاید 36: زمان دستیابی به دیسک دستیابی به دیسک را می توان به سه عمل فیزیکی متمایز تقسیم کرد:زمان پیگردتاخیر چرخشیزمان انتقال

اسلاید 37: زمان پیگردتاخیر چرخشی

اسلاید 38: زمان پیگردزمان لازم برای انتقال بازوی دستیابی به سیلندر مناسب را زمان پیگرد می گویند

اسلاید 39: تاخیر چرخشیزمان لازم برای چرخش دیسک تا سکتور مورد نظر زیر هد خواندن و نوشتن قرار گیرد.

اسلاید 40: زمان انتقال زمان انتقال از فرمول زیر بدست می آید:زمان انتقال=(تعداد بایت های انتقال یافته/تعداد بایت های روی شیار)*زمان چرخش

اسلاید 41: تنگنای دیسک راههای مقابله با تنگنای دیسک:چند بر نامه ای (multiprogramming)نوار بندی (striping)موازی گرایی(parallelism)

اسلاید 42: سازمان دهی داده ها در نوار هاچون دستیابی به نوار ها به صورت ترتیبی است برای تشخیص موقعیت داده ها نیازی به آدرس نیست

اسلاید 43: مقايسه اي از برخي سيستمهاي نواري

اسلاید 44: نوار 7شیاره(A) 9شیاره(B)

اسلاید 45: بيت توازن بيت توازن بخشی از داده ها نيست. بلکه براي بررسي اعتبار داده ها به کار مي رود. اگر از توازن فرد استفاده شود اين بيت در کادرهاي فرد برابر 1 قرار داده مي شود. توازن روج نيز به همین صورت عمل مي کند. ولي در نوارها به ندرت از آن استفاده مي شود.

اسلاید 46: در نوار دو نوع بيت توازن وجود دارد: بيت پاريتي عرضي يا کاراکتريبيت پاريتي طوليبيت پاريتي عرضي براي هرکاراکتر و بيت پاريتي طولي، براي تعدادي کاراکتر ايجاد مي شود.

اسلاید 47: نوار گردان ها اختلاف کارایی در میان نوار گردان ها را بر حسب سه کمیت می توان سنجید:تراکم نوارسرعت نواراندازه شکاف بین بلاک ها

اسلاید 48: براورد طول نوار مورد نیاز طول فیزیکی یک بلوک از داده ها=bطول شکاف بین بلا ک ها=gتعداد بلاک های داده ها=n

اسلاید 49: فصای لازم برای نگهداری فایل :sS=n*(b+g)

اسلاید 50: اندازه بلوک / تراکم نوار=bطول بلوک=b

اسلاید 51: تراکم ضبط موثر: مقدار داده های واقعی را که به ازای هر اینچ از نوار می توان ذخیره کرد:تراکم ضبط موثر=تعداد بایتها در هر بلوک/تعداد اینچهای مورد نیاز برای هر بلوک

اسلاید 52: برآورد زمان انتقال داده هاعوامل موثر در سرعت انتقال داده ها:اندازه شکاف های بین بلاکیاندازه بلاک های دادهسرعت اسمی =تراکم نوار*سرعت نوار

اسلاید 53: مقایسه دیسک و نوارنوار برای پردازش ترتیبی و دیسک برای پردازش تصادفی است.نوار ها به یک فرایند اختصاص دارند در حالی که دیسک ها معمولا چند فرایند را سرویس دهی می کنند.نوار ها ارزانتر از دیسک ها هستند.سرعت پردازش دیسک ها بالاتر است.

اسلاید 54: CD_ROMنقطه قوت:ظرفیت ذخیره سازی بالا-بهای کم و دوام زیادنقطه ضعف:جستجو در آن بسیار کند است

اسلاید 55: کارایی در جستجودر واقع ضعف اصلی CD_ROM در دستیابی مستقیم است زیرا بسیار زمان بر است

اسلاید 56: سرعت انتقال داده هاسرعت انتقال داده ها بالا است چون نحوه ذخیره سازی به صورت بلاکی است.

اسلاید 57: ظرفیت ذخیره سازیCD_ROM بیش از600 مگا بایت داده را نگهداری می کند , پس ظرفیت ذخیره سازی آن بالا است.

اسلاید 58: دستیابی فقط خواندنی CD_ROM یک رسانه انتشاراتی است و پس از نوشتن محتویات آن قابل تغییر نیست.

اسلاید 59: تکنیک CVA دربرابر CAV

اسلاید 60: نوشتن و خواندن نا متقارنبه این معنی که ما فقط یک بار روی آن می نویسیم ولی هزاران بار آن را می خوانیم.

اسلاید 61: DVD(Digital versatile Disk ) در سال 1997 چند شرکت بزرگ تجهيزات الکترونيکي سازماني بنام DVD – Forum تاسيس کردند که هدفش توليد استاندارد جديد براي CD بود که پس از کشمکشهاي زياد (Digital video pisk) DVD با 8 نوع متفاوت ساخته شدند.در ابتدا DVD ها فقط براي ويدئوها طراحي شدند. بنابراين تحت نام (Digital video Disk) معرفي شدند.

اسلاید 62: اولين تفاوت DVD ها با CD ها بخاطر ظرفيت بالاي DVD هاست بطور مثال در حال حاضر ظرفيت بعضي DVD ها 20 برابر CDهاست. که يک عامل مهم آن دو لايه بودن DVD است بطوريکه يک طرف ديسک دو لايه مي تواند شامل دو لايه داده باشد در حين خواندن ابتدا لايه اوّل و سپس لايه دوم خوانده مي شود. البته تشخيص DVD ها دو لايه از DVDهاي تک لايه آسان است چون DVD دو لايه نقره اي و DVD تک لايه طلايي رنگ است.

اسلاید 63: انواع DVD از نظر ظرفيتDVD ها بر اساس ظرفيت در هشت فرمت مختلف(18- DVD and 10- DVD و 9- DVD و 5- DVD و 4- DVD و 3- DVD و 2- DVD و 1- DVD) که هر شماره مقدار تقريبي هر ظرفيت DVD به گيگابايت را نشان مي دهد وجود دارند.

اسلاید 64: دوتکنو لوژی لیزری برای dvdها

اسلاید 65: کاربرد DVDها متنوع است: video- DVD که براي نمايش فيلم Data- DVD براي کاربردهاي نرم افزاري Audio- DVD براي گوش کردن موسيقي ها بکار مي روند.Duta - DVD همان CD – ROM با ظرفيت بالا مي باشد و مانند CDهاي معمولي استفاده مي شود اما باراندمان بالاتر، video- DVD ها بسيار رايج تر از Data- DVDهاهستند و در مقايسه با VHSها آينده ي پربارتري دارند.

اسلاید 66: آشنايي با بافر و بافرينگ بافر ناحيه اي است واسط در عمليات ورودي و خروجي و در اين ناحيه اقلاًّ يک رکورد در حالت فايل بلاک بندي شده با يک بلاک در حالت بلاک بندي شده جاي داده مي شود و اساساً براي ايجاد هماهنگي بين عمليات پردازنده ورودي/خروجي و واحد پردازش مرکزي و در شرايطي سريع اين عمليات به کار مي رود. در سيستم فايل، بافر معمولاً از منطقه اي از حافظه اصلي به برنامه فايل پرداز تخصيص داده مي شود که به آن منطقه بافرها مي گويند.

اسلاید 67: نحوه ايجاد بافرها خود برنامه ساز بافر را ايجاد مي کند: با ايجاد ناحيه اي در حافظهبا اجراي يک ماکرو، که از سيستم عامل درخواست ايجاد بافر مي کند.خود سيستم عامل وقتي که فايل باز مي شود. اقدام به ايجاد بافرما مي کند و پس از بسته شدن فايل بافرها را باز پس مي گيرد.

اسلاید 68: بافر دهی چند گانهبه این معنی که CPU می تواند در حین ارسال یک بافر به دیسک , بافر دیگری را پر کند.

اسلاید 69: حالت تعیین محل در بافر دهیبافر مستقیما بین داده ها و حافظه باشد.بافر های سیستم همه بافر ها را کنترل کنداما اشاره گری برای محل بافر ها در اختیار برنامه باشد.

اسلاید 70:

اسلاید 71: پراکنش ورودیبا پراکنش ورودی با یکبار خواندن , نه یک بافر , بلکه مجموعه ای از بافر هایی که داده های یک بلوک باید در آن پخش شود شناسایی می شود.

اسلاید 72: تمر کز خروجیچند بافر را می توان گرد هم آورد و یکباره بر روی همه آنها نوشت.بدین ترتیب لازم نیست آنها را در یک بافر خروجی کپی کرد.

اسلاید 73: فصل چهارممفاهیم اساسی ساختار فایل

اسلاید 74: سازمان دهی فیلد ها و رکورد هاواحد اصلی داده ها فیلد است.آرایه مجموعه ای از فیلد های مثل هم است.رکورد مجموعه ای از فیلد های متفاوت است.رکوردی که در حافظه نگهداری می شود را یک شی گویندفیلد های رکورد را اعضای آن می نامند.

اسلاید 75: ساختار های فیلدقرار دادن فیلدها در طول هایی قابل پیش بینیشروع کردن هر فیلدی با نشانگر طول فیلدقرار دادن یک فاصل در انتهای هر فیلد برای جدا کردن آن از فیلد بعدیاستفاده از یک عبارت کلیدی برای شناسایی هر فیلد و محتویات آن

اسلاید 76: روش 1: ثابت کردن طول هر فیلدمزیت این روش در این است که با محاسباتی ساده می توان داده ها را از فیلد های اولیه باز یابی کردعیب این روش این است که افزودن فضاهای خالی مورد نیاز برای رساندن فیلد ها به طولی ثابت باعث می شود فایل ها بسیار بزر گتر شوند.

اسلاید 77: روش2: قرار دادن نشانگر طول فیلد در ابتدای هر فیلداگر فیلد ها بیش از حد طولانی نباشند (کمتر از 256بایت) می توان طول آنها را تنها با یک بایت در آغاز هر فیلد نگهداری کرد.این فیلدها را مبتنی بر طول می نامند.

اسلاید 78: روش 3 : جدا کردن فیلد ها با فاصل در این روش کافی است یک کاراکتر خاص یا ترتیبی از کاراکتر ها را که در فیلد ظاهر نمی شود انتخاب کنیم و آن فاصل راپس از نوشتن هر فیلد در فایل وارد کنیم. در بسیاری از موارد از کاراکتر فضای خالی استفاده می شود.

اسلاید 79: روش 4 : استفاده از عبارت کلیدی برای شناسایی فیلد هااین روش دارای مزیتی است که بقیه ندارند و نخستین ساختاری است که در آن فیلد اطلا عاتی در باره خودش فراهم می آورد.اما عیب این روش فضای زیادی است که تلف می کند.

اسلاید 80: ساختار های رکوردرکورد مجموعه ای از فیلد ها است.مجموعه ای از رکورد ها فایل را تشکیل می دهند.برای مراجعه به داده های مقیم در حافظه از کلمه شی و برای مراجعه به داده های مقیم در فایل از کلمه رکورد استفاده می شود.

اسلاید 81: روش های سازمان دهی رکورد های فایلقابل پیش بینی کردن طول رکورد ها بر حسب بایت.قابل پیش بینی کردن طول رکورد ها بر حسب فیلد ها.شروع هر رکورد با یک نشانگر طول که تعداد بایتهای رکورد را نشان می دهد.استفاده از فایل دیگری برای نگهداری آدرس شروع هر رکورد.قرار دادن فاصل در انتهای هر رکورد برای جدا کردن آن از رکورد بعدی.

اسلاید 82: روش 1 : قابل پیش بینی کردن طول رکورد ها بر حسب بایتفایلی با طول ثابت , فایلی است که در آن تعداد بایتهای همه رکورد ها یکسان است.رکورد های با طول ثابت , غالبا به عنوان محلی برای نگهداری تعداد متغیری از فیلد ها , با طول متغیر به کار می روند.

اسلاید 83: روش 2 : قابل پیش بینی کردن طول رکورد ها بر حسب فیلد ها. در این روش به جای آنکه مشخص کنیم هر رکورد در فایل حاوی تعداد ثابتی از بایتهاست , می توان مشخص کرد که حاوی تعداد ثابتی از فیلد هاست.

اسلاید 84: روش 3: شروع هر رکورد با یک نشانگر طول که تعداد بایتهای رکورد را نشان می دهد. در این روش فیلدی در ابتدای هر رکورد در نظر گرفته می شود و طول رکورد در آنجا ذخیره می گردد.از این روش معمولا برای کار با رکورد هایی با طول متغییر استفاده می شود.

اسلاید 85: روش 4 : استفاده از فایل دیگری برای نگهداری آدرس شروع هر رکورد. برای نگهداری آفست بایت مربوط به رکورد های موجود در فایل , می توان از اندیس استفاده کرد.با آفست بایت می توان ابتدای هر رکورد را یافت و طول رکورد را محاسبه کرد

اسلاید 86: روش 5 : قرار دادن فاصل در انتهای هر رکورد برای جدا کردن آن از رکورد بعدی. این حالت در سطح رکورد ها , دقیقا مشابه راه حلی است که برای متمایز ساختن فیلد ها در برنامه ها به کار می رود.

اسلاید 87: سیستم raid سه سطحی درمقابل raid یک سطحی

اسلاید 88: فصل پنجممدیریت فایل هایی از رکورد ها

اسلاید 89: کلید های رکورد برای جستجو بین رکورد ها باید یک شکل استاندارد برای کلید ها تعریف کنیم . این شکل استاندارد را شکل کانونیک کلید می نامند.

اسلاید 90: جستجوی ترتیبی در این روش فایل رکورد به رکورد خوانده می شود تا رکوردی با یک کلید خاص پیدا شود.

اسلاید 91: ارزیابی جستجوی ترتیبیبه طور کلی کار مورد نیاز برای جستجوی ترتیبی در فایلی باN رکورد با n متناسب است.حداکثر n مقایسه و به طور میانگین n/2 مقایسه مورد نیاز است.

اسلاید 92: بهبود کارایی جستجوی ترتیبی با بلوک بندی رکورد هادر این روش با خواندن بلوکی از چند رکورد به یکباره و سپس پردازش آن بلوک از رکورد ها در حافظه , کارایی جستجو را بهبود می بخشیم.

اسلاید 93: گرچه بلوک بندی می تواند منجر به بهبود چشمگیر کارایی شود , مرتبه عملکرد جستجوی ترتیبی را تغییر نمی دهد.زمان جستجو هنوز o(N) است و با اندازه فایل نسبت مستقیم دارد.

اسلاید 94: بلوک سازی , اختلاف میان سرعت دستیابی در حافظه و زمان دستیابی در حافظه ثانویه را نشان می دهد.بلوک سازی تعداد مقایسه هایی را که باید در حافظه انجام شود تغییر نمی دهدو احتمالا مقدار داده های انتقال یلفته میان حافظه و دیسک را افزایش می دهد.

اسلاید 95: با بلوک سازی در زمان صرفه جویی می شود زیرا مقدار جستجو کاهش می یابد.بدین ترتیب تفاضل میان زمان جستجو و زمان عملیات دیگر , نظیر انتقال داده ها با دستیابی به حافظه , نیروی محرکه طراحی ساختار فایل است.

اسلاید 96: ابزار های یونیکس برای پردازش ترتیبیمتداول ترین ساختار فایل که در یونیکس وجود دارد یک فایل اسکی با کاراکتر خط جدید به عنوان فاصل رکورد ها و در صورت امکان , فضای خالی به عنوان فاصل فیلد هاست.

اسلاید 97: دستیابی مستقیمهنگامی که بتوانیم مستقیما به ابتدای یک رکورد برویم و آن را به حافظه وارد کنیم به آن رکورد دستیابی مستقیم داریم.

اسلاید 98: رکورد های سرایندهر فایل دارای یک رکورد سرایند است که حاوی سه مقدار است:اندازه سرایندتعداد رکورد هااندازه هر رکورد

اسلاید 99: دستیابی به فایل و سازمان دهی فایلرکورد های طول متغییر و رکورد های طول ثابت مربوط به بحث سازمان دهی فایل و دستیابی مستقیم و دستیابی ترتیبی مربوط به مبحث دستیابی به فایل می باشد.تعامل میان ساز مان دهی فایل و دستیابی به فایل , بسیار سودمند است.

اسلاید 100: داده های انتزاعی برای دستیابی به فایلاین مفهوم که نیازی نیست داده ها را به صورتی که در یک رسانه خاص ظاهر شده اند در نظر بگیریم , در عملیات مدل دادهای انتزاعی مستتر است.

اسلاید 101: سرآیند ها و فایل های خود توصیف گربه فایلی که در رکورد سرایند آن اطلاعات بیشتری در باره ساختار فایل وجود داشته باشد فایل خود توصیف گر می گویند.

اسلاید 102: اطلاعاتی که میتوان در سرآیند نوشتنامی برای هر فیلدطول هر فیلدتعداد فیلد های هر رکورد

اسلاید 103: عوامل موثر بر قابلیت حملاختلاف میان سیستم های عاملاختلاف میان زبان هااختلاف در معماری ماشین

اسلاید 104: توافق بر سر رمز گذاری دودوییIEEE مشخصات فرمت استاندارد را برای اعداد ممیز شناور 32 بیتی , 64 بیتی و 128 بیتی و برای اعداد صحیح 8 بیتی , 16 بیتی و 32 بیتی وضع کرده است.

اسلاید 105: یونیکس و قابلیت حملیونیکس ابزاری به نام dd فراهم آورده است.گرچه dd اساسا برای کپی کردن داده ها از روی سیستم های یونیکس بر روی نوار و بالعکس در نظر گرفته شده است, می توان آن را برای تبدیل از منبع فیزیکی دیگری به کار برد.

اسلاید 106: مواردی که ابزار dd در اختیار قرار می دهد:تبدیل از یک اندازه بلوک به دیگریتبدیل رکورد های طول ثابت به طول متغییر و بالعکستبدیل اسکی به ابسدیک و بالعکستبدیل همه کاراکتر ها به حروف کوچک یا حروف بزرگتبادل هر جفت دلخواه از بایتها

اسلاید 107: فصل ششمسازمان دهی فایل ها برای کارایی

اسلاید 108: دلایل فشرده سازی فایل هافایل های کوچکتر نیاز به حافظه کمتری دارند که باعث صرفه جویی می شود.سریعتر انتقال داده می شوند که زمان دسترسی را کوتاهتر می کند یا به جای آن می توان با همان زمان دسترسی از پهنای باند کمتر و ارزانتر استفاده کرد.به صورت ترتیبی سریعتر قابل پردازش هستند.

اسلاید 109: تکنیک های فشرده سازیاستفاده از یک نماد گذاری جدیدحذف دنباله های تکراریتخصیص کد های با طول متغییر

اسلاید 110: استفاده از یک نماد گذاری جدیدمعایب فشرده سازی با رمزبا استفاده از رمز گذاری دودویی فایل به وسیله اشخاص قابل خواندن نیست.زمانی که بخواهیم نامی را به فایلمان اضافه کنیم زمانی را برای رمز گذاری از دست خواهیم داد.باید ماژول های رمز گذاری و رمز گشایی را در تمام نرم افزار هایی که فایل را

اسلاید 111: حذف دنباله های تکراریبر خلاف فشرده سازی نمادی رمز گزاری طول رانش مقدار معینی از صرفه جویی در فضا را تضمین نمی کند.

اسلاید 112: تخصیص کد های با طول متغییرکد های با طول متغییر عموما بر اساس این اصل به وجود آمده اند که بعضی مقادیر بیش از بقیه به کار می روند بنابراین کد این مقادیر باید فضای کمتری اشغال کند.کد های با طول متغییر فرم دیگری از کاهش زواید است.

اسلاید 113: روش های فشرده سازی بر گشت ناپذیرنوع دیگری از فشرده سازی به نام فشرده سازی بر گشت ناپذیر بر اساس این اصل عمل می کند که مقداری از اطلا عات را می توان نادیده گرفت.

اسلاید 114: فشرده سازی در یونیکسهم یونیکس برکلی و هم system v روال های فشرده سازی فراهم می کنند که بسیار مورد استفاده قرار می گیرد .system v روالهایی دارد به نام packو unpack که از کد های هافمن به صورت بایت به بایت استفاده می کنند.

اسلاید 115: باز یابی فضای داخل فایلهابا داده های اضافی چه باید کرد؟آنها را در انتهای فایل قرار داد و اشاره گری ایجاد کرد تا از مکان اولیه رکورد به بقیه آن اشاره کند.کل رکورد را در انتهای فایل دوباره نوشت.

اسلاید 116: انواع تغییرات در فایلاضافه کردن رکوردبهنگام سازی رکوردحذف رکورد

اسلاید 117: حذف رکورد و متراکم کردن فایلهر راهبرد حذف رکورد باید راهی را فراهم کند تا رکورد های حذف شده شناخته شوند.یک روش ساده قرار دادن یک علامت خاص در هر رکورد حذف شده است.

اسلاید 118: حذف رکورد های با طول ثابت برای بازیابی پویای فضامتراکم کردن فایل آسان ترین و رایج ترین روش های بازیابی فضا است.برای حذف رکورد ها و استفاده دوباره از فضای آزاد شده باید بتوانیم دو مسئله را تضمین کنیمرکورد های حذف شده به طور خاصی علامت گذاری شوند.بتوانیم محلی را که توسط رکورد های حذف شده اشغال شده بود را پیدا کنیم.

اسلاید 119: مواردی که برای باز یابی سریع فضا به آنها نیاز داریم:راهی که بلا فاصله بدانیم حفره های خالی در فایل وجود دارد یا نه؟راهی که اگر چنین حفرهای وجود دارد سریع به آن پرش کنیم.

اسلاید 120: راه حل:استفاده از لیست های پیوند برای پیوند دادن تمام رکورد ها هر دو نیاز فوق را بر آورده می کند.لیست پیوندی ساختمان داده ای است که هر گره آن به گره بعدی اشاره می کند.

اسلاید 121: پشته هاآ سان ترین راه برای کار کردن با لیست استفاده از آن به صورت پشته است.پشته لیستی است که در آن اضافه و حذف گرهها از یک انتهای لیست انجام می شود.

اسلاید 122: برای حل دو مسئله مر بوط به دسترسی سریع به فضای قابل بازیابی رکورد های حذف شده نیاز است که:بدانیم که آیا حفره های خالی در فایل وجود دارد.اگر چنین حفره ای وجود دارد مستقیما به آن پرش کنیم.

اسلاید 123: برای باز یابی رکورد ها از طریق لیست پیوندی به موارد زیر نیاز داریم:راهی برای پیوند دادن رکورد های حذف شده و تبدیل آنها به یک لیست.الگوریتمی برای اضافه کردن رکورد های حذف شده به لیست.الگوریتمی برای پیدا کردن و خارج کردن یک رکورد از لیست, هنگامی که می خواهیم از آن رکورد استفاده کنیم.

اسلاید 124: پراکندگی حافظهفضای تلف شده در داخل یک رکورد پراکندگی داخلی نامیده می شود.اگر با رکورد های طول ثابت کار کنیم برای به حداقل رساندن پراکندگی داخلی باید حداقل طول رکورد را انتخاب کنیم.

اسلاید 125: راهبرد های انتخاب جااولین جای مناسب(first fit)مناسب ترین جا(best fit)نامناسب ترین جا(worst fit)

اسلاید 126: اشکال روش best fit زمان پردازش اضافیوجود پراکندگی خارجی

اسلاید 127: اشکال روش worst fit در این روش پراکندگی داخلی زیاد است.

اسلاید 128: جستجوی دو دویی در برابر جستجوی ترتیبیجستجوی دودو یی فایلی با n رکورد حد اکثر به [log n]+1 مقایسه نیاز دارد .اما جستجوی ترتیبی فایلی مشابه حداکثر به n مقایسه و به طور متوسط به n/2 مقایسه نیاز دارد

اسلاید 129: محدودیت های جستجوی دودویی و مرتب سازی داخلیجستجوی دودویی نیاز به بیش از یک یا دو دسترسی به دیسک دارد.نگهداری یک فایل به صورت مرتب شده خیلی گران تمام می شود.مرتب سازی داخلی تنها در مورد فایل های کوچک عملی است.

اسلاید 130: مرتب سازی کلیدی مرتب سازی کلیدی که گاهی به آن مرتب سازی با بر چسب می گویند بر این ایده استوار است که وقتی فایلی را در حافظه مرتب می کنیم , تنها چیزی که به آن نیاز داریم کلید رکورد ها است.

اسلاید 131: فصل هفتمشاخص گذاری

اسلاید 132: شاخص چیست؟منظور از شاخص مجموعه اي از عناصر شاخص است كه به صورت جفت هاي(x , a ) از داده هايي با طول ثابت است كه به طور فيزيكي كنار هم قرار دارند . x نشانگر كليد و a نشانگر اطلاعات همراه با كليد است .

اسلاید 133: فرض مي كنيم خود شاخص انقدر بزرگ است كه تنها بخش كوچكي از آن را مي توان در يك لحظه در حافظه اصلي نگه داشت . بنا بر اين شاخص بايد در يك حافظه جانبي ذخيره شود . نوع حافظه جانبي دستگاه هايي با دستيابي شبه تصادفي است كه زمان دستيابي يا انتظار آنها نسبتا طولاني است .

اسلاید 134: هدف , پيدا كردن روش كلي براي ذخيره و بازيابي داده ها در سيستم هاي فايل بزرگ بود كه امكان دسترسي با حداقل زمان را فراهم سازد . مك كرايت در سال 1972 اولين مقاله خود را در رابطه با درخت Bمنتشر كرد . پس از آن درخت B به قدري گسترش يافت كه كومر اينگونه نوشت : « درخت B , به طور غير رسمي ساختار استانداردي براي شاخص بندي در بانكهاي اطلاعاتي به شمار مي رود» .

اسلاید 135: شاخص چند سطحی

اسلاید 136: مزیت شاخص هابدون دستکاری محتویات فایل ,به فایل نظم و تر تیب می بخشند.

اسلاید 137: لازمه استفاده از الگوريتم جستجوي دودويي اين است كه بلاك هاي داده اي به طور پيوسته ذخيره شده باشند . اگر بلاك ها به طور ناپيوسته ذخيره و به هم پيوند شده باشند , يافتن آدرس بلاك مياني نا ممكن است .

اسلاید 138: با استفاده از تكنيكهاي ابتدايي ساختمان داده ها به آساني مي توانيم گره هايي را درست كنيم كه شامل فيلد هاي پيوندي چپ و راست باشند و به اين ترتيب درخت جستجوي دودويي را به صورت يك ساختار پيوندي ايجاد كنيم .

اسلاید 139: شكل زير را در نظر بگيريد :

اسلاید 140: مشكل درخت جستجوي دودويي اين است كه براي شاخص بندي روي ديسك سرعت لازم را ندارد . اما مشكل مهم ديگر درخت جستجوي دودويي , وجود نداشتن يك راهبرد موثر براي موازينه كردن درخت است براي حل اين مشكلات درختهاي AVL و در ختهاي دوديي صفحه صفحه به ميان آمدند

اسلاید 141: کاتالوگ کارتی چیست؟مجموعه ای از سه شاخص است که هر کدام از یک فیلد کلید متفاوت استفاده می کنند وهمه آنها از یک شماره کاتالوگ یکسان به عنوان فیلد آدرس بهره می گیرند.

اسلاید 142: مقایسه سرعت دسترسیشاخص باعث می شود تا رکورد ها را به وسیله کلید آنها با سرعت زیادی ÷یدا کنیم .سرعت این کار در مقایسه با حالتی که جستجوی دودویی در یک فایل مرتب موجود در حافظه انجام می شود بیشتر است.

اسلاید 143: عملیات مورد نیاز برای نگهداری فایل شاخص بندی شدهایجاد فایل داده ها و شاخص خالی اولیهباز کردن فایل شاخص در حافظه ,قبل از به کار گیری آننوشتن فایل شاخص بر روی دیسک , پس از به کار گیری آنافزودن رکورد هایی به فایل داده هاحذف رکورد ها از فایل داده هابهنگام کردن رکورد ها در فایل داده هابهنگام کردن شاخص برای انعکاس تغییرات به عمل آمده در فایل داده ها

اسلاید 144: ایجاد فایل داده ها و شاخص خالی اولیهدو فایل باید ایجاد شود:فایل داده ها برای نگهداری اشیائ داده ای فایل شاخص برای نگهداری کلید اولیه

اسلاید 145: باز کردن فایل شاخص در حافظه ,قبل از به کار گیری آن بازیابی و ذخیره اشیاء توسط کلاس io buffer انجام می شود.

اسلاید 146: نوشتن فایل شاخص بر روی دیسک , پس از به کار گیری آنیکی از خطرات مربوط به خواندن شاخص و نوشتن آن در پایان برنامه آن است که اگر برنامه متوقف شود کپی شاخص که بر روی دیسک است اعتبار ندارد.

اسلاید 147: برنامه باید حداقل دو مکانیسم زیر را برای محافظت از خطا داشته باشدباید مکانیسمی باشد که به برنامه اطلاع دهد که شاخص در چه زمانی از رده خارج استاگر برنامه تشخیص دهد که شاخص از رده خارج است باید به روالی دستیابی داشته باشد که شاخص را از فایل داده ها بازسازی کند.

اسلاید 148: افزودن رکورد هایی به فایل داده ها برای افزودن رکورد ها باید همه ورودی هایی را که کلید آنها پس از کلید ورودی جدید است , جابجا کنیم تا پس از این ورودی قرار گیرند.

اسلاید 149: حذف رکورد ها از فایل داده هابر خلاف یک فایل داده ای مرتب برای حفظ ترتیب رکورد ها نیاز به جابجایی آنها نیست.به وسیله کلید بدون اختلال در جای رکورد ها می توانیم با سرعت زیادی به رکورد ها دسترسی پیدا کنیم.

اسلاید 150: بهنگام کردن رکورد ها در فایل داده هابهنگام سازی به دو صورت انجام می شود:بهنگام سازی تعداد فیلد و کلید را تغییر می دهدبهنگام سازی بر فیلد کلید تا ثیر نمی گذارد.

اسلاید 151: بهینه سازیشیوه استاندارد برای انجام این کار افزودن نشانگری به شی شاخص استتا نشان دهد که چه زمانی تغییر کرده است.هنگامی که رکورد به حاففظه منتقل می شود به این نشانگر ارزش false داده می شود.و هرگاه رکورد شاخص توسط متد های remove و insert تغغییر داده شد به آن ارزش true داده می شود.

اسلاید 152: شاخص های بزرگاگر شاخص بیش از حد بزرگ باشد در آن صورت دستیابی به شاخص و دستکاری آن باید در حافظه ثانویه صورت گیرد.

اسلاید 153: معایب دستیابی به شاخص روی دیسکجستجوی دودویی شاخص به جای آنکه با سرعت حافظه صورت پذیرد نیاز به چندین پیگرد دارد.ترتیب مجدد شاخص که از حذف یا افزودن رکورد ناشی می شود نیاز به جابجا کردن یا مرتب سازی رکورد ها در حافظه ثانویه دارد که این کار بسیار گرانتر از اجرای این عملیات در حافظه است.

اسلاید 154: هرگاه شاخص در حافظه جا نشود باید از موارد زیر استفاده کرد:در صورتی که سرعت دستیابی در اولویت قرار داشته باشد از درهم سازی استفاده شوددر صورتی که به هر دو نوع دستیابی کلیدی و ترتیبی نیاز باشد از یک شاخص چند سطحی با ساختار درختی نظیر درخت B استفاده می شود.

اسلاید 155: نکته 1:شاخص ساده استفاده از جستجوی دودویی را برای دستیابی کلیدی به یک رکورد در فایلی که طول رکورد های آن متغییر است امکان پذیر می سازد.

اسلاید 156: نکته 2: اگر ورودی های شاخص بسیار کوچکتر از رکورد های فایل داده ها باشد مرتب سازی و نگهداری شاخص نسبت به مرتب سازی و نگهداری فایل داده ها زمان کمتری می برد.

اسلاید 157: نکته 3:اگر در فایل داده ها رکورد هایی وجود دارند که در جای خود مستقر هستند با استفاده از شاخص می توان ترتیب کلید ها را بدون جابجایی رکورد های داده ها عوض کرد.

اسلاید 158: افزودن رکوردهنگامی که شاخص ثانویه ای موجود باشد , افزودن یک رکورد به فایل به معنای افزودن یک ورودی شاخص ثانویه است.

اسلاید 159: نکتهاختلاف مهم شاخص اولیه با ثانویه آن است که شاخص ثانویه می تواند حاوی کلید های دوگانه باشد.

اسلاید 160: حذف رکورد هاحذف یک رکورد به معنای حذف تمامی آدرس های آن رکورد در سیستم فایل است.

اسلاید 161: بهنگام سازی رکورد هابهنگام سازی فایل داده ها فقط هنگامی شاخص ثانویه را تحت تا ثیر قرار می دهد که کلید اولیه یا ثانویه تغییر یابند

اسلاید 162: در بهنگام سازی سه وضعیت پیش می آید:بهنگام سازی با عث تغییر کلید ثانویه می شودبهنگام سازی باعث تغییر کلید اولیه می شودبهنگام سازی محدود به فیلد های دیگر

اسلاید 163: ساختار های شاخص ثانویه دو مشکل دارندهر بار که رکورد جدیدی به فایل افزوده می شود باید فایل شاخص را دوباره مرتب کنیم.اگر کلید های ثانویه وجود داشته باشد فیلد کلید ثانویه برای هر ورودی تکرار می شود.

اسلاید 164: انقیاد منظور از انقیاد این است که کلید در چه نقطه ای به آدرس فیزیکی رکورد مربوط به خود می پیوندد

اسلاید 165: در کل این فصل انقیاد کلید های اولیه به آدرس در زمان ایجاد شدن فایلها رخ می دهد.ولی کلید های ثانویه در زمان استفاده به آدرس خود پیوند می یابند.

اسلاید 166: نکتهعیب انقیاد مستقیم در فایل آن است که سازمان دهی دوباره فایل داده ها باید منجر به اصلاح همه فایل های شاخص انقیاد یافته شود.

اسلاید 167: انقیاد درون داده ها هنگامی بهترین نتیجه را می دهد که:فایل داده ها ایستا یا تقریبا ایستا باشد و نیاز کمی به حذف , اضافه یا بهنگام سازی داده ها داشته باشد.کارایی سریع طی بازیابی واقعی , از اولویت بالایی بر خوردار است.

اسلاید 168: فصل هشتمپردازش کمک ترتیبی و مرتب سازی فایل های بزرگ

اسلاید 169: عملیاتعملیات کمک ترتیبی شامل پردازش هماهنگ دو یا چند لیست ترتیبی برای ایجاد یک لیست خروجی است.روال زير تطابق بين دو ليست را نشان مي‌دهد.

اسلاید 170: In +match (char * List1Name, char * List2 name, char * outpute listName){Int More items;Initialize List (1, List Name) Initialize List (2, List Name)Initialize output (Output List Name)More items; = next ItemINList (1)86 Next ItemInList (2)

اسلاید 171: While (More items){If (Item (1) < Item (2))More items= next Item List (1);Else If Item (1) = Item (2){Process item (1) ; // Match foundMore items= next ItemInList;}ElseMore items = next ItemInList(2)}finishup();Return 1;}

اسلاید 172: ترتیب روال همخوانیآماده سازی دستیابی به عضو بعدی لیست همزمان سازی کنترل شرایط پایان فایلتشخیص خطا ها

اسلاید 173: الگوریتمی برای ادغام k طرفهتصمیم گیری در این باره که کدامیک از دو عضو ورودی دارای مقدار کمینه است , قرار دادن آن عضو در خروجی و سپس حرکت به طرف جلو

اسلاید 174: الگوریتمی که می توان برای ادغام k طرفه در نظر گرفت بدینگونه است : Int minitem = minindex (item , k )Process item ( minitem),For (i=0 ; i<k ; i++ )If ( item (minitem) = = item(i) More items[i] = nextiteminlist(i);

اسلاید 175: مراحل مرتب سازی در حافظهخواندن فایل از روی دیسک به حافظهمرتب سازی رکورد ها با استفاده از یک روال مرتب سازی استاندارد نوشتن دوباره فایل روی دیسک

اسلاید 176: هرم درختی دودویی با ویژگی های زیر است:هر گره دارای کلیدی است که آن کلید بزرگتر یا مساوی کلید واقع در گره پدرش است.یک درخت دودویی کامل است.بخاطر ویژگی های 1و2 در نگهداری درخت می توان آرایه ای اختصاص داد که در آن گره ریشه اندیس 1 و اندیس های فرزندان چپ و راست گره i به ترتیب برابر با2i,2i+1 باشند .

اسلاید 177: درخت دودويي صفحه اي

اسلاید 178: بازیابی ترتیبی کلید ها به صورت زیر انجام می شودتعیین مقدار کلید موجود در اولین موقعیت هرمانتقال بزرگترین مقدار هرم به اواین محل آن و کم کردن یک واحد از تعداد عناصرترتیب دوباره هرم

اسلاید 179: برنامه حذفchar * Heap::Remove ( ) }// remove the smallest element , reorder the Heap// put the smallest value into val for use in return char * val = HeapArray [1]; // put largest value into root HeapArray [1] = HeapArray [NumElements]; // decrease the number of elements NumElements - - ; // reorder the heap by exchanging and moving down int k = 1 ; //node of heap that contains the largest value int newK ; // node to exchange with largest value while (2 * K <= NumElements ) //K has at least one child { // set nemK to the index of smallest child of K if Compare (2 * k , 2 * K + 1) < 0 ) newK = 2 * K; else newK = 2 * K + 1 ; if (Compar (K,newK) < 0) break ; // in order Exchange (K,newK ); // K and newK out of order K = NEWk ; // continue down the tree } return val ; }

اسلاید 180: فايل با ساختار درخت K-D اين فايل گونه اي از ساختار درخت جستجوي دودويي است . اما تفاوت فايل با ساختار درخت K-D با فايل با ساختار درخت جستجوي دودويي دراين است كه فيلد كليد در سطوح مختلف يكسان نيست .به طوركلي ، تعداد درخت هاي K-D براي يك مجموعه از ركوردها مي تواند بيش از يك باشد .انتخاب يك درخت از درختهاي ممكن بستگي به نظمي دارد كه براساس آن مي خواهيم ركوردها را درج كنيم .

اسلاید 181: مثالي از درخت K-D

اسلاید 182: مرتب سازی کلیدی دو نارسایی دارد:هنگامی که کلید ها مرتب سازی می شوند باید زمان زیادی صرف این موارد شود ,پیگرد هر رکورد در رکورد های مرتب شده,خواندن هر رکورد به حافظه و سپس نوشتن آن روی فایل مرتب شده.در مرتب سازی کلیدی اندازه فایلی که قابل مرتب سازی است به تعداد جفت کلید/اشاره گری که در حافظه جا شود محدود می شود.

اسلاید 183: مراحل مرتب سازیخواندن همه رکورد ها به حافظه برای مرتب سازی و تشکیل رانش هانوشتن رانش های مرتب شده روی دیسک

اسلاید 184: مراحل ادغامخواندن رانش های مرتب شده به حافظه برای ادغامنوشتن فایل مرتب شده بر روی دیسک

اسلاید 185: راهکارهای کاهش زمانتخصیص سخت افزار بیشتر نظیر دیسک گردان و حافظهاجرای ادغام در بیش از یک مرحلهافزایش طول رانش های مرتب شده از لحاظ الگوریتمییافتن راههایی برای همپوشانی عملیات i/o

اسلاید 186: به کمک سخت افزارافزایش مقدار حافظهافزایش تعداد دیسک گردان هاافزایش تعداد کانال های i/o

اسلاید 187: ابزار هایی برای بهبود کارایی مرتب سازی خارجیبرای مرتب سازی درون حافظه ای از مرتب سازی هرمی در یک رانش استفاده می کنیماستفاده از حد اکثر حافظه ممکناگر تعداد رانش های اولیه بزرگ باشد از ادغام چند مرحله ای استفاده می کنیماستفاده از گزینش جایگزینی برای تشکیل رانش های اولیهاز بیش از یک دیسک گردان و کانال io استفاده کنیم

اسلاید 188: مراحل مرتب سازی روی نوارتقسیم فایل مرتب نشده به رانش های مرتب شدهادغام رانش ها به یک فایل مرتب شده

اسلاید 189: راهکارهای کاهش زمانهای تاخیر چرخشی و پیگردبا اجرای ادغام در بیش از یک مر حلهافزایش اندازه رانش های مرتب شده اولیه

اسلاید 190: تعداد رکوردها به ازای هر پیگرد برای تشکیل رانشها تعداد رکوردها به ازای هر پیگرد برای تشکیل رانشها اندازه رانشهای تشکیل یافتهتعداد رانشهای تشکیل شدهتعداد پیگردهای مورد نیاز برای تشکیل رانشمرتبه ادعام به کار رفتهتعداد کل پیگردهادقیقهساعتاندازه رانشهای تشکیل یافتهتعداد رانشهای تشکیل شدهتعداد پیگردهای مورد نیاز برای تشکیل رانشمرتبه ادعام به کار رفتهتعداد کل پیگردهادقیقهساعت800 مرتب سازی حافظه ای و سپس ادغام 800 جانبه000,100000,100800160080068160052گزینش جایگزینی و سپس ادغام 534 جانبی (رکوردها به ترتیب تصادفی)250001500005346400534521132361گزینش جایگزینی و سپس ادغام 200 جانبه (رکوردها تا حدی مرتب هستند)2500040000020064002002064003800

اسلاید 191: تعداد رکوردها به ازای هر پیگرد برای تشکیل رانشها تعداد رکوردها به ازای هر پیگرد برای تشکیل رانشها اندازه رانشهای تشکیل یافتهتعداد رانشهای تشکیل شدهالگوی ادغام مورد استفادهتعداد پیگردها در فازهای ادغامتعداد کل پیگردهادقیقهساعتاندازه رانشهای تشکیل یافتهتعداد رانشهای تشکیل شدهالگوی ادغام مورد استفادهتعداد پیگردها در فازهای ادغامتعداد کل پیگردهادقیقهساعت800 مرتب سازی حافظه ای000,100000,10080025 ادغام 32 جانبه و سپس یک ادغام 25 جانبه20000/25600127200240گزینش جایگزینی و سپس ادغام 534 جانبی (رکوردها به ترتیب تصادفی)2500015000053419 ادغام 28 جانبه و سپس یک ادغام 19 جانبه15162/22876124438230گزینش جایگزینی و سپس ادغام 200 جانبه (رکوردها تا حدی مرتب هستند)2500040000020020 ادغام10 جانبه و سپس یک ادغام 20 جانبه16000/8000110400200مقایسه ی زمان های دستیابی مورد نیاز برای مرتب سازی 80 میلیون رکورد با استفاده از مرتب سازی حافظه ای و گزینش جایگزینی و یک ادغام دو جانبه پس از هریک.

اسلاید 192: فصل نهمشاخص بندی چند سطحی و درختهای B

اسلاید 193: اهداف فصل توسعه ی درخت های B برای حل مسأله هایی که برای آن ها طراحی شده اند.نگاهی به سایر ساختارهای درختی که ممکن است در حافظه های جانبی مورد استفاده قرار گیرند، مثل درخت AVL صفحه بندی شده (paged).معرفی شاخص های چند رکوردی و چند سطحی و ارزیابی سرعت عمل جستجو.درک ویژگی های مهمی که توسط درخت های B پردازش می شوندو بررسی اهمیت آن ها در حافظه های جانبی.طراحی شیء گرای درخت های Bتعریف کلاس BTreeNode، نمایش گره های درخت های B در حافظه.تعریف کلاس BTree، نمایش کامل درخت های B و تمام اعمال آن ها.تشریح پیاده سازی اصول عملیات درخت های Bمعرفی بافردهی صفحه ای و درخت های B مجازی.توصیف الگوریتم های اصلی درخت B، مثل آن هایی که برای ساختن درخت B* و درخت B با رکوردهای طول متغیر به کار گرفته شده اند.

اسلاید 194: دستگاهها با دستیابی تصادفی واقعی:حافظه کر دستگاهها با دستیابی شبه تصادفی:دیسک های دارای هد ثابت و متحرک, طبله ها و سلول های داده ها

اسلاید 195: نکتهمشکل اصلی نگه داشتن شاخص در حافظه جانبی این است که دسترسی به حافظه جانبی کند است

اسلاید 196: مشکل قبل به دو مشکل تقسیم می شود:جستجو بر حسب شاخص باید سریع تراز جستجوی دودویی باشد.درج و حذف باید با سرعت جستجو کردن انجام شود.

اسلاید 197: راهکار مشکل اولاستفاده از درخت های دودویی صفحه ایدر درخت دودويي صفحه اي سعي مي كند با قرار دادن چندين گره دودويي در يك صفحه ديسك مشكل را حل كند . به اين ترتيب كه با يك دستيابي به ديسك بخش بزرگي از درخت را مي توان به دست آورد . ب شاخص هاي صفحه اي مي توان در بين تعداد زيادي كليد , با تعداد كمي دستيابي به ديسك كليدي را جستجو كنيم .

اسلاید 198: شكل زير نمونه اي از درخت دودويي صفحه اي را نشان مي دهد.

اسلاید 199: راهکار مشکل دوماستفاده از درخت موازنه شده

اسلاید 200: دو مزیت درختهای AVLبا تعیین کردن حداکثر تفاوت مجاز در ارتفاع هر دو زیر درخت این درخت ها حداقل کارایی را در جستجو تضمین می کنند.برای اینکه هنگام درج در درخت AVL ویژگی خود را حفظ کند مستلزم چهار نوع چرخش است.

اسلاید 201: تاریخچه درخت B داگلاس کومر، در مقاله ی تحقیقاتی عالی خود، تحت عنوان درخت B درهمه جا از رقابت میان صاحبان صنایع کامپیوتر و گروه های تحقیقاتی مستقل در اواخر دهه ی 1960 صحبت می کند. هدف، پیدا کردن روشی کلی برای ذخیره و بازیابی داده ها در فایل بزرگ بود، که امکان دسترسی سریع با حداقل زمان را فراهم کند. در میان رقبا، بایر و پ. مک کرایت بودند که برای شرکت بویینگ کار می کردند. در سال 1972 آن ها مقاله ای به نام سازمان دهی و نگهداری شاخص های مرتب شده ی بزرگ منتشر کردند که درخت B را به جهان معرفی کرد.

اسلاید 202: درخت Bهر گره درخت B یک رکورد شاخص است .هر کدام از این رکورد ها تعداد یکسانی از جفتهای کلید – آدرس دارند که مرتبه درخت نام دارد.

اسلاید 203: متد جستجو در درخت Bبه صورت تکراری عمل می کنند.در دو مر حله عمل می کنند : به صورت یک در میان روی کل صفحات.

اسلاید 204: مراحل درج کردنجستجو تا سطح برگ با استفاده از متد FINDLEAF قبل از تکرار.درج تشخیص سرریز و تقسیم کردن در مسیر رو به بالا.ایجاد یک ریشه جدید , در صورتی که ریشه فعلی تقسیم شده است.

اسلاید 205: خواص یک در خت B از مرتبه mهر صفحه حد اکثر m فرزند دارد.هر صفحه بجز ریشه ها و برگها حداقل [m/2]فرزند دارد.ریشه حد اقل دو فرزند دارد.تمام برگها در یک سطح قرار دارند.سطح برگها, یک شاخص کامل و مرتب شده از داده های مر بوط به درخت را ایجاد می کند.

اسلاید 206: خواص درختهای B*هر صفحه حد اکثر m فرزند دارد.هر صفحه بجز ریشه حداقل[(2m-1)/3] فرزند دارد.ریشه حداقل دو فرزند دارد.تمام برگها در یک سطح قرار دارند.

اسلاید 207: روش LRUاین روش زمانی کارساز است که احتمال در خواست صفحاتی که در بافر است از درخواست احتمال صفحاتی که در بافر وجود ندارند بیشتر باشد.

اسلاید 208: درخت B امکان بازیابی، درج و حذف کردن کلیدها را درزمان متناسب با log K I یا بهتر از آن فراهم می کند، I اندازه ی شاخص را نشان می دهد و K یک عدد طبیعی وابسته به دستگاه است که اندازه ی صفحه را نشان می دهد، به طوری که نگهداری و دستیابی، نزدیک به حالت بهینه باشد.ارزیابی سرعت درخت B

اسلاید 209: PAGE FAULTفرایند دستیابی به دیسک برای خواندن صفحه ای که در بافر وجود ندارد.

اسلاید 210: دو علت برای نقص صفحه وجود دارد:هیچگاه تا کنون از آن صفحه استفاده نکرده ایم.آن صفحه قبلا در بافر بوده است اما صفحه جدیدی جایگزین آن شده است.

اسلاید 211: فصل دهمدستیابی به فایل های ترتیبی شاخص دار و درختهای B+

اسلاید 212: اهداف فصل آشنایی با فایل های ترتیبی شاخص دار.شرح عملیات روی مجموعه ای ترتیبی از بلوک ها که رکوردها را به ترتیب توسط کلید ذخیره می کنند.چگونه می توان یک مجموعه شاخص را روی یک مجموعه ی ترتیبی ایجاد و یک ساختار فایل ترتیبی شاخص دار ایجاد نمود.آشنایی با کاربرد درخت B برای حفظ مجموعه شاخص و در نتیجه آشنایی با درخت B+ و درخت B+ پیشوندی ساده (prefix B+ tree).چگونه مجموعه شاخص درخت B در یک درخت B+ پیشوندی ساده، می تواند از مرتبه ی متفاوتی بوده، تعداد متغیری از جدا کننده ها (separators) را نگهداری می کند.مقایسه نقاط ضعف و قوت درخت های B+، درخت های B+ پیشوندی ساده و درخت های B.

اسلاید 213: اين فايل داراي ساختاري فاقد هر گونه نظم است . يعني ركوردها بر اساس مقادير هيچ نوع كليدي مرتب نشده اند و در بهترين حالت نظم بين ركوردها ، نظمي زماني است .فايل با ساختار پايل يا برهم :

اسلاید 214: فايل ترتيبي كه بر دو نوع فايل ترتيبي كليدي و فايل ترتيبي زماني است . در فايل ترتيبي زماني ، ركوردها به ترتيب ورود به سيستم ذخيره مي شوند و در فايل ترتيبي ، لود اوليه تمام نمونه ركوردها بر اساس مقادير صفت كليد ذخيره شده است به طوريكه تمام نمونه ركوردها قالب از پيش طراحي شده اي دارند .

اسلاید 215: فايل ترتيبي شاخص دار :اين ساختار براي تسريع واكشي تك ركورد از يك فايل ترتيبي طراحي و ايجاد مي شود . از شاخص براي تسريع واكشي اطلاعات استفاده مي شود .

اسلاید 216: فايل چند شاخصي :اين ساختار چنان است كه پديده عدم تقارن در آن وجود ندارد ، زيرا روي تعدادي و حتي تمام صفات كليد مي توان شاخص ايجاد كرد .

اسلاید 217: ساختار فايل مستقيم :در اين ساختار درج و واكشي ركوردها با استراتژي خاصي صورت مي گيرد . به طوريكه يكي از صفات خاصه به عنوان كليد در نظر گرفته شده ، سيستم فايل آن را پردازش مي كند و حاصل آدرسي است كه ركورد بايد در آن جاي گيرد .

اسلاید 218: ساختار فايل چند حلقه اي :در اين ساختار، ركوردهاي مختلف در حلقه هايي تعويه مي شوند به طوريكه هر عنصر حلقه ، با شروع از سرآيند ، به عنصر بعدي و آخرين عنصر به سرآيند نشانه مي رود . اين ساختار حجم بالايي از نشانه روها را دارد كه مديريت آن مهم ترين مسئله به نظر مي رسد .

اسلاید 219: فايل ترتيبي با ساختار مستقيم در اين ساختار با استفاده از نشانوند جستجو مي توان از يك نوع تابع درهم ساز براي دستيابي به فايل استفاده كرد . تابع درهم ساز ، پس از اعمال روي مقادير نشانوند جستجو ، براي هر ركورد عددي را به دست مي دهد كه نشان دهنده موقعيت نسبي ركورد در فايل است كه همان آدرس نسبي ركورد (RRN) است . سيستم فايل با داشتن RRN و طول ركورد و نيز آدرس شروع فايل (BOF)‌ آدرس محل درج ركورد را به دست مي دهد .نشانوند جستجوتابع درهم سازRRN استآدرس ركورد با استفاده از فرمول زير حاصل مي شود :آدرس ركورد = آدرس شروع فايل + ( RRN – 1 ) * R

اسلاید 220: نشانوند جستجوتابع درهم سازRRآدرس ركورد با استفاده از فرمول زير حاصل مي شود :آدرس ركورد = آدرس شروع فايل + ( RRN – 1 ) * R

اسلاید 221: دستیابی شاخص دار فایل را می توان به عنوان مجمو عه ای از کلید ها در نظر گرفت که توسط کلید شاخص بندی شده اند.

اسلاید 222: دستیابی ترتیبیبه فایل می توان دستیابی ترتیبی داشت (برای رکورد های پیوسته – بدون پیگرد) و رکورد ها را به ترتیب توسط کلید باز گرداند.

اسلاید 223: مجموعه ترتیبیمجموعه ای از رکورد ها که به طور فیزیکی توسط کلید ها مرتب شده اند و رکورد هایی به آن اضافه یا از آن حذف می شوند.

اسلاید 224: ته ریز شدن در درخت B می تواند منجر به دو راه حل زیر شود:اگر یک گره مجاور نیز نیمه پر باشد می توان دو گره را در هم ادغام کرد و یکی از آنها را برای استفاده دوباره آزاد ساخت.اگر گره های مجاور بیش از نیمه پر باشند می توان رکورد ها را دو باره میان گره ها توزیع کرد تا توزیع تقریبا متعادل گردد.

اسلاید 225: اهمیت قرار دادن شاخص در حافظهچون این شاخص از نوع ساده ای است رکورد های مشخص را با جستجوی دودویی اندیس می یابیم .اگر این جستجو در حافظه صورت پذیرد خوب عمل می کند.با تغییر بلوکها در مجموعه ترتیبی , در اثر شکستن بلوکها , ادغام و تو زیع دوباره , شاخص باید بهنگام شود .بهنگام سازی یک شاخص ساده برای رکورد های طول ثابت , در صورتی که نسبتا کوچک باشد و در حافظه نگنجد خوب عمل می کند.

اسلاید 226: درخت B+ پیشوندی سادهيك درخت B+ كه مجموعه شاخص آن , حاوي كوچكترين جداكننده يا پيشوندي كليدها باشد ايجاد مي شود درخت B+ پيشوندي نام دارد.مجموعه انديس يك درخت B است . تغييرات صورت گرفته در مجموعه انديس , تغييرات ثانويه را نتيجه جانبي حاصل از عمليات اصلي روي مجموعه ترتيبي است. د ر همه عمليات درج و حذف , عمل اصلي در مجموعه ترتيبي صورت مي گيرد. چون ركوردها در آن قرار دارند . فقط وقتي جدا كننده جديدي به مجموعه شاخص مي افزاييم كه بلوك جديدي به مجموعه ترتيبي اضافه مي شود .

اسلاید 227: درخت B+درختي متشكل از يك مجموعه ترتيبي از ركوردها كه به طور ترتيبي بر حسب كليد و به همراه يك مجموعه شاخص كه دستيابي شاخص شده به ركوردها را فراهم مي آورد , مرتب شده اند.همه اين ركوردها د ر مجموعه ترتيبي نگهداري مي شوند. درج و حذف ركوردها از طريق شكافتن , پيوند دادن و توزيع دوباره بلوك ها در مجموعه ترتيبي صورت مي پذيرد.

اسلاید 228: تفاوت ميان درخت B+ يشوندي ساده و درخت B+ آن است كه B+ از پيشوندهايي به عنوان جداكننده استفاده نمي كند . در عوض جدا كننده ها د ر مجموعه انديس , صرفا يك كپي از نمونه هاي واقعي اند.

اسلاید 229: نکاتاگر بلوکها در مجموعه ترتیبی شکافته شوند , یک خط جدا کننده جدید باید در مجموعه شاخص درج گردد.اگر بلوکها در مجموعه ترتیبی ادغام شوند یک جدا کننده باید از مجموعه شاخص حذف گردد.اگر رکورد ها بین بلوکها در مجموعه ترتیبی دوباره توزیع شوند , مقدار یک جداکننده در مجموعه شاخص باید تغییر یابد.

اسلاید 230: بلوکاندازه فیزیکی یک گره برای مجموعه اندیس , معمولا برابر با اندازه یک بلوک در مجموعه ترتیبی است.در چنین موردی به جای گره از لفظ بلوک برای مجموعه شاخص استفاده می کنیم .

اسلاید 231: دلایل استفاده از اندازه بلوک مشترک میان مجموعه های ترتیبی و اندیسی:معمولا از آن رو برای مجموعه شاخص از اندازه بلوک مجموعه ترتیبی استفاده می شود که تطابق خوبی میان اندازه بلوک , ویژگیهای دیسک گردان و مقدار حافظه در دسترس وجود دارد.بنا بر این , اندازه بلوکی که برای مجموعه ترتیبی بهترین باشد , برای مجمو عه شاخص نیز بهترین خواهد بود.

اسلاید 232: 2. با اندازه بلوکهای مشترک , پیاده سازی یک الگوی بافر دهی برای ایجاد درخت B+ پیشوندی ساده مجازی مشابه درختهای B مجازی آسانتر می گردد.

اسلاید 233: 3. بلوکهای مجموعه ترتیبی و بلوکهای مجموعه شاخص غالبا در یک فایل قرار داده می شوند تا از جستجو میان دو فایل جداگانه در هنگام دستیابی به درخت B+ پیشوندی ساده پرهیز شود.استفاده از یک فایل برای هر دو نوع بلوک , در صورت هم اندازه بودن آنها آسانتر صورت می پذیرد.

اسلاید 234: ساختار درونی بلوکهای مجموعه ترتیبی : یک درخت B از مرتبه متغییراین ساختار بلوک شامل موارد زیر می شود:تعداد جداکننده هاطول کل جدا کننده ها

اسلاید 235: نکته 1:بلوک صرفا یک دسته برش داده شده از یک فایل همگن نیست , بلکه چیزی بیش از یک مجموعه رکورد است.بلوک خود می تواند دارای یک ساختار درونی پیچیده باشد , که شامل شاخص داخلی آن , مجموعه ای از رکورد های طول متغییر , مجموعه های جداگانه ای از رکورد های طول متغییر و غیره باشد.

اسلاید 236: نکته 2:هر گره در مجموعه اندیس درخت B از درخت B+ پیشوندی ساده دارای مرتبه متغییر است.زیرا هر بلوک از مجموعه شاخص حاوی تعداد متغیری از جداکننده ها است.

اسلاید 237: دلیل استفاده از کوتاه ترین جدا کننده ها فشرده سازی هر چه بیشتر آنها در یک بلوک از مجموعه شاخص است.این بدان معنا است که , در بلوکهای مجموعه شاخص از فیلد هایی با طول متغییر استفاده می کنیم.

اسلاید 238: خصوصیات مشترک درختهای B و B+ و B+ پیشوندی ساده1.همگی ساختار های شاخص صفحه ای هستند.یعنی کل اطلا عات موجود در بلوک را یکباره به حافظه منتقل می کنند.در نتیجه می توان از میان حالتهای مختلف تنها با چند پیگرد , حالتی خاص را در دیسک یافت.شکل این درختها پهن و تو خالی است.

اسلاید 239: 2. در هر سه روش درختهایی نگهداری می شود که ارتفاع آنها موازنه است .درختها به شیوه ای غیر عادی که منجر به جستجو های طولانی برای کلید های معین می شود رشد نمی کنند.

اسلاید 240: 3.در همه موارد درختها از پایین به بالا رشد می کنند و موازنه از طریق شکستن بلوک , ادغام و توزیع دوباره حفظ می شود.4.با هر سه ساختار می توان از طریق استفاده از شکافتگی دو به سه و در صورت امکان توزیع دوباره به جای شکستن بلوک , بازدهی را بالا برد.

اسلاید 241: 5.هر سه روش را می توان به عنوان ساختار های درختی مجازی پیاده سازی کرد که در آن آخرین بلوکهای استفاده شده در حافظه نگهداری می شوند.6.هر یک از این سه روش را می توان با استفاده از ساختار های موجود در بلوک با رکورد های طول متغییر به کار برد.

اسلاید 242: تفاوت میان درخت B و B+تفاوت مهم میان درخت B و B+ در آن است کهدر درخت B+ همه اطلاعات مربوط به کلید ها و رکورد ها در یک مجموعه پیوند یافته از بلوکها موسوم به مجموعه ترتیبی قرار دارند.

اسلاید 243: دو مزیت مهم ساختار درخت B+ نسبت به درخت Bمجموعه ترتیبی را می توان به شیوه ای واقعا ترتیبی و خطی پردازش کرد و در نتیجه به ترتیب کلید ها به رکورد ها دستیابی مو ثری داشت.شاخص با یک کلید منفرد یا جدا کننده به ازای هر بلوک از رکورد های داده ها , به جای یک کلید به ازای هر رکورد ساخته می شود.

اسلاید 244: پایان