Computer Software Engineering

مطالب تکثیر شده روی 12 صفحه

ص1

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

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

در بهترین حالت، نظم بین رکوردها، نظمی است زمانی (ترتیبی Entry sequential) انگار رکوردها بر یکدیگر پشته شده اند.

فرم کلی ساختار هر رکورد به شکل زیر است: A1=V1,A2=V2A3=V3,… که A1 نام فیلد (اسم صفت خاصه)، و V1 مقدار آن فیلد (مقدار صفت خاصه) می باشد.

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

کل تعداد فیلدها را a در نظر می گیریم و متوسط تعداد فیلدها را در یک رکورد با a' نشان می دهیم.

متوسط حافظه ی لازم برای هر فیلد را A بایت در نظر می گیریم و R=a'(A+V+2)

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

زمان واکشی در رکورد TF:

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

برای حالت بلاک بندی:  برای حالت بدون بلاک بندی:

 =سرعت انتقال خواندن انبوه و b=تعداد بلاک ها و B=طول بلاک ها و n=تعداد رکوردها

 این قدر بایت بر ثانیه خوانده می شود

زمان به دست آوردن رکورد بعدی TN:

چون در این سازمان هیچ نظمی نداریم معلوم نیست که رکورد بعدی کجاست و یک بار باید همه را بخواند یعنی TN=TF

زمان درج رکورد TI:

از آن جا که فایل پایل هیچ گونه نظمی ندارد، رکورد جدید همواره در انتهای فایل اضافه (Append) می شود.

1ـ خواندن آخرین بلاک فایل از دیسک به بافر s + r+ btt

2ـ اضافه کردن رکورد به بلاک خوانده شده. از آن جا که این عمل در حافظه صورت گرفته و بسیار سریع است، زمان آن را در محاسبات خود وارد نمی کنیم.

3ـ بازنویسی بلاک مذکور

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

***

ص2

زمان به هنگام سازی از طریق تغییر مقادیر فیلدها (Update):

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

1ـ رکورد مورد نظر را واکشی می کنیم 2ـ این رکورد را برای حذف علامت گذاری کنیم 3ـ رکورد حذف شدنی را در جای خود بنویسیم 4ـ رکورد را اصلاح می کنیم 5ـ رکورد جدید را به فایل اضافه می کنیم. (موارد 1و 2 و 3، Delete یا نتیجه ی Update شده را می بریم ته فایل می نویسیم به خاطر سادگی کار یا سر جایش آن را قرار می دهیم با علامت گذاری)

موارد 2و 4 در بافر صورت می گیرد

4ـ ایجاد دسته جدید است.

رکورد را می ریزیم داخل بافر

بافر

علامت گذاری می کنیم

محاسبه ی TD: از روی همین، عمل Delete کردن را می نویسیم و آن یک Update کردن درجا است.

حذف یک رکورد اینقدر زمان می گیرد:

زمان خواندن کل فایل Tx:

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

1ـ یا بر اساس ترتیب منطقی یا سریال                        Serial                      

2ـ یا بر اساس ترتیب فیزیکی یا ترتیبی                        Sequential                 که زمان کمتری می برد

ممکن است موقعی که سریال می خوانیم مثلا اگر بر اساس ترتیب دانشجویی بخوانیم ممکن است در یک فیلد نداشته باشیم چرا که رکوردها نظمی ندارند و آن هایی را که نداریم ته فایل قرار می گیرند.

D+o+n

O+n

اگر بر اساس Sort کردن حساب کنیم و فایل Sort شده باشد، قبل از خواندن.

تذکر: Sort یعنی طوری رکوردها را عوض کنیم که ترتیب منطقی و فیزیکی یکی نشوند.

زمان سازمان دهی مجدد TY:

برای این که یک نظم به فایل بدهیم و حافظه های هرز را از بین ببریم و فایل را کوچک کنیم.

حال فرض کنیم D رکورد حذف شدنی داشته باشیم و 5 رکورد منتقله و n تعداد رکوردهای اولیه در فایل.

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

ویژگی ها و کاربرد ها:

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

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

***

ص3

فایل ترتیبی Sequential:

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

 

رکوردها بر اساس فیلد (صفت خاصه) به صورت صعودی مرتب شده اند.

طول و ساختار هر رکورد عموما در هر فایل ذخیره می گردد.

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

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

گاهی اوقات به فایل ترتیبی، فایل ترتیبی کلیدی (key) یا فایل ترتیبی مرتب شده Sorted Sequential نیز گفته می شود در مقابل به فایلی که بر اساس فیلدی مرتب نشده باشد، فایل ترتیبی زمانی یا Unordered Sequential می گویند.

یک ویژگی مهم فایل ترتیبی آن است که جهت بالا بردن سرعت، عملیات درج در فایل اصلی انجام نمی گیرد بلکه در یک فایل کمکی به نام فایل ثبت تراکنش ها یا TLF (Transaction Log File) صورت می گیرد. یعنی مثلا رکوردهای جدید به سادگی و با سرعت در انتهای فایل TLF ذخیره شوند بر اساس ترتیب زمانی ورود و بدون انجام مرتب سازی و بر اساس فیلد اصلی؛ سپس در یک دوره ی متناوب (مثلاً در آخر هر روز) در هنگام سازماندهی مجدد، محتویات فایل TLF (که نا مرتب است) خوانده شده و اطلاعات آن با فایل اصلی ادغام می شود. بدین ترتیب پس از سازماندهی مجدد فایل TLF خالی شده و کلیه ی اطلاعات در فایل اصلی به صورت مرتب شده موجود خواهد بود. مکان ثبت تراکنش ها هم می تواند به صورت یک فایل مجزا (TLF) در نظر گرفته شود و هم می تواند ناحیه ای در فایل اصلی باشد. به این مکان ثبت تراکنش ها، ناحیه سر ریزی یا Overflow Area نیز می گویند.

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

هنگامی که پردازش سریالی رکوردها مورد نظر باشد، ساختار ترتیبی بهتر از پایل است. در بسیاری از سیستم های تجاری که رکوردها به صورت دسته ای (Batch) پردازش می شوند، از ساختار ترتیبی استفاده می شود.

متوسط اندازه رکورد:                                  R=a.V                                                      a تعداد فیلد

کل فایل:                                                   S=n.a.V                                   V طول فیلد

کل فایل با تراکنش:                                    S=(n+o).a.V                                           n تعداد رکوردها

***

ص4

محاسبه ی TF در فایل ترتیبی: چقدر زمان طول می کشد به یک رکورد دسترسی پیدا کنیم.

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

n تعداد رکوردها در داخل فایل اصلی و o تعداد رکوردها در ناحیه ی سر ریزی و t' نرخ انتقال انبوه است.

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

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

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

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

ولی اگر رکورد در ناحیه ی سر ریزی (فایل تراکنش) باشد پس از بررسی کل فایل اصلی با جست و جوی دودویی که زمان  را می برد باید به سراغ ناحیه ی سر ریزی رفته و آن را به صورت خطی جست و جو کنیم. پس اگر o تعداد رکوردها در ناحیه ی سر ریزی و b تعداد رکوردها در ناحیه ی اصلی (مرتب شده) باشد آنگاه:

مثال: فایل ترتیبی داریم شامل 400000 رکورد می باشد. اگر  باشد، قبل از اضافه شدن رکوردی به ناحیه ی سر ریزی، زمان متوسط واکشی چه میزان خواهد بود؟

S=16 ms, r=8.3 ms, btt=18 ms

و اگر فایل به صورت پایل می بود:

***

ص5

جست و جو با پرش بلاکی (Skipped Block Search)

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

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

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

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

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

اگر فرض کنیم رکوردها در جدول T.L.F باشد، با کلید نمی شود رکورد بعدی را در این جدول حدس زد و پیدا کرد؛ بنابراین پیدا کردن رکورد بعدی بی معنی است.

محاسبه TI در فایل ترتیبی:

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

 : یافتن نقطه ی منطقی درج ،  : زمان شیفت یک بلاک

با فرض کوچک بودن فایل، در حد یک استوانه، دیگر زمان S را در ارزیابی زمان شیفت هر بلاک دخالت ندادیم و زمان r را نیز به دلیل این که عملیات بلاک به بلاک به طور پی در پی انجام می گیرد در محاسبه ئارد نمی کنیم.

***

ص6

درج فایل های بزرگ:

برای هر یک درج، اگر همه ی رکوردها را شیفت بدهیم وقت گیر است و از روش T.L.F استفاده می کنیم و اگر رکوردی بخواهیم درج بشود می بریم ته فایل

زمان به هنگام سازی تغییر دهنده:

Tu (Update) , TD (Delete)

برای حذف یک رکورد از روش حذف منطقی به صورت درجا استفاده می شود. رکورد مورد نظر در زمان TF خوانده شده و علامت حذف در ابتدای آن در بافر نوشته شده و در گردش بعدی دیسک (2r) در سر جای اولیه اش رو نویسی می گردد. پس داریم:

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

 برای اصلاح بر روی فیلد غیر کلید

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

 برای اصلاح بر روی فیلد کلید

در عملیات اصلاح در فایل ترتیبی طول رکورد تغییر نمی کند.

اگر رکورد مورد اصلاح در ناحیه ی سر ریزی باشد دیگر فرقی نمی کند که فیلد کلید آن اصلاح می شود و یا فیلد غیر کلید آن. در هر دو حالت عملیات اصلاح به صورت در جا بوده و TF+2r زمان می برد.

برای خواندن کل فایل دو روش داریم:

الف ـ سریال (پی در پی) بدون نظم ، ب ـ ترتیبی که بر اساس نظم منطقی است.

الف) ، R طول رکورد ، t' زمان انتقال انبوه یک بلاک ،  زمان انتقال یک رکورد.

ب)  ، d تعداد رکوردهایی که حذف می شوند و علامت گذاری می شوند

زمان سازماندهی مجدد TY:

1: زمان Sort به اندازه ی o رکورد

2: خواندن فایل اصلی

3: خواندن فایل T.L.F

4: ادغام دو فایل و نوشتن آن ها به صورت یک فایل جدید (Merg).

***

ص7

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

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

مثال: فایل ترتیبی دانشجویان در زیر برحسب شماره دانشجویی مرتب شده می باشد که در کنار این فایل ترتیبی یک فایل ایندکس (شاخص) برحسب کلید اصلی (شماره دانشجویی) و یک فایل ایندکس برحسب معدل ترسیم شده است.

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

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

اگر در فایل ایندکس صفت خاصه ی شاخص، کلید اصلی باشد به آن شاخص اولیه یا اصلی می گویند (Primary Index). و در صورتی که فایل ایندکس بر اساس فیلدی غیر از کلید اصلی ساخته شود به آن شاخص ثانویه گویند (Secondary Index).

***

ص8

پس فایل شاخص مجموعه ای از تعدادی مدخل (Entry) می باشد که به فرم کلی زیر:

مقدار

آدرس

V

P

فیلد آدرس به طول P بایت حاوی یک نشانه گر به یک یا گروهی از رکوردهاست. در فایل داده ای اصلی فیلد مقدار به طول V بایت شامل صفت خاصه ای یا ترکیبی از صفات خاصه است که ایندکس بر اساس آن ساخته شده است بنابراین طول هر رکورد فایل شاخص برابر V+P بایت است. به هر نقطه از فایل داده ای اصلی که از مدخل شاخص به آن نشانه گر وجود دارد را لنگرگاه یا Anchor Point گویند.

اگر هر مدخل فایل شاخص به یک رکورد اشاره کند، شاخص را متراکم (Dense Index) گویند و اگر به گروهی از رکوردها مثلا یک بلاک اشاره کند، شاخص را غیر متراکم (Non Dense Index) گویند.

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

تعریف ظرفیت نشانه روی شاخص (Index fdnout):

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

مثال: اگر طول بلاک 2000 بایت، اندازه ی صفت خاصه ی شاخص V برابر 14 بایت و اندازه ی اشاره گر شاخص P برابر 6 بایت باشد، ظرفیت نشانه روی هر بلاک شاخص چقدر است؟

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

 , R=200 بایت , B=2000 بایت

 

در فایل اصلی 10 رکورد جای میگرد                                                                                            

حافظه ی مصرفی برای سطح اول شاخص                                                                

تعداد بلاک های سطح اول                                                                                                        

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

برای نگه داری در حافظه ی اصلی زیاد است                                                                              

تعداد بلاک ها در سطح دوم                                                                                                       

پس ساختار شاخص را در سه سطح ایجاد می کنیم                                  

بلاک های سطح سوم

و تعداد سطوح شاخص از رابطه ی زیر به دست می آید:

هرچه تعداد سطوح بیشتر باشد دفعات دستیابی برای واکشی رکورد بیشتر خواهد بود.

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

10 مدخل

10 بلاک

X=3

X=2

X=1

BF=10

100 تا

***

ص9

بررسی مسئله ی سر ریزی: به این چند سؤال ابتدا باید پاسخ داد.

1ـ فضای لازم برای درج رکورد سر ریزی چگونه انتخاب می شود؟

2ـ فضای انتخاب شده چگونه در محیط فیزیکی (دیسک) به فایل تخصیص می یابد؟

3ـ عمل درج با چه تکنیکی انجام می شود؟

الف: در نظر گرفتن جا در هر بلاک   ب: در نظر گرفتن فایل جداگانه   ج: در نظر گرفتن جا در همان فایل اصلی

برای حالت 1 سه راه حل پیشنهاد شده:

 

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

67

68

69

B

فایل اصلی

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

فایل اصلی

فایل سر ریزی

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

الف: استوانه های جداگانه در نظر بگیریم   ب: شیارهایی از هر استوانه برای سر ریزی همان استوانه در نظر   گرفته شود (در انتهای هر استوانه)

2ـ تقسیم بندی سخت افزاری است:

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

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

استوانه ها

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

اصلی

سر ریزی

3ـ عمل درج در ناحیه ی سر ریزی با چه تکنیکی انجام می شود؟

الف: درج در اولین بلاک جادار در ناحیه سر ریزی   ب: درج با Push Trough

الف) در این تکنیک، رکورد جدید مستقیما وارد بلاکی از ناحیه ی سر ریزی می شود و در اولین مکان آزاد جای می گیرد (در اولین بلاک جادار). سپس از رکورد منطقا پیشین به رکورد درج شده نشانه رو ایجاد می شود و به ترتیب زنجیره ی رکوردهای سر ریزی پدید می آید. در این تکنیک برای هر رکورد از ناحیه ی اصلی و ناحیه ی سر ریزی یک نشانه رو وجود دارد. البته ممکن است در بعضی از رکوردها محتوای این فیلد Null باشد.

***

ص10

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

ممکن است از یک بلاک چند اشاره گر به ناحیه ی سر ریزی داشته باشیم.

روش درج ساده است ولی جست و جو وقت گیر می باشد.

 

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

1ـ نظم درون بلاکی همیشه وجود داشته باشد، حتی برای ناحیه ی سر ریزی.

2ـ از هر بلاک ناحیه ی اصلی تنها یک اشاره گر به ناحیه سر ریزی اشاره کند.

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

در ناحیه ی اصلی داریم در لحظه ی شروع کار:

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

 

موارد استفاده ی ساختار:

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

***

ص11

ساختار فایل چند شاخصی Multi Indexed:

اهمیت این ساختار به خاطر این است که %70 الی %80 ساختار بانک های اطلاعاتی با این ساختار است.

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

سه ایراد عمده داشت: 1ـ ایستا بودن شاخصها بود. 2ـ عدم تقارن بود. 3ـ مسئله سر ریزی بود.

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

فایل اصلی

شاخص

سطح اول

ترتیب مثلا بر اساس نام خانوادگی باشد

ترتیب مثلا بر اساس اسم باشد

ترتیب مثلا روی شماره ی دانشجویی باشد.

فایل اصلی، غیر ترتیبی یا پایل میتواند باشد

شاخص متراکم، شاخص به همه ی رکوردها داریم.

شاخص دینامیک است، شاخص همراه تغییر رکوردها تغییر می کند.

این ساختار چنان است که پدیده ی عدم تقارن در آن وجود ندارد. زیرا روی تعدادی، حتی تمام صفات خاصه می توان شاخص داشت و مسئله ی رکوردهای سر ریزی به صورتی که در ساختار سوم مطرح بود در این جا وجود ندارد. یعنی درج رکوردهای جدید آسان تر و پویاتر است و بالاخره خود ساختار شاخص وضعیتی پویا دارد و هم روند با تغییرات فایل داده ای، قابل تنظیم و به هنگام در آوردن است. اگر a تعداد صفات خاصه در فایل باشد، حداکثر a فایل شاخص می توان داشت.

از آن جا که در یک رکورد به طور متوسط، a' تا صفت خاصه وجود دارد، لذا به یک رکورد a' ساختار شاخص ناظر است. پس این ساختار در اساس از نظر فایل داده ای همان پایل است اما مجهز به یک سری استراتژی دستیابی قوی، پویا و سریع.

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

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

***

ص12

اجزاء ساختار ترتیبی شاخص دار عبارتند از: ناحیه اصلی، ناحیه سر ریزی، مجموعه شاخص ها.

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

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

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

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

فایل های شاخص تأمین کننده ی استراتژی دستیابی برای فایل داده ای هستند.

در فایل داده ای مقدار فیلدی می تواند Null یا ناشناخته باشد.

شاخص گذاری جزو نوع دستیابی تصادفی است.

فایلی شامل اطلاعات ثبت نام دروس دانشجویان با 2000 رکورد داریم. هر دانشجو به طور متوسط 5/4 درس اخذ کرده است. اگر روی فیلد درس اخذ شده (که تکرار شونده است) شاخص ایجاد کنیم تعداد مدخل های این شاخص چقدر خواهد بود؟

2000×4.5=9000

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

اگر در فایلی که شاخص اولیه و ثانویه دارد بر اثر اصلاح، کلید اولیه تغییر کند، چه تنظیم دیگری را باید انجام دهیم؟

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

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