ایران سرفراز- نرم افزار وپروژهای دانشجویی


نرم افزار وپروژهای دانشجویی

(ذخیره و بازیابی اطلاعات)-ساختار فایل ها -سازمان دیسک ها-حافظه جانبی و نرم افزار

 

ساختار فایل ها

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



mohsen_mahyar@yahoo.com


منبع: سیستم و ساختار فایل
مولف: زولیک
تعداد واحد:3

فصل اول

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

هدف کتاب

یافتن راههایی برای به حداقل رساندن دستیابی به دیسک , برای فایل هایی است که اندازه ومحتویات آنها تغییر می کند.

عوامل موثر در طراحی ساختار فایل

n      زمان دستیابی نسبتا کم دیسک ها

n      ظرفیت بالای آنها

n      حفظ اطلاعات پس از قطع جریان برق

تاریخچه مختصری درباره طراحی ساختار فایل

  1. دستیابی ترتیبی (فایل ها بر روی نوار)
  2. درخت دودویی AVL
  3. درخت B
  4. درخت B+:ترکیب درخت B و لیست پیوندی
  5. دستیابی مستقیم

 

فصل دوم

عملیات مهم پردازش فایل

فایلهای فیزیکی و منطقی

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

باز کردن فایل ها

معرفی تابع OPEN

 FD=OPEN(FILENAME,FLAGS[,PMODE]) 

 

  1. FD:توصیف کننده فایل.
  2. FILENAME:یک رشته کاراکتری حاوی نام فایل فیزیکی.
  3. FLAGS:عملکرد تابع OPEN را کنترل کرده وتععیین می کند که فایل موجود را برای خواندن یا نوشتن باز می کند یا خیر.
  4. PMODE:حالت محافظت فایل را بر می گرداند.

    آرگومان

نوع

تــوضیـــح

مقدار flags

int

 مقدار flags با اجرای یک عمل or بیتی روی مقادیر زیر تعیین می شود .    

 

 

: الحاق عمل نوشتاری به انتهای فایل O_APEEND

 

 

:ایجاد یک فایل برای نوشتنO_CREAT

 

 

 مشخص شده باشد و فایل موجود باشد خطائی را باز می گرداند .O_CREAT : اگر O_ECLE

 

 

: باز کردن فایل فقط برای خواندن O_RDONLY

 

 

: باز کردن فایل برای خواندن و نوشتنO_RDWR

 

 

:باز کردن فایل فقط برای نوشتن O_WRONLY

 

 

: اگر فایل موجود باشد مقدار ان را از بین می برد .O_TRUNC

 

 

بستن فایل ها

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

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

خواندن و نوشتن

n      READ(SOURCE_FILE,DESTINATION_ADDR,SIZE)

 

n      WRITE(DESTINATION_FILE,SOURCE_ADDR,SIZE)

 

DESTINATION: نام فایل مقصد

 

SOURCE:نام فایل منبع

 

SIZE:تعداد بایتهایی که باید خوانده یا نوشته شود

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

SEEK(SOURCE_FILE,OFFSET)

 

SOURCE_FILE:نام فایل منطقی که در آن جستجو صورت می گیرد

 

OFFSET:میزان حرکت اشاره گر فایل را مشخص می کند

 

پیگرد با جریان های C

POS=FSEEK(FILE,BYTE_OFFSET,ORIGIN)

 

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

 

FILE:توصیف کننده فایلی که FSEEK  باید در آن اعمال شود.

 

BYTE_OFFSET:تعداد بایتهایی که باید از مبدا حرکت داده شود.

 

 

برنامه نمایش محتویات با استفاده از جریان

#INCLUDE<STDIO.H>      

Main( ) {        

Char ch  ;

FILE *file ;

Char filename [20] ;

Printf (" enter the name of the file") ; //step 1

Gets (filename) ;         //step 2

File = fopen (filename, "r") ;   //step 3

While (fread(&ch, 1, 1, file) ! = 0) ;    //step 4a

    Fwrite (&ch, 1,  1, student) ;          //step 4b

Fclose (file) ; //step 5

 

}          برنامه نمایش محتویات با استفاده ا ز کلاسهای جریان ++ C:

 

#include <fsream.h>

main ( ) {

char ch ;

fstream file ;

char file name [20]  ;

cout << "enter the name of the file: "                 //step 1

 << flush; 

cin >> filename;          //step 2

file . open (filename,ios::in);                             //step 3

file . unsetf(ios::skipws);

while (1)

  {

    file >> ch;                                                //step 4a

    if (file.fail ()) break;           

    cout << ch;                                             //step 4b

  }

    file . close ();                                                     //step 5

}

 

ساختار فهرست ها در یونیکس

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

 

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

 

 

 

نمونه ای از فهرست ها در یونیکس

 

 

 

 

 

 

 

 

 

نمونه ای از فهرست ها در یونیکس

 

 

 

 


 

 

 

 

                    

 

 

                                                             

 

 

 

 

دستگاههای فیزیکی و فایل های منطقی

n      در یونیکس , فایل مجموعهای از بایتها است

n      در یونیکس چگونگی و محل ذخیره فایل ها مهم نیست

n      در یونیکس مهم نیست که فایل ها از کجا می آیند

n      در یونیکس شکل فیزیکی فایل مهم نیست زیرا نمای منطقی فایل در یونیکس یکی است.

 

 

 

فصل سوم

 

حافظه جانبی و نرم افزار سیستم

 

بطور کلی هر سیستم کامپیوتری از دو محیط قابل تشخیص تشکیل شده است:

n      محیط درون ماشینی:

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

تعریف حافظه

 

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

 

دلایل مهم بکارگیری انواع مختلف رسانه های ذخیره سازی عبارتند از:

n      حافظه های درون ماشینی دارای ظرفیت محدود هستند.

n      لزومی ندارد همه اطلاعاتی که برای رفع نیازهای اطلاعاتی یک محیط عملیاتی ذخیره می شوند در حافظه اصلی باشند.

n      گران بودن حافظه اصلی.

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

 

دیسکها

 

n      دیسک های سخت ظرفیتی بالا با هزینه پایین به ازای هر بیت ارائه می دهند.

دیسک های فلاپی ارزان هستند ولی سرعت آنها کم است و داده های نسبتا کمی را نگهداری می

انواع حافظه های برون ماشینی از نظر تکنولوژی ساخت

 

n      چهار تکنولوژی وجود دارد:

n      تکنولوژی الکترومکانیک

n      الکترو مغناطیس

n      تکنولوژی الکترو اپتیک

n      تکنولوژی الکترومغنااپتیک

 

 

سازمان دیسک ها

 

 

n      اطلاعات به صورت شیارهایی (TRACK) روی سطح دیسک نگهداری می شود

n      هر شیار غالبا به چند سکتور(SECTOR) تقسیم می شود

n      سکتور کوچکترین بخشی از دیسک است که قابل آدرس دهی است.

n      دیسک گردان ها معمولا چند صفحه دارند

n      شیارهایی که مستقیما در بالا و پایین یکدیگر قرار دارند یک سیلندر را تشکیل می دهند.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

برآورد نیازهای سرعت و ظرفیت ها

n      ظرفیت شیار=تعداد سکتورها *طول هر سکتور بر حسب بایت

 

n      ظرفیت سیلندر=تعداد شیار ها در هر سیلندر*ظرفیت شیار

 

n      ظرفیت دیسک=تعداد سیلندرها*ظرفیت سیلندر

روش های سازمان دهی داده ها بر روی دیسک

 

  1. بر اساس سکتور

 

 

  1. بر اساس بلوک های تعریف شده توسط کار بر

سازمان دهی سکتور ها بر روی یک شیار

  1. سکتور ها بخش های مجاور و با اندازه ثابت از یک شیار باشند(این روش راه خوبی برای در نظر گرفتن فایل به طور منطقی است اما راه خوبی برای نگه داشتن فیزیکی سکتور ها نیست.)

 

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

کلاستر:

n      کلاستر عبارت از تعداد ثابتی از سکتور های پیوسته است

n      کلاستر های بزرگ تعداد زیادی از سکتور ها را بدون پیگرد می خوانند.

n      استفاده از کلاستر های بزرگ در هنگام پردازش ترتیبی فایل به کارایی بیشتر منجر می شود.

 

 

 

 

پراکندگی

 

     طول تمام سکتور های موجود در یک دیسک باید یکسان باشد اما همیشه این تناسب بر قرار نیست .دو شیوه برای مقابله با این روش وجود دارد:

 

  1. نگهداری یک رکورد در هر سکتور.
  2. قرار دادن رکورد ها به طور متوالی به طوری که بخشی از رکورد در یک سکتور و بخش دیگر آن در سکتور دیگر قرار گیرد.

سازمان دهی شیار ها به کمک بلوک

n      گاهی شیار ها به سکتور تقسیم نمی شوند بلکه به تعدادی از بلوک ها تقسیم می شوند.

n      همانند سکتور ها بلوکها را غالبا رکورد های فیزیکی می دانند.

n      سازمان دهی بلوکها مشکلات پوشایی سکتورها و پراکندگی را ندارد.

 

 

 

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

 

  1. زمان پیگرد
  2. تاخیر چرخشی
  3. زمان انتقال

 دیسک

 

 

 

زمان پیگرد

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

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

 

 

 

 

 

زمان انتقال

 

 

 

 

 

زمان انتقال از فرمول زیر بدست می آید:

 

 

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

تنگنای دیسک

راههای مقابله با تنگنای دیسک:

 

  1. چند بر نامه ای (multiprogramming)
  2. نوار بندی (striping)
  3. موازی گرایی(parallelism)

 

سازمان دهی داده ها در نوار ها

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

مقایسه ای از برخی سیستمهای نواری مقایسه ای از برخی سیستمهای نواری

9شیار

ریل یک اینچی

خودکار

200MB

9 خطی

1 MB/sec

نوارخطی

دیجیتال

کارتریج DLT

روبات

35GB

36خطی

5 MB/sec

hp colorado

T3000

کارتریج 4/1اینچی

دستی

1.6GB

مارپیچ

0.5MB/sec

strong tek

Redwood

کارتریج

نیم اینچی

سیلوی روباتی

50GB

مارپیچ

10 MB/sec

Sun T10000

کارتریچ75/5اینچی

خودکار

500GB

مارپیچ

120 MB/sec

 

نوار 7شیاره(A) 9شیاره(B)

بیت توازن

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

در نوار دو نوع بیت توازن وجود دارد:

n      بیت پاریتی عرضی یا کاراکتری

n      بیت پاریتی طولی

n      بیت پاریتی عرضی برای هرکاراکتر و بیت پاریتی طولی، برای تعدادی کاراکتر ایجاد می شود.

 

 

نوار گردان ها

 

 

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

 

  1. تراکم نوار
  2. سرعت نوار
  3. اندازه شکاف بین بلاک ها

براورد طول نوار مورد نیاز

طول فیزیکی یک بلوک از داده ها=b

 

طول شکاف بین بلا ک ها=g

 

تعداد بلاک های داده ها=n

 

 

فصای لازم برای نگهداری فایل :s

 

S=n*(b+g)

اندازه بلوک / تراکم نوار=b

 

طول بلوک=b

 

 

تراکم ضبط موثر:

مقدار داده های واقعی را که به ازای هر اینچ از نوار می توان ذخیره کرد:

 

تراکم ضبط موثر=تعداد بایتها در هر بلوک/تعداد اینچهای مورد نیاز برای هر بلوک

برآورد زمان انتقال داده ها

n      عوامل موثر در سرعت انتقال داده ها:

 

  1. اندازه شکاف های بین بلاکی
  2. اندازه بلاک های داده

 

سرعت اسمی =تراکم نوار*سرعت نوار

مقایسه دیسک و نوار

n      نوار برای پردازش ترتیبی و دیسک برای پردازش تصادفی است.

n      نوار ها به یک فرایند اختصاص دارند در حالی که دیسک ها معمولا چند فرایند را سرویس دهی می کنند.

n      نوار ها ارزانتر از دیسک ها هستند.

n      سرعت پردازش دیسک ها بالاتر است.

CD_ROM

n      نقطه قوت:ظرفیت ذخیره سازی بالا-بهای کم و دوام زیاد

 

 

n      نقطه ضعف:جستجو در آن بسیار کند است

 

 

کارایی در جستجو

 

n      در واقع ضعف اصلی CD_ROM در دستیابی مستقیم است زیرا بسیار زمان بر است

سرعت انتقال داده ها

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

ظرفیت ذخیره سازی

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

دستیابی فقط خواندنی

n      CD_ROM  یک رسانه انتشاراتی است و پس از نوشتن محتویات آن قابل تغییر نیست.

تکنیک CVA  دربرابر CAV

نوشتن و خواندن نا متقارن

n      به این معنی که ما فقط یک بار روی آن می نویسیم ولی هزاران بار آن را می خوانیم.

DVD(Digital versatile Disk )

n      در سال 1997 چند شرکت بزرگ تجهیزات الکترونیکی سازمانی بنام DVD – Forum تاسیس کردند که هدفش تولید استاندارد جدید برای CD بود که پس از کشمکشهای زیاد (Digital video pisk) DVD با 8 نوع متفاوت ساخته شدند.

n      در ابتدا DVD ها فقط برای ویدئوها طراحی شدند. بنابراین تحت نام (Digital video Disk)  معرفی شدند.

 

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

انواع DVD از نظر ظرفیت

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

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

n      کاربرد DVDها متنوع است: video- DVD که برای نمایش فیلم Data- DVD برای کاربردهای نرم افزاری Audio- DVD برای گوش کردن موسیقی ها بکار می روند.

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

آشنایی با بافر و بافرینگ

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

 

 

 

 

نحوه ایجاد بافرها

n      خود برنامه ساز بافر را ایجاد می کند: با ایجاد ناحیه ای در حافظه

n      با اجرای یک ماکرو، که از سیستم عامل درخواست ایجاد بافر می کند.

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

 

 

 

 

بافر دهی چند گانه

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

 

 

 

 

حالت تعیین محل در بافر دهی

  1. بافر مستقیما بین داده ها و حافظه باشد.

 

  1. بافر های سیستم همه بافر ها را کنترل کنداما اشاره گری برای محل بافر ها در اختیار برنامه باشد.

 

 

 

پراکنش ورودی

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

تمر کز خروجی

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

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

 

 

 

 

 

 

سازمان دهی فیلد ها و رکورد ها

n      واحد اصلی داده ها فیلد است.

n      آرایه مجموعه ای از فیلد های مثل هم است.

n      رکورد مجموعه ای از فیلد های متفاوت است.

n      رکوردی که در حافظه نگهداری می شود را یک شی گویند

n      فیلد های رکورد را اعضای آن می نامند.

 

 

 

 

ساختار های فیلد

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

 

روش 1: ثابت کردن طول هر فیلد

 

n      مزیت این روش در این است که با محاسباتی ساده می توان داده ها را از فیلد های اولیه باز یابی کرد

 

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

 

 

روش2: قرار دادن نشانگر طول فیلد در ابتدای هر فیلد

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

این فیلدها را مبتنی بر طول می نامند.

 

 

 

روش 3 : جدا کردن فیلد ها با فاصل

 

 

 

 

 

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

  در بسیاری از موارد از کاراکتر فضای خالی استفاده

  می شود.

 

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

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

 

اما عیب این روش فضای زیادی است که تلف می کند.

 

 

 

ساختار های رکورد

 

 

n      رکورد مجموعه ای از فیلد ها است.

 

n      مجموعه ای از رکورد ها فایل را تشکیل می دهند.

 

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

روش های سازمان دهی رکورد های فایل

n      قابل پیش بینی کردن طول رکورد ها بر حسب بایت.

n      قابل پیش بینی کردن طول رکورد ها بر حسب فیلد ها.

n      شروع هر رکورد با یک نشانگر طول که تعداد بایتهای رکورد را نشان می دهد.

n      استفاده از فایل دیگری برای نگهداری آدرس شروع هر رکورد.

n      قرار دادن فاصل در انتهای هر رکورد برای جدا کردن آن از رکورد بعدی.

 

روش 1 : قابل پیش بینی کردن طول رکورد ها بر حسب بایت

n      فایلی با طول ثابت , فایلی است که در آن تعداد بایتهای همه رکورد ها یکسان است.

 

n      رکورد های با طول ثابت , غالبا به عنوان محلی برای نگهداری تعداد متغیری از فیلد ها , با طول متغیر به کار می روند.

روش 2 : قابل پیش بینی کردن طول رکورد ها بر حسب فیلد ها.

n      در این روش به جای آنکه مشخص کنیم هر رکورد در فایل حاوی تعداد ثابتی از بایتهاست , می توان مشخص کرد که حاوی تعداد ثابتی از فیلد هاست.

روش 3: شروع هر رکورد با یک نشانگر طول که تعداد بایتهای رکورد را نشان می دهد.

n      در این روش فیلدی در ابتدای هر رکورد در نظر گرفته می شود و طول رکورد در آنجا ذخیره می گردد.

n      از این روش معمولا برای کار با رکورد هایی با طول متغییر استفاده می شود.

روش 4 : استفاده از فایل دیگری برای نگهداری آدرس شروع هر رکورد.
 

n      برای نگهداری آفست بایت مربوط به رکورد های موجود در فایل , می توان از اندیس استفاده کرد.با آفست بایت می توان ابتدای هر رکورد را یافت و طول رکورد را محاسبه کرد

روش 5 : قرار دادن فاصل در انتهای هر رکورد برای جدا کردن آن از رکورد بعدی.
 

n      این حالت در سطح رکورد ها , دقیقا مشابه راه حلی است که برای متمایز ساختن فیلد ها در برنامه ها به کار می رود.


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

فصل پنجم

مدیریت فایل هایی از رکورد ها

 

 

کلید های رکورد

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

 

 

جستجوی ترتیبی

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

ارزیابی جستجوی ترتیبی

به طور کلی کار مورد نیاز برای جستجوی ترتیبی در فایلی با

N رکورد با n  متناسب است.

حداکثر n  مقایسه و به طور میانگین n/2  مقایسه مورد نیاز است.

بهبود کارایی جستجوی ترتیبی با بلوک بندی رکورد ها

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

n      گرچه بلوک بندی می تواند منجر به بهبود چشمگیر کارایی شود , مرتبه عملکرد جستجوی ترتیبی را تغییر نمی دهد.

n      زمان جستجو هنوز o(N) است و با اندازه فایل نسبت مستقیم دارد.

n      بلوک سازی , اختلاف میان سرعت دستیابی در حافظه و زمان دستیابی در حافظه ثانویه را نشان می دهد.

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

n      با بلوک سازی در زمان صرفه جویی می شود زیرا مقدار جستجو کاهش می یابد.

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

ابزار های یونیکس برای پردازش ترتیبی

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

 

 

 

دستیابی مستقیم

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

رکورد های سرایند

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

 

  1. اندازه سرایند
  2. تعداد رکورد ها
  3. اندازه هر رکورد

دستیابی به فایل و سازمان دهی فایل

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

 

n      تعامل میان ساز مان دهی فایل و دستیابی به فایل , بسیار سودمند است.

داده های انتزاعی برای دستیابی به فایل

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

 

 

سرآیند ها و فایل های خود توصیف گر

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

 

 

 

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

 

  1. نامی برای هر فیلد

 

  1. طول هر فیلد

 

  1. تعداد فیلد های هر رکورد

عوامل موثر بر قابلیت حمل

  1. اختلاف میان سیستم های عامل

 

  1. اختلاف میان زبان ها

 

  1. اختلاف در معماری ماشین

توافق بر سر رمز گذاری دودویی

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

یونیکس و قابلیت حمل

 

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

n      مواردی که ابزار dd در اخ تبدیل از یک اندازه بلوک به دیگری

n      تبدیل رکورد های طول ثابت به طول متغییر و بالعکس

n      تبدیل اسکی به ابسدیک و بالعکس

n      تبدیل همه کاراکتر ها به حروف کوچک یا حروف بزرگ

n      تبادل هر جفت دلخواه از بایتها

 تیار قرار می دهد:

 

فصل ششم

 

 

 

 

 

 

 

 

سازمان دهی فایل ها برای کارایی

فصل ششم

سازمان دهی فایل ها برای کارایی

دلایل فشرده سازی فایل ها

n      فایل های کوچکتر نیاز به حافظه کمتری دارند که باعث صرفه جویی می شود.

n      سریعتر انتقال داده می شوند که زمان دسترسی را کوتاهتر می کند یا به جای آن می توان با همان زمان دسترسی از پهنای باند کمتر و ارزانتر استفاده کرد.

n      به صورت ترتیبی سریعتر قابل پردازش هستند.

 

 

n      تکنیک های فشرده سازی استفاده از یک نماد گذاری جدید

 

n      حذف دنباله های تکراری

 

n      تخصیص کد های با طول متغییر

 

استفاده از یک نماد گذاری جدید

معایب فشرده سازی با رمز

  1. با استفاده از رمز گذاری دودویی فایل به وسیله اشخاص قابل خواندن نیست.
  2. زمانی که بخواهیم نامی را به فایلمان اضافه کنیم زمانی را برای رمز گذاری از دست خواهیم داد.
  3. باید ماژول های رمز گذاری و رمز گشایی را در تمام نرم افزار هایی که فایل را

 

 

حذف دنباله های تکراری

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

 

 

تخصیص کد های با طول متغییر

 

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

کد های با طول متغییر فرم دیگری از کاهش زواید است.

روش های فشرده سازی بر گشت ناپذیر

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

فشرده سازی در یونیکس

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

باز یابی فضای داخل فایلها

n      با داده های اضافی چه باید کرد؟

 

  1. آنها را در انتهای فایل قرار داد و اشاره گری ایجاد کرد تا از مکان اولیه رکورد به بقیه آن اشاره کند.

 

  1. کل رکورد را در انتهای فایل دوباره نوشت.

 

 

انواع تغییرات در فایل

 

 

 

n      اضافه کردن رکورد

 

n      بهنگام سازی رکورد

 

n      حذف رکورد

حذف رکورد و متراکم کردن فایل

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

 

حذف رکورد های با طول ثابت برای بازیابی پویای فضا

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

  1. رکورد های حذف شده به طور خاصی علامت گذاری شوند.
  2. بتوانیم محلی را که توسط رکورد های حذف شده اشغال شده بود را پیدا کنیم.

 

 

مواردی که برای باز یابی سریع  فضا به آنها نیاز داریم:

 

 

  1. راهی که بلا فاصله بدانیم حفره های خالی در فایل وجود دارد یا نه؟

 

راه حل:

n      استفاده از لیست های پیوند برای پیوند دادن تمام رکورد ها هر دو نیاز فوق را بر آورده می کند.

 

n      لیست پیوندی ساختمان داده ای است که هر گره آن به گره بعدی اشاره می کند.

 

 

 

پشته ها

آ سان ترین راه برای کار کردن با لیست استفاده از آن به صورت پشته است.

 

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

 

برای حل دو مسئله مر بوط به دسترسی سریع به فضای قابل بازیابی رکورد های حذف شده نیاز است که:

n      بدانیم که آیا حفره های خالی در فایل وجود دارد.

 

n      اگر چنین حفره ای وجود دارد مستقیما به آن پرش کنیم.

 

 

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

n      راهی برای پیوند دادن رکورد های حذف شده و تبدیل آنها به یک لیست.

n      الگوریتمی برای اضافه کردن رکورد های حذف شده به لیست.

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

پراکندگی حافظه

n      فضای تلف شده در داخل یک رکورد پراکندگی داخلی نامیده می شود.

 

n      اگر با رکورد های طول ثابت کار کنیم برای به حداقل رساندن پراکندگی داخلی باید حداقل طول رکورد را انتخاب کنیم.

 

 

راهبرد های انتخاب جا

n      اولین جای مناسب(first fit)

 

n      مناسب ترین جا(best fit)

 

n      نامناسب ترین جا(worst fit)

 

اشکال روش best fit

n      زمان پردازش اضافی

 

n      وجود پراکندگی خارجی

 

 

اشکال روش worst fit

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

جستجوی دو دویی در برابر جستجوی ترتیبی

n      جستجوی دودو یی فایلی با n رکورد حد اکثر به

[log n]+1 مقایسه نیاز دارد .

n      اما جستجوی ترتیبی فایلی مشابه حداکثر به n

 مقایسه و به طور متوسط به n/2 مقایسه نیاز دارد

 

محدودیت های جستجوی دودویی و مرتب سازی داخلی

n      جستجوی دودویی نیاز به بیش از یک یا دو دسترسی به دیسک دارد.

n      نگهداری یک فایل به صورت مرتب شده خیلی گران تمام می شود.

n      مرتب سازی داخلی تنها در مورد فایل های کوچک عملی است.

مرتب سازی کلیدی

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

 

 

فصل هفتم

 

 

شاخص گذاری

شاخص چیست؟

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

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

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

شاخص چند سطحی

 

n      مزیت شاخص ها

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

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

 

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

 

 

شکل زیر را در نظر بگیرید :

 

 

 

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

 

 

کاتالوگ کارتی چیست؟

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

مقایسه سرعت دسترسی

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

 

 

عملیات مورد نیاز برای نگهداری فایل شاخص بندی شده

 

n      ایجاد فایل داده ها و شاخص خالی اولیه

n      باز کردن فایل شاخص در حافظه ,قبل از به کار گیری آن

n      نوشتن فایل شاخص بر روی دیسک , پس از به کار گیری آن

n      افزودن رکورد هایی به فایل داده ها

n      حذف رکورد ها از فایل داده ها

n      بهنگام کردن رکورد ها در فایل داده ها

n      بهنگام کردن شاخص برای انعکاس تغییرات به عمل آمده در فایل داده ها

ایجاد فایل داده ها و شاخص خالی اولیه

دو فایل باید ایجاد شود:

باز کردن فایل شاخص در حافظه ,قبل از به کار گیری آن

 

  1. فایل داده ها برای نگهداری اشیائ داده ای
  2. فایل شاخص برای نگهداری کلید اولیه

بازیابی و ذخیره اشیاء توسط کلاس io buffer انجام می شود.

نوشتن فایل شاخص بر روی دیسک , پس از به کار گیری آن

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

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

n      باید مکانیسمی باشد که به برنامه اطلاع دهد که شاخص در چه زمانی از رده خارج است

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

 

 

افزودن رکورد هایی به فایل داده ها

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

حذف رکورد ها از فایل داده ها

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

بهنگام کردن رکورد ها در فایل داده ها

بهنگام سازی به دو صورت انجام می شود:

 

  1. بهنگام سازی تعداد فیلد و کلید را تغییر می دهد
  2. بهنگام سازی بر فیلد کلید تا ثیر نمی گذارد.

بهینه سازی

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

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

شاخص های بزرگ

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

معایب دستیابی به شاخص روی دیسک

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

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

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

n      در صورتی که سرعت دستیابی در اولویت قرار داشته باشد از درهم سازی استفاده شود

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

نکته 1:

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

نکته 2:

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

نکته 3:

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

افزودن رکورد

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

نکته

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

حذف رکورد ها

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

بهنگام سازی رکورد ها

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

در بهنگام سازی سه وضعیت پیش می آید:

n      بهنگام سازی با عث تغییر کلید ثانویه می شود

 

n      بهنگام سازی باعث تغییر کلید اولیه می شود

 

n      بهنگام سازی محدود به فیلد های دیگر

ساختار های شاخص ثانویه دو مشکل دارند

n      هر بار که رکورد جدیدی به فایل افزوده می شود باید فایل شاخص را دوباره مرتب کنیم.

n      اگر کلید های ثانویه وجود داشته باشد فیلد کلید ثانویه برای هر ورودی تکرار می شود.

انقیاد

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

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

نکته

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

انقیاد درون داده ها هنگامی بهترین نتیجه را می دهد که:

n      فایل داده ها ایستا یا تقریبا ایستا باشد و نیاز کمی به حذف , اضافه یا بهنگام سازی داده ها داشته باشد.

n      کارایی سریع طی بازیابی واقعی , از اولویت بالایی بر خوردار است.

 

 

 

فصل هشتم

 

 

 

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

عملیات

n      عملیات کمک ترتیبی شامل پردازش هماهنگ دو یا چند لیست ترتیبی برای ایجاد یک لیست خروجی است.

 

n      روال زیر تطابق بین دو لیست را نشان می‌دهد.

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)

 

 

 

While (More items)

{

If (Item (1) <  Item (2))

More items= next Item List (1);

Else If Item (1) = Item (2)

{

Process item (1) ; // Match found

More items= next ItemInList;

}

Else

More items = next ItemInList(2)

}

finishup();

Return 1;

}

 

 

 

ترتیب روال همخوانی

n      آماده سازی

n      دستیابی به عضو بعدی لیست

n      همزمان سازی

n      کنترل شرایط پایان فایل

n      تشخیص خطا ها

 

 

الگوریتمی برای ادغام k  طرفه

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

 

 

الگوریتمی که می توان برای ادغام k طرفه در نظر گرفت بدینگونه است :

 

n      Int minitem = minindex (item , k )

n      Process item ( minitem),

n      For (i=0 ; i<k ; i++ )

n                                        If ( item (minitem) = = item(i)

n                                              More items[i] = nextiteminlist(i);

 

 

 

مراحل مرتب سازی در حافظه

  1. مرتب سازی رکورد ها با استفاده از یک روال مرتب سازی استاندارد
  2. خواندن فایل از روی دیسک به حافظه
  3. نوشتن دوباره فایل روی دیسک

 

 

درخت دودویی صفحه ای

  

 

 

 

 

 

 

بازیابی ترتیبی کلید ها به صورت زیر انجام می شود

n      تعیین مقدار کلید موجود در اولین موقعیت هرم

 

n      انتقال بزرگترین مقدار هرم به اواین محل آن و کم کردن یک واحد از تعداد عناصر

 

n      ترتیب دوباره هرم

برنامه حذف

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 ;      }

 

 

فایل با ساختار درخت K-D

n      این فایل گونه ای از ساختار درخت جستجوی دودویی است . اما تفاوت فایل با ساختار درخت K-D با فایل با ساختار درخت جستجوی دودویی دراین است که فیلد کلید در سطوح مختلف یکسان نیست .

n      به طورکلی ، تعداد درخت های K-D برای یک مجموعه از رکوردها می تواند  بیش از یک باشد .انتخاب یک  درخت از درختهای ممکن بستگی به نظمی دارد که براساس آن می خواهیم رکوردها را درج کنیم .

مثالی از درخت K-D

 

مرتب سازی کلیدی دو نارسایی دارد:

n      هنگامی که کلید ها مرتب سازی می شوند باید زمان زیادی صرف این موارد شود ,پیگرد هر رکورد در رکورد های مرتب شده,خواندن هر رکورد به حافظه و سپس نوشتن آن روی فایل مرتب شده.

n      در مرتب سازی کلیدی اندازه فایلی که قابل مرتب سازی است به تعداد جفت کلید/اشاره گری که در حافظه جا شود محدود می شود.

مراحل مرتب سازی

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

 

n      نوشتن رانش های مرتب شده روی دیسک

مراحل ادغام

n      خواندن رانش های مرتب شده به حافظه برای ادغام

 

n      نوشتن فایل مرتب شده بر روی دیسک

 

راهکارهای کاهش زمان

n      تخصیص سخت افزار بیشتر نظیر دیسک گردان و حافظه

n      اجرای ادغام در بیش از یک مرحله

n      افزایش طول رانش های مرتب شده از لحاظ الگوریتمی

n      یافتن راههایی برای همپوشانی عملیات i/o

به کمک سخت افزار

n      افزایش مقدار حافظه

n      افزایش تعداد دیسک گردان ها

n      افزایش تعداد کانال های i/o

 

ابزار هایی  برای بهبود کارایی مرتب سازی خارجی

n      برای مرتب سازی درون حافظه ای از مرتب سازی هرمی در یک رانش استفاده می کنیم

n      استفاده از حد اکثر حافظه ممکن

n      اگر تعداد رانش های اولیه بزرگ باشد از ادغام چند مرحله ای استفاده می کنیم

n      استفاده از گزینش جایگزینی برای تشکیل رانش های اولیه

n      از بیش از یک دیسک گردان و کانال io استفاده کنیم

 

مراحل مرتب سازی روی نوار

n      تقسیم فایل مرتب نشده به رانش های مرتب شده

 

n      ادغام رانش ها به یک فایل مرتب شده

راهکارهای کاهش زمانهای تاخیر چرخشی و پیگرد

n      با اجرای ادغام در بیش از یک مر حله

 

n       

n       

n       

n       

n       

n       

n       

n       

n       

n       

n       

n       

 

n       

n      افزایش اندازه رانش های مرتب شده اولیه

 

 

تعداد رکوردها به ازای هر پیگرد برای تشکیل رانشها  

اندازه  رانشهای تشکیل یافته

تعداد رانشهای تشکیل شده

تعداد پیگردهای مورد نیاز برای تشکیل رانش

مرتبه ادعام به کار رفته

تعداد کل پیگردها

دقیقه

ساعت

 

 䦋㌌㏒㧀좈琰茞ᓀ㵂Ü

تعداد رانشهای تشکیل شده

دقیقه

ساعت

000,100

000,100

800

1600

681600

5

2

 

گزینش جایگزینی و سپس ادغام 534 جانبی (رکوردها به ترتیب تصادفی)

25000

150000

534

6400

534

521132

36

1

 

 

گزینش جایگزینی و سپس ادغام 200 جانبه  (رکوردها تا حدی مرتب هستند)

25000

400000

200

6400

200

206400

38

00

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

مقایسه ی زمان های دستیابی مورد نیاز برای مرتب سازی 80 میلیون رکورد با استفاده از مرتب سازی حافظه ای و گزینش جایگزینی و یک ادغام دو جانبه پس از هریک.

تعداد رکوردها به ازای هر پیگرد برای تشکیل رانشها  

اندازه  رانشهای تشکیل یافته

تعداد رانشهای تشکیل شده

الگوی ادغام مورد استفاده

تعداد پیگردها در فازهای ادغام

تعداد کل              پیگردها

دقیقه

ساعت

 

 䦋㌌㏒㧀좈琰茞ᓀ㵂Ü

تعداد رانشهای تشکیل شده

دقیقه

ساعت

000,100

000,100

800

25 ادغام 32 جانبه و سپس یک ادغام 25 جانبه

127200

24

0

 

گزینش جایگزینی و سپس ادغام 534 جانبی (رکوردها به ترتیب تصادفی)

25000

150000

534

19 ادغام 28 جانبه و سپس یک ادغام 19 جانبه

15162/22876

124438

23

0

 

 

گزینش جایگزینی و سپس ادغام 200 جانبه  (رکوردها تا حدی مرتب هستند)

25000

400000

200

20 ادغام10 جانبه و سپس یک ادغام 20 جانبه

16000/8000

110400

20

0

 

 

 

 

 

 

 

 

 

 

 

فصل نهم

شاخص بندی چند سطحی و درختهای B

اهداف فصل

n      توسعه ی درخت های B برای حل مسأله هایی که برای آن ها طراحی شده اند.

n      نگاهی به سایر ساختارهای درختی که ممکن است در حافظه های جانبی مورد استفاده قرار گیرند، مثل درخت AVL صفحه بندی شده (paged).

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

n      درک ویژگی های مهمی که توسط درخت های B پردازش می شوندو بررسی اهمیت آن ها در حافظه های جانبی.

n      طراحی شیء گرای درخت های B

n      تعریف کلاس BTreeNode، نمایش گره های درخت های B در حافظه.

n      تعریف کلاس BTree، نمایش کامل درخت های B و تمام اعمال آن ها.

n      تشریح پیاده سازی اصول عملیات درخت های B

n      معرفی بافردهی صفحه ای و درخت های B مجازی.

n      توصیف الگوریتم های اصلی درخت B، مثل آن هایی که برای ساختن درخت B* و درخت B با رکوردهای طول متغیر به کار گرفته شده اند.

n      دستگاهها با دستیابی تصادفی واقعی:حافظه کر

 

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

نکته

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

مشکل قبل به دو مشکل تقسیم می شود:

n      جستجو بر حسب شاخص باید سریع تراز جستجوی دودویی باشد.

n      درج و حذف باید با سرعت جستجو کردن انجام شود.

راهکار مشکل اول

n      استفاده از درخت های دودویی صفحه ای

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

 

 

 

شکل زیر نمونه ای از درخت دودویی صفحه ای را نشان می دهد.

 

 

 

 

 

 

 

 

 

 

 

 

 

 


راهکار مشکل دوم

n      استفاده از درخت موازنه شده

دو مزیت درختهای AVL

n      با تعیین کردن حداکثر تفاوت مجاز در ارتفاع هر دو زیر درخت این درخت ها حداقل کارایی را در جستجو تضمین می کنند.

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

تاریخچه درخت B

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

درخت B

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

متد جستجو در درخت B

n      به صورت تکراری عمل می کنند.

n      در دو مر حله عمل می کنند : به صورت یک در میان روی کل صفحات.

مراحل درج کردن

n      جستجو تا سطح برگ با استفاده از متد FINDLEAF قبل از تکرار.

n      درج تشخیص سرریز و تقسیم کردن در مسیر رو به بالا.

n      ایجاد یک ریشه جدید , در صورتی که ریشه فعلی تقسیم شده است.

خواص یک در خت B از مرتبه m

n      هر صفحه حد اکثر m فرزند دارد.

n      هر صفحه بجز ریشه ها و برگها حداقل  [m/2]فرزند دارد.

n      ریشه حد اقل دو فرزند دارد.

n      تمام برگها در یک سطح قرار دارند.

n      سطح برگها, یک شاخص کامل و مرتب شده از داده های مر بوط به درخت را ایجاد می کند.

 

 

 

خواص درختهای B*

n      هر صفحه حد اکثر m فرزند دارد.

n      هر صفحه بجز ریشه حداقل[(2m-1)/3] فرزند دارد.

n      ریشه حداقل دو فرزند دارد.

n      تمام برگها در یک سطح قرار دارند.

 

 

روش LRU

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

 

ارزیابی سرعت درخت B

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

PAGE FAULT

n      فرایند دستیابی به دیسک برای خواندن صفحه ای که در بافر وجود ندارد.

دو علت برای نقص صفحه وجود دارد:

n      هیچگاه تا کنون از آن صفحه استفاده نکرده ایم.

 

n      آن صفحه قبلا در بافر بوده است اما صفحه جدیدی جایگزین آن شده است.

 

 

 

فصل دهم

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

اهداف فصل

n      آشنایی با فایل های ترتیبی شاخص دار.

n      شرح عملیات روی مجموعه ای ترتیبی از بلوک ها که رکوردها را به ترتیب توسط کلید ذخیره می کنند.

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

n      آشنایی با کاربرد درخت B برای حفظ مجموعه شاخص و در نتیجه آشنایی با درخت B+  و درخت B+ پیشوندی ساده (prefix B+ tree).

n      چگونه مجموعه شاخص درخت B در یک درخت B+ پیشوندی ساده، می تواند از مرتبه ی متفاوتی بوده، تعداد متغیری از جدا کننده ها (separators) را نگهداری می کند.

n      مقایسه نقاط ضعف و قوت درخت های B+، درخت های B+ پیشوندی ساده و درخت های B.

فایل  با ساختار پایل یا برهم :

n      این فایل دارای ساختاری فاقد هر گونه نظم است . یعنی رکوردها بر اساس مقادیر هیچ نوع کلیدی مرتب نشده اند و در بهترین حالت نظم بین رکوردها ، نظمی زمانی است .

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

فایل ترتیبی شاخص دار :

n      این ساختار برای تسریع واکشی تک رکورد از یک فایل ترتیبی طراحی و ایجاد می شود . از شاخص برای تسریع واکشی اطلاعات استفاده می شود .

فایل چند شاخصی :

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

ساختار فایل مستقیم :

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

ساختار فایل چند حلقه ای :

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

فایل ترتیبی با ساختار مستقیم

n      در این ساختار با استفاده از نشانوند جستجو می توان از یک نوع تابع درهم ساز برای دستیابی به فایل استفاده کرد . تابع درهم ساز ، پس از اعمال روی مقادیر نشانوند جستجو ، برای هر رکورد عددی را به دست می دهد که نشان دهنده موقعیت نسبی رکورد در فایل است که همان آدرس نسبی رکورد (RRN) است . سیستم فایل با داشتن RRN و طول رکورد و نیز آدرس شروع فایل (BOF)‌ آدرس محل درج رکورد را به دست می دهد .نشانوند جستجوتابع درهم سازRRN است

n      آدرس رکورد با استفاده از فرمول زیر حاصل می شود :

n      آدرس رکورد  = آدرس شروع فایل  + ( RRN – 1 ) * R

تابع درهم ساز

RR

نشانوند جستجو

               

 

 

 

 

 

 

دستیابی شاخص دار

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

 

دستیابی ترتیبی

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

مجموعه ترتیبی

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

ته ریز شدن در درخت B  می تواند منجر به دو راه حل زیر شود:

n      اگر یک گره مجاور نیز نیمه پر باشد می توان دو گره را در هم ادغام کرد و یکی از آنها را برای استفاده دوباره آزاد ساخت.

n      اگر گره های مجاور بیش از نیمه پر باشند می توان رکورد ها را دو باره میان گره ها توزیع کرد تا توزیع تقریبا متعادل گردد.

اهمیت قرار دادن شاخص در حافظه

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

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

درخت B+ پیشوندی ساده

یک درخت B+  که مجموعه شاخص آن , حاوی کوچکترین جداکننده یا پیشوندی کلیدها باشد ایجاد می شود درخت B+ پیشوندی نام دارد.

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

درخت B+

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

n      همه این رکوردها د ر مجموعه ترتیبی نگهداری می شوند. درج و حذف رکوردها از طریق شکافتن , پیوند دادن و توزیع دوباره بلوک ها در مجموعه ترتیبی صورت می پذیرد.

n      تفاوت میان درخت B+ یشوندی ساده و درخت B+  آن است که B+ از پیشوندهایی به عنوان جداکننده استفاده نمی کند . در عوض جدا کننده ها د ر مجموعه اندیس , صرفا یک کپی از نمونه های واقعی اند.

نکات

n      اگر بلوکها در مجموعه ترتیبی شکافته شوند , یک خط جدا کننده جدید باید در مجموعه شاخص درج گردد.

n      اگر بلوکها در مجموعه ترتیبی ادغام شوند یک جدا کننده باید از مجموعه شاخص حذف گردد.

n      اگر رکورد ها بین بلوکها در مجموعه ترتیبی دوباره توزیع شوند , مقدار یک جداکننده در مجموعه شاخص باید تغییر یابد.

 

mohsen_mahyar@yahoo.com

 

بلوک

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

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

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

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

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

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

n      این ساختار بلوک شامل موارد زیر می شود:

  1. تعداد جداکننده ها
  2. طول کل جدا کننده ها

نکته 1:

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

نکته 2:

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

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

خصوصیات مشترک درختهای B و B+ و B+ پیشوندی ساده

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

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

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

 

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

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

 

6.هر یک از این سه روش را می توان با استفاده از ساختار های موجود در بلوک با رکورد های طول متغییر به کار برد.

تفاوت میان درخت B و B+

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

 

 

             پایان

 

با تشکر از استاد ایرج رضایی

mohsen_mahyar@yahoo.com

   + MOHSEN GHASEMI - ٩:٢٧ ‎ق.ظ ; ۱۳۸٩/٧/٢٦