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

صفحه 1:


صفحه 2:
دانشگاه RE cy ‏اطلاعات‎ 

صفحه 3:


صفحه 4:
جلسات wlasue 9 well L wuluil tol aul> ‏عملیات مهم پردازش فایلء‎ ilgbls ,lisbe ‎Lb abslb‏ م افزا جلسه دوم: آذامه مبحث حافظه ‎Pe er‏ ‏1 ‏۱ ی 10 ‏ا ‎ae‏ ‎ve‏ جهانم : مقا غيم اساي سا خار فال ‏مديريت فايلهايي از ركوردها جلسه ينجم: ادامه مبحث مديريت فا | ‎Pera le) eee errs Pes eat pers‏ ‎PE ne >‏ ‎ 

صفحه 5:
فهرست ‎“Ml‏ ‏جلسه هفتم: ادامه ی ۳۵( 525000-07 sul ‏كم‎ Rice ‏شا‎ ‎Gans able meal‏ شاخص گذاري» پردازش کمک موجه و مرتب سازي ‏اب ۳ج هبست: پردآزش کمک ترئيبي و ‎eae Maine‏ فایل هاي بزرگ ‎SoS yu jloys ous all ‏جلسه يازدهم:‎ ‎Pye ry PA Spray 3 Cee) ‏ال‎ ‏تور ی‎ ])< ۳۳ ۳ wee) eee ‎ 

صفحه 6:
كت اله 1۳۳۷ 020 SoC etme ever nines Serer eyed +6 ‏شاخص دار و درخت هاي‎ جلسه چهاردهم: ادامه مبحث دستيابي به فایل ‎SPE es) Pet eerr er ane) Fy‏ ل 0 درهم سازي جلسه يانزدهم: ادامه مبحث درهم لاف ذا ل | سازيء درهم سازي قابل توسعه 8 

صفحه 7:
- ۰ آشنايي با طراحي و مشخصات ۱ ۰ عملیات مهم پردازش فایل ۰ حافظه جانبي و نرم‌افزار 7 

صفحه 8:
PAE ces cs Vee OPEN By SRE EO 

صفحه 9:


صفحه 10:
57 pe oe + 

صفحه 11:


صفحه 12:
و از ۶ ‎Sig :‏ 24 3 ۱ ; ا وسو ند 7 

صفحه 13:
| در ی 

صفحه 14:
عمليات 0 دازش فايل ae 

صفحه 15:


صفحه 16:


صفحه 17:


صفحه 18:


صفحه 19:


صفحه 20:


صفحه 21:
ی ا و 

صفحه 22:


صفحه 23:
۰ ۱ 3-4 ‎tency‏ در سا 

صفحه 24:


صفحه 25:


صفحه 26:


صفحه 27:
‎irae)‏ او ‎Nh ali Sg alls‏ ‎ ‎ 

صفحه 28:


صفحه 29:


صفحه 30:
i A TN 4 | f ۱ 

صفحه 31:
ظرفیت دیبتک تابعي از تعداد سیلندرها ؛تعدا شیار‌ها به ازاي هر سیلندر. و ظرفيت هر شیار است. 

صفحه 32:
دو روش براي ننازماندهي داده ,ها بر زوي دیسک وجود دارد:: () بز اساش سكتون ۲ بر اسامن بلوک هاي تعریف ده توسنط گاریر 

صفحه 33:


صفحه 34:


صفحه 35:
أشكل عدم جدهای فایل [تاجنه سایه زنذة شينة فضا: وی دیسک زا که رک فایل اد یل اشقال می‌کند نشان می‌دهد] 

صفحه 36:


صفحه 37:


صفحه 38:


صفحه 39:


صفحه 40:


صفحه 41:
ST BP ke BL, ‏ی‎ 

صفحه 42:


صفحه 43:


صفحه 44:


صفحه 45:
0 

صفحه 46:


صفحه 47:
۲ 20000 47 7 ‏تین‎ ha eI 

صفحه 48:


صفحه 49:
سرعت خطی ثابت CLV CAV hus © 1+ ‏شكل‎ 

صفحه 50:
بافر/(1/0 سیشتم »به مدیّیت فایل این امکان را مي دهد تا داذه ها را بر واحدهايي به اتداژه تنکتون‌یا بلوک بخوائد يا بتویسد. 

صفحه 51:
و 7 ‎aris‏ وش ی لس ی #0 27 

صفحه 52:


صفحه 53:
یک بافر خروجي ‎IMR‏ ‎ate sha‏ ی 

صفحه 54:
‎BP hee‏ رن ‎Sa‏ ينل ‎ 

صفحه 55:
بونام‌های کازبر ra ۱ ‏اه‎ vee be es ‏كك‎ 2 ea ۲ 4 ۱ ۲ 4 چایگرها کسولیز سخت‌اقزار 7 هعل ۳۲۳ ساختار 1/60 هسته 

صفحه 56:


صفحه 57:
سه نوع سيستم 1/0 متفاوت داريم : )( سیستم 1/0 لوكي ۲ ینتم ‎pS IS‏ )تیم ‎SITIO‏ اي 

صفحه 58:


صفحه 59:


صفحه 60:
[۱ eye pene 

صفحه 61:


صفحه 62:
و 7 ‎aris‏ وش ی لس ی #0 27 

صفحه 63:


صفحه 64:
زکورد مجموعه اي از فیلا ها است و مجموعه اي از رکوردها فایل را نشان مي ذهند: 

صفحه 65:


صفحه 66:


صفحه 67:
با ربوبرآذاري فایل مني توان بایت هاي واقعي نگهداري شده در آل را مشناهده کزند. 

صفحه 68:
‎Leth, +0‏ لعتیار قربار مي‌دهد تا چندین‌ک هن مي‌شولنند از لعضاو متداهايةشتركاستفادم کنند, ‎ 

صفحه 69:
ی تا زا فتردسازی وبازکرس ‎Josl‏ ‏بر فيلدهاىى طول ثابت \OButter He ‏أرليه كاراكثرى براى مقدار‎ VariableLengthButer خواندن و نوشتن اعمالی برای رکودهای طول متغير LengthFieldButier ‏اعمال فشردهسازى و بسط برا‎ ‏فبلدهاى ميتنى برطول‎ شکل ۱۴ ۳ سلسله مراتب Delemtedielautter ‏اعمال فترده‌ساری و بط‎ ‏برای فبلدهای فاصل‎ 

صفحه 70:
USE Sr eon 

صفحه 71:
لوف رب 0 و ی ‎pe‏ ‎aia‏ ی تین 

صفحه 72:
1 MY ‏لاني‎ pale) baa Sikes gs 

صفحه 73:
‎)١‏ كرجه بلوك بندي مي توائد منجر به بهبود جشمكير كارايي شوا »مرتبه عملکرد جستجوي ترئيبي را تغییر نمي دهد. ‎oS gh )۲‏ ساري ءاختلاف میان تترعت دستيابي بر خافظه و زمان دستيابي در حافظه ثانویه را نشان مي دهد. ‏۳) بلوک سازي تعذاد مقایسه هايي زا که باید در حافظه آنجام " شوند تغییر نمي ذهد و احتمالاً مقدار داده هاي انتقال یافته.میال حافظه و دیشک را افزایشمَي دهد. ‎ 

صفحه 74:


صفحه 75:
نك ليلد سكي کراکتن ‎Call ghee yg Le‏ ‎yyy‏ و دن صورت [ تا ‎ja Vey age‏ عالی به گوازد 

صفحه 76:


صفحه 77:


صفحه 78:


صفحه 79:


صفحه 80:


صفحه 81:
یک طراحي شيءگراي خوّب براي ماندگا شذن اشیاء ايد عمقي ازا خواندن ‎a‏ تم ایا قراهم ۵ 

صفحه 82:
تا کنون عمل پوشتن نیازمند به دو عمل جداگانه بود,: ۱ فشرده سازي در یک بافر۲) نوشتن بافر:روي فایل 

صفحه 83:


صفحه 84:
‎tia ee 0 ۱‏ زر سر وی ‎LF Uh aie hos‏ ‎ ‎ 

صفحه 85:
داده هايي مثل صوت .تصاویر »و اسناد به صورت فیلدها و رکوردها ذخیره نمي شوند. 

صفحه 86:


صفحه 87:


صفحه 88:


صفحه 89:


صفحه 90:
رن 

صفحه 91:
+ i? ll Sas a 2 

صفحه 92:
تا و زب ۷ = 9 7 ee oh Pe 9 و 

صفحه 93:
0-3000 fee ey by iy فايلهايي از ركوردها ۰ سازماندهي فایلها براي كارايي 

صفحه 94:
2 07 cian ‏ی‎ [1 1 

صفحه 95:
و 7 ‎aris‏ وش ی لس ی #0 27 

صفحه 96:


صفحه 97:
۱ Cre we Bier 

صفحه 98:


صفحه 99:


صفحه 100:
Few 

صفحه 101:


صفحه 102:


صفحه 103:


صفحه 104:


صفحه 105:


صفحه 106:
۱ اضنافه کردن رکوزد ۲ بهنگام ساززي رکورند ۳) حذف رگورد 

صفحه 107:


صفحه 108:


صفحه 109:


صفحه 110:


صفحه 111:


صفحه 112:


صفحه 113:


صفحه 114:


صفحه 115:


صفحه 116:


صفحه 117:


صفحه 118:


صفحه 119:


صفحه 120:
‎Byer‏ يي 

صفحه 121:
‎My‏ رد ند وید ‎ 

صفحه 122:
Few 

صفحه 123:
مدو شكلاز يمكر يت قلا ايه فال لش وک راوس 

صفحه 124:


صفحه 125:


صفحه 126:


صفحه 127:
127 a | شاخص 07 

صفحه 128:


صفحه 129:


صفحه 130:


صفحه 131:


صفحه 132:


صفحه 133:
79 8 4 ۱ 

صفحه 134:


صفحه 135:
منبع دیگر بهینه سازي چنتانچه رکوزد شاخصن تغییر ده باشد» نوشتن دربازه رکورد شاخ در فایل, شاخص ‎al‏ 

صفحه 136:
لونم دستیابی : ‎eee‏ Ape ی 

صفحه 137:


صفحه 138:


صفحه 139:


صفحه 140:


صفحه 141:


صفحه 142:
5 ‏و‎ aes p erg sak 777 

صفحه 143:
۳ aolol + ‎٠‏ بردازش كمك ترتيبي و مرتب سازي ۱ هاي بنزرگ 

صفحه 144:


صفحه 145:
اي شاخص 4 ۷ 4 17 pe 

صفحه 146:
2 ‏کم کر کر ی‎ igg ‏یر ری‎ eel 

صفحه 147:
داز ش کمک 1 1 34 ای رت إتب ترتيبي و مرتب زي فایل 5 اري فايل هاي برر. dee 

صفحه 148:


صفحه 149:


صفحه 150:
‎My‏ رد ند وید ‎ 

صفحه 151:
حافظه شامل سه مرحله آس 000 : 

صفحه 152:


صفحه 153:


صفحه 154:
اشكل ماسم ۷ بگ‌هرم كه به کل آ ری و برخت تمایش دایه شده است . 9 

صفحه 155:


صفحه 156:


صفحه 157:


صفحه 158:


صفحه 159:


صفحه 160:
ترتيبي و مرتب سازي فایل هاي بزر 

صفحه 161:


صفحه 162:


صفحه 163:


صفحه 164:


صفحه 165:
ادغام چند مرحله ای دارای ویژگی های مطلوب زیر است : ۱) هر رکورد فقط یک بار خوانده می شود. ۲) اگر برای مقایسه های انجام شده در عملیات ادغام از یک درخت انتخاب استفاده شود .در آن صورت تعداد مقایسه های مورد [ ۳) چون۲ با ۷| تناسب مستیم دارد اين عمل از مرتبة ( ۷,بوم[*0)۱1(بر حسب تعداد مقایسه ها) است. 

صفحه 166:


صفحه 167:


صفحه 168:


صفحه 169:
37 7 = ws 

صفحه 170:


صفحه 171:
1 2 7 ah ok ears ates J 

صفحه 172:


صفحه 173:


صفحه 174:


صفحه 175:


صفحه 176:
© ادامه مبحت ‎SoS yujlo»‏ ی و مرتب سازي فايل هاي بزرگ ‎٠‏ شاخص بندي جند سطحي و درختهاي © ‎176 

صفحه 177:
0 ليست ” ‏استفاده )5 حَداكثز حافظه ممكن‎ )٠١ ۳ اگر تعداد واذش هاي اولیه چتان بزرگ باشد که زمان کل پیگرد و چرخش بسیار بزگتر از, زمان انتقال کل باشند از ادغام چندمژحله اي انتفاده مي کنیم. ‎Eye Nae tee ga‏ م9 ‏8 از نیش از یک نیسنک,گردان کل 1/6 ات ‎ 

صفحه 178:


صفحه 179:


صفحه 180:
Gee pe 

صفحه 181:
ERG CPOE S eee eee yee. 16۹ 

صفحه 182:


صفحه 183:


صفحه 184:


صفحه 185:


صفحه 186:
شکن ‎٩۰٩‏ درختهایی که .1 ۸۷ نیستند. 

صفحه 187:
3 7 AP sees Ss 4 iat 

صفحه 188:


صفحه 189:


صفحه 190:


صفحه 191:


صفحه 192:


صفحه 193:
193 مبحث شاخص بندي چند سطحي و درخت 

صفحه 194:


صفحه 195:


صفحه 196:


صفحه 197:


صفحه 198:
00 

صفحه 199:
7 رز ‎ate‏ وه 

صفحه 200:
قوانین حذف کلید با از ؟ ‎)١‏ اكر تعداد كليدهاي > بیشتر 1 7 5 4 ‎ 

صفحه 201:


صفحه 202:


صفحه 203:


صفحه 204:
‎My‏ رد ند وید ‎ 

صفحه 205:


صفحه 206:


صفحه 207:
aid ape id 7 7 

صفحه 208:
۳ 

صفحه 209:
|B EUROeSE Bees CoP SRE EN EE Cne reer) e090 

صفحه 210:


صفحه 211:


صفحه 212:
‎BP hee‏ رن ‎Sa‏ ينل ‎ 

صفحه 213:


صفحه 214:
و 7 ‎aris‏ وش ی لس ی #0 27 

صفحه 215:
4 یکی از تواند منجر 2 8 ل 4 يحي و 

صفحه 216:


صفحه 217:


صفحه 218:


صفحه 219:


صفحه 220:
‎My‏ رد ند وید ‎ 

صفحه 221:
1 ‏داري جوت‎ citi tay at My oan ‏ز داریم عبذاکننده ها‎ 

صفحه 222:


صفحه 223:


صفحه 224:


صفحه 225:
هاي ‎ue Lis Pere‏ ۳ و درخت هاي0+ ‎٠‏ درهم سازي ‎225 

صفحه 226:
0 ae lt de 22111111117071 9 

صفحه 227:


صفحه 228:


صفحه 229:
0 معمولا ‎git‏ مجموعه شاخص از اندازه بلوک مكار على ترگيبي اتف الي كارك كلا تطایق. خوبی مین انداز بلوک ,ويژگيهاي دیسک گردان,»ومقدار حافظه در کسترش وجود Avis ۲) با اندازربلوک مشترک پیاده نسازي یک الگوي بافردهي براي : ایجاد درخت . . پيشوندي سساده مجازي »مشاب درختهاي, ظ) مجازي آسان تر مي گرند. ۳) يلوك هاي مجموعه تزتيتي و يلوك ها پ< ل ‎i‏ وند تا از 4 ی تا 

صفحه 230:


صفحه 231:


صفحه 232:
2 “id ۳ cian ih rae bite 

صفحه 233:
666 

صفحه 234:


صفحه 235:


صفحه 236:


صفحه 237:
درهم سازي 

صفحه 238:


صفحه 239:


صفحه 240:


صفحه 241:


صفحه 242:
242 الل ا ال 0 

صفحه 243:


صفحه 244:


صفحه 245:


صفحه 246:
‎BP hee‏ رن ‎Sa‏ ينل ‎ 

صفحه 247:


صفحه 248:


صفحه 249:
کر 

صفحه 250:
2 ه) ۵( دیل مبتا 

صفحه 251:
af sik AP atta, ‏ی‎ 

صفحه 252:


صفحه 253:


صفحه 254:


صفحه 255:
شكل ‎1١-9‏ میانگین لول جستجو در مقایسه پاد تسيتة قشردگی, دو فایل درهم‌سازی که بر آن رگورد می‌تراند نخیره شود.برای رفع برخوردها از سرریز فزاندهاستفاده می‌شود و فايل به حافظه بار شده است. 

صفحه 256:


صفحه 257:


صفحه 258:


صفحه 259:
5 107 aes p erg sak 777 

صفحه 260:


صفحه 261:
27 7 200 dice 701 1 7 

صفحه 262:


صفحه 263:


صفحه 264:
9 > ae 53 ‏د‎ ‎3 ‎hy NG 

صفحه 265:
درهم سازي قابل توسعه 

صفحه 266:
3 eT, Ut ai alae sighed gs 

صفحه 267:


صفحه 268:


صفحه 269:


صفحه 270:


صفحه 271:


صفحه 272:
5 ae ee Mee: Lon | pee 

صفحه 273:
929 

صفحه 274:


1 دانشگاه پيام نور دانشكده فناوري اطالعات 2 ترجمه: مهندس عين ا ...جعفرنژاد قمي ابراهيم محرابي تعداد واحد3 : 3 تهيه‌كننده: دكتر احمد فراهي فهرست جلسات جلسه اول :آشنايي با طراحي و مشخصات ساختار فايلها ،عمليات مهم پردازش فايل، حافظه جانبي و نرم افزار سيستم جلسه دوم :ادامه مبحث حافظه جانبي و نرم افزار سيستم جلسه سوم :ادامه مبحث حافظه جانبي و نرم افزار سيستم جلسه چهارم :مفاهيم اساسي ساختار فايل، مديريت فايلهايي از رکوردها جلسه پنجم :ادامه مبحث مديريت فايلهايي از رکوردها جلسه ششم :ادامه مبحث مديريت فايلهايي از رکوردها ،سازماندهي فايلها براي کارايي 4 فهرست جلسات سازماندهي Eفايلها براي جلسه هفتم :ادامه مبحث کارايي ،شاخص گذاري جلسه هشتم :ادامه مبحث شاخص گذاري جلسه نهم :ادامه مبحث شاخص گذاري، پردازش کمک ترتيبي و مرتب سازي فايل هاي بزرگ جلسه دهم :ادامه مبحث پردازش کمک ترتيبي و مرتب سازي فايل هاي بزرگ جلسه يازدهم :ادامه مبحث پردازش کمک ترتيبي و مرتب سازي فايلهاي بزرگ ،شاخص بندي چند سطحي و درختهاي B جلسه دوازدهم :ادامه مبحث شاخص بندي چند سطحي و درختهاي B 5 فهرست جلسات جلسه سيزدهم :دستيابي به فايل هاي ترتيبي شاخص دار و درخت هاي +B جلسه چهاردهم :ادامه مبحث Eدستيابي به فايل هاي ترتيبي شاخص دار و درخت هاي ، +B درهم سازي جلسه پانزدهم :ادامه مبحث درهم سازي جلسه شانزدهم :ادامه مبحث درهم سازي ،درهم سازي قابل توسعه 6 • آشنايي با طراحي و مشخصات ساختار فايلها • عمليات مهم پردازش فايل • حافظه جانبي و نرم‌افزار سيستم 7 آشنايي با طراحي و مشخصات ساختار فايلها 8 ساختار فايل ترکيبي از نحوه نمايش داده ها در فايل ها و عمليات الزم براي دستيابي به داده ها است. ساختار فايل به برنامه کاربردي اين امکان را مي دهد که داده ها را بخواند ،بنويسد و اصالح کند. 9 طي سه دهه اخير با بررسي تکامل ساختارهاي فايل مشاهده مي کنيم که طراحي ساختار فايل ابتدا از ترتيبي شروع شد ،سپس به ساختارهاي درختي رسيد و سرانجام دستيابي مستقيم مطرح شد .در همه اين موارد مشکالت و ابزارهاي طراحي مشابهي مشاهده شده است .اين ابزارها را ابزارهاي مفهومي مي نامند که روش هايي براي تنظيم و حل يک مسئله طراحي اند. 10 يک مشکل اصلي در توصيف کالس هايي که بتوان براي طراحي ساختار فايل آنها را به کار برد ،آن است که اين کالس ها پيچيده و در حال رشد هستند .کالس هاي جديد غالبا ً شکل اصالح شده يا توسعه يافته اي از کالس ها ديگر بوده ،جزئيات ارائه داده ها و عمليات باز هم پيچيده تر مي شود. 11 در يک سيستم اطالعاتي شيء گرا محتوا و رفتار داده ها ،در يک طراحي منسجم مي شود .اشياي سيستم به کالس هاي اشيايي با ويژگي هاي مشترک تقسيم مي شوند .هر کالس توسط اعضاي ( )membersخود توصيف مي شود که يا صفات داده ها (عضوهاي داده اي) يا توابع (توابع عضو يا متدها) هستند. 12 مشکل اصلي در طراحي ساختار فايل زمان نسبتا ً زيادي است که براي گرفتن تطالعات از ديسک مورد نياز است .در همه طراحي هاي ساختار فايل آنچه مورد توجه است به حد اقل رساندن دفعات دستيابي به ديسک و به حد اکثر رساندن احتمال وجود اطالعات مورد نظر برنامه کاربردي در حافظه است. 13 عمليات مهم پردازش فايل 14 هنگامي که درباره فايلي روي يک ديسک يا نوار صحبت مي کنيم ،منظور ما مجموعه اي از بايت ها است که در آنجا ذخيره شده اند .فايل در اين معنا داراي موجوديت فيزيکي است .يک ديسک ممکن است حاوي صدها و حتي هزاران فايل فيزيکي باشد. 15 برنامه غالبا ً نمي داند بايت ها از کجا مي آيند يا به کجا مي روند ،اين را مي داند که کدام خط را مورد استفاده قرار داده است .اين خطوط را معموالً فايل منطقي مي نامند تا از فايل فيزيکي ،که روي ديسک يا نوار قرار دارد متمايز گردد. 16 هنگامي که شناسه ( )identifierفايل منطقي با دستگاه يا فايل فيزيکي ارتباط پيدا کرد ،بايد اعالم کنيم که مي خواهيم با فايل چه کنيم : )۱باز کردن يک فايل موجود )۲ايجاد يک فايل جديد و حذف محتويات موجود در فيزيکي 17 فايل هنگامي که برنامه اي به صورت عادي پايان مي يابد فايل ها معموالً به طور خودکار بسته مي شوند .در نتيجه اجراي يک دستور بستن در داخل برنامه فقط براي محافظت آن در برابر اتالف داده ها در صورت توقف برنامه و آزاد کردن نام فايل هاي منطقي براي استفاده دوباره ضروري است. 18 خواندن و نوشتن در پردازش فايل اهميت بنيادي دارند ،اينها اعمالي هستند که پردازش فايل را به يک عمل ورودي/خروجي تبديل مي کنند. 19 براي دستيابي آسان به تعداد زياد از فايل ها کامپيوتر روشي براي سازماندهي فايل ها دارد .در يونيکس اين روش سيستم فايل ناميده مي شود .چون هر نام فايل در سيستم يونيکس بخشي از سيستم فايلي است که با ريشه آغاز مي شود ،هر فايل را مي توان انحصاراً با دادن نام مسير آن شناسايي کرد. 20 يکي از پر قدرت ترين ايده ها در يونيکس تعريفي است که از فايل مي شود .در يونيکس فايل مجموعه اي از بايت ها است و چگونگي و محل ذخيره آنها هم مهم نيست .همچنين مهم نيست که اين بايت ها از کجا مي آيند. اين نگرش معمولي به فايل موجب مي شو کاري را که در سيستم عامل هاي ديگر به زحمت انجام مي شوند ،در اين سيستم عامل به راحتي انجام پذير باشد. 21 يونيکس فرمان هاي بسياري براي دستکاري فايل ها دارد که عبارتند از : ‏cat, tail, cp, mv, rm, chmod, ls, mkdir, rmdir 22 حافظه جانبي و نرم افزار سيستم 23 دستگاه هاي حافظه جانبي ،با حافظه تفاوت بسيار دارند. همان طور که پيش از اين نيز متذکر شديم يک اختالف از آنجا ناشي مي شود که در دستگاه هاي حافظه جانبي زمان بيشتري براي دستيابي مورد نياز است .اختالف ديگر آن است که همه دستيابي ها يکسان نيستند. 24 ديسک ها انواع مختلفي دارند : )۱ديسک هاي سخت ()hard disks )۲ديسک هاي فالپي ()floppy disks )۳کارتريج ديسک )۴ديسک هاي نوري 25 دامه مبحث حافظه جانبي و نرم افزار سيس 26 اطالعات ذخيره شده روي ديسک ،در سطح يک يا چند صفحه نگهداري مي شود .ترتيب کار به صورتي است که اطالعات به صورت شيارهايي ( )tracksروي سطح ديسک نگهداري مي شوند .هر شيار غالبا ً به چند سکتور ( )sectorتقسيم مي شود .سکتور کوچکترين بخشي از ديسک است که قابل آدرس دهي است. 27 28 ديسک گردان ها معموالً چند صفحه دارند .شيارهايي که مستقيما ً در باال و پايين يکديگر قرار دارند ،يک سيلندر را تشکيل مي دهند .اهميت سيلندر در آن است که به همه اطالعات روي يک سيلندر مي توان بدون حرکت دادن بازوي نگهدارنده هد ( )headخواندن/نوشتن دستيابي داشت. حرکت اين بازو پيگرد ( )seekingنام دارد. 29 30 ظرفيت ديسک تابعي از تعداد سيلندرها ،تعدا شيارها به ازاي هر سيلندر و ظرفيت هر شيار است. 31 دو روش براي سازماندهي داده ها بر روي ديسک وجود دارد : )۱بر اساس سکتور )۲بر اساس بلوک هاي تعريف شده توسط کاربر 32 کالس تر عبارت از تعداد ثابت ي از س کتورهاي پيوسته است. مديريت فايل براي در نظر گرفتن فايل به عنوان مجموعه اي از کالسترها و در عين حال حفظ حالت س کتوري ،س کتورهاي منطق ي را ب ه کالسترهاي فيزيک ي ک ه ب ه آنه ا تعل ق دارد ،ب ه وسيله جدول تخصيص فايل ( )FATارتباط مي دهد. 33 اگر فضاي زيادي روي ديسک باشد ،ممکن است بتوان کاري کرد که فايل به طور کامل از کالسترهاي پيوسته تشکيل شود .در چنين موردي گفته مي شود که فايل حاوي يک حد ( )extentاست. 34 35 اتالف فضا در داخل يک سکتور را پراکندگي داخلي مي نامند .سازماندهي بلوک ها مشکالت پوشايي سکتورها و پراکندگي را ندارد ،زيرا اندازه بالک ها مي تواند تغيير کند تا سازماندهي منطقي داده ها امکان پذير شود. 36 بلوک معموالً طوري سازماندهي مي شود که تعداد مناسبي از رکوردهاي منطقي را نگهداري کند .براي اشاره به تعداد رکوردهايي که قرار است در هر يک از بالک هاي فايل نگهداري شوند ،از اصطالح ضريب بلوک بندي استفاده مي شود. 37 در الگوهاي آدرس دهي بالکي هر بلوک از داده ها معموالً با يک يا چند زير بلوک ( )subblockهمراه است که حاوي اطالعات اضافي راجع به بلوک داده ها است .معموالً يک زيربلوک شمارشي وجود دارد که تعداد بايت هاي موجود در بلوک مربوط را نگه مي دارد .همچنين ممکن است که يک زيربلوک کليد ،حاوي کليد مربوط به آخرين رکورد در بلوک داده ها باشد. 38 هم بالک ها و هم سکتورها نيازمند آنند که مقدار معيني از فضاي ديسک را به شکل سربار غير داده اي اشغال کنند .بخشي از اين سربار از اطالعاتي تشکيل مي شود که طي فرمت کردن ،بر روي ديسک نگهداري مي شود. فرمت کردن ،پيش از آنکه ديسک بتواند مورد استفاده قرار گيرد ،صورت مي پذيرد. 39 فرمت کردن موجب مي شود تا شکاف ( )gapو عالمت هاي هم زمان سازي ،بين فيلدهاي اطالعاتي قرار داده شود تا مکانيزم خواندن/نوشتن ،بين آنها تمايز قائل شود. 40 دستيابي به ديسک را مي توان به سه عمل فيزيکي متمايز تقسيم کرد که هر يک هزينه خود را دارد : )۱زمان پيگرد ()seek time )۲تأخير چرخشي ()rotational delay )۳زمان انتقال ()transfer time 41 ادامه مبحث حافظه جانبي و نرم افزار سي 42 زمان پيگرد عبارت است از زمان الزم انتقال بازوي دستيابي ،به سيلندر مناسب. 43 تأخير در چرخش عبارت است از زمان الزم براي چرخش ديسک ،تا سکتور مورد نظر زير هد خواندن/نوشتن قرار گيرد. 44 علي رغم افزايش کارايي ديسک ها ،سرعت شبکه ها به حدي باال رفته است که دستيابي به ديسک غالبا ً تنگناي مهمي در کل سيستم I/Oبه شمار مي رود. چند تکنيک براي مقابله با اين مشکل وجود دارد : )۱نواربندي )۲استفاده از ديسک RAM )۳حافظه نهان 45 نوارهاي مغناطيسي به دستگاه هايي تعلق دارند که دستيابي مستقيم به داده ها را فراهم نمي آورند ولي دستيابي ترتيبي به سرعت انجام مي شود .نوارها فشرده اند ،شرايط محيطي متفاوت را خوب تحمل مي کنند،نگهداري و حمل آنها آسان است و ارزانتر از ديسک ها هستند. 46 نقاط قوت CD-ROMشامل ظرفيت ذخيره سازي باال،بهاي کم و دوام آن است .نقطه ضعف اصلي آن اين است که جستجو در CD-ROMبسيار کند است،يعني غالبا ً هر جستجو نيم تا يک ثانيه طول مي کشد. 47 در قالب سرعت خطي ثابت (، )CLVسرعت چرخش ديسک هنگام خواندن لبه هاي بيروني ،کندتر از هنگام خواندن لبه هاي داخلي است. در سرعت زاويه اي ثابت (، )CAVديسک با شيارهاي متحدالمرکز و سکتورهاي مدور خود ،داده ها را با تراکم کمتري در شيارهاي خارجي نسبت به شيارهاي داخلي مي نويسد. 48 49 بافر I/Oسيستم ،به مديريت فايل اين امکان را مي دهد تا داده ها را در واحدهايي به اندازه سکتور يا بلوک بخواند يا بنويسد. 50 عمل کنترل عمليات ديسک توسط دستگاهي انجام مي شود که کنترلگر ديسک ناميده مي شود. 51 سيستم هاي I/Oتقريبا ً هميشه حداقل دو بافر دارند. يکي براي ورودي و ديگري براي خروجي .برخي سيستم هاي فايل از يک طرح بافردهي موسوم به استخر بافري ( )buffer spoolingاستفاده مي کنند. 52 با پراکنش ورودي ،با يک بار خواندن ،نه يک بار بافر بلکه مجموعه اي از بافرهايي که داده هاي يک بلوک بايد در آن ها پخش شود شناسايي مي شود. با تمرکز خروجي ،چند بافر را مي توان گردهم آورد و يکباره بر روي همه آنها نوشت ،بدين ترتيب الزم نيست آنها را در يک بافر خروجي کپي کرد. 53 هسته به نوبت به اين چهار جدول زير مراجعه مي کند تا اطالعاتي را که براي نوشتن در فايل موجود در ديسک نياز دارد به دست آورد : )۱جدول توصيف گر فايل )۲جدول فايل هاي باز )۳جدول تخصيص فايل )۴جدول گره هاي انديسي 54 55 اشاره گري از يک فهرست به اينود فايل را اتصال سخت ( )hard linkمي نامند و اتصال نرم ()soft link يا اتصال سمبوليک ،نام فايل را به جاي فايل واقعي ،به يک نام فايل ديگر مرتبط مي سازد. 56 سه نوع سيستم I/Oمتفاوت داريم : )۱سيستم I/Oبلوکي )۲سيستم I/Oکاراکتري )۳سيستم I/Oشبکه اي 57 براي هر دستگاه جانبي مجموعه اي از روال هاي جداگانه وجود دارد که راه انداز دستگاه ناميده مي شود. 58 • مفاهيم اساسي ساختار فايل • مديريت فايلهايي از رکوردها 59 مفاهيم اساسي ساختار فايل 60 واحد اصلي داده ها،فيلد است که حاوي يک مقدار داده است. فيلدها به صورت مجموعه اي از داده ها يا به صورت کپي هاي متعددي از يک فيلد (آرايه) يا ليستي از فيلدهاي متفاوت (رکورد)سازماندهي مي شوند. 61 هنگامي که رکوردي در حافظه نگهداري شد آن را يک شيء و فيلدهاي آن را اعضاي آن مي نامند. 62 راههاي فراواني براي افزودن ساختار به فايل وجود دارد تا هويت فيلد حفظ شود. چهار روش متداول عبارتند از : )۱ثابت کردن طول فيلدها )۲قرار دادن نشانگر طول فيلد در ابتداي هر فيلد )۳جدا کردن فيلدها با فاصل )۴استفاده از عبارت کليدي براي شناسايي فيلدها 63 رکورد مجموعه اي از فيلد ها است و مجموعه اي از رکوردها فايل را نشان مي دهند. 64 بعضي از روش هاي سازماندهي رکوردهاي فايل عبارتند از : )۱قابل پيش بيني کردن طول رکوردها بر حسب بايت )۲قابل پيش بيني کردن طول رکوردها بر حسب فيلدها )۳شروع هر رکورد با نشانگر طول )۴استفاده از انديس براي نگهداري آدرس ها )۵قرار دادن فاصل در انتهاي هر رکورد 65 دو روش براي نمايش طول رکورد وجود دارد : )۱طول رکورد به صورت يک عدد صحيح دو بايتي ، قبل از هر فيلد ديگر رکورد نوشته شود. )۲تبديل طول به يک کاراکتر رشته اي با استفاده از خروجي فرمت بندي شده 66 با روبرداري فايل مي توان بايت هاي واقعي نگهداري شده در آن را مشاهده کرد. 67  ++Cوراثترا در اختيار ق رار ميدهد ت ا چندينک الس ميت وانند از اعضا و متدهايمشترکاستفاده ک نند. 68 69 مديريت فايلهايي از رکوردها 70 هنگامي که کارايي جستجوهاي انجام شده در حافظه الکترونيک ي را توص يف م ي کنيم معموالً از تعداد مقايس ه هاي مورد نياز براي جستجو ،به عنوان واحد کار استفاده مي کنيم. 71 به طورکلي ،کار مورد نياز براي جستجوي ترتيبي ،در فايلي با nرکورد با nمتناسب است : حداکثر nمقايسه و به طور ميانگين n/2مقايسه مورد نياز است. 72 در تحليل و بحث درباره بلوک بندي رکورد چند چيز را بايد مورد توجه قرار داد : )۱گرچه بلوک بندي مي تواند منجر به بهبود چشمگير کارايي شود ،مرتبه عملکرد جستجوي ترتيبي را تغيير نمي دهد. )۲بلوک ساري ،اختالف ميان سرعت دستيابي در حافظه و زمان دستيابي در حافظه ثانويه را نشان مي دهد. )۳بلوک س ازي تعداد مقايس ه هاي ي را ک ه باي د در حافظه انجام شوند ،تغيير نمي دهد و احتماالً مقدار داده هاي انتقال يافته ميان حافظه و ديسک را افزايش مي دهد. )۴ب ا بلوک س ازي ،در زمان ص رفه جوي ي مي شود زيرا مقدار جستجو کاهش مي يابد. 73 جستجوي ترتيبي براي اکثر شرايط بازيابي زمان بسيار مي برد. اين که آيا جستجوي ترتيبي توصيه مي شود يا خير تا حد زيادي به چگونگي استفاده از فايل ،سرعت سيستم عامل در انجام جستجو ،و چگونگي ساختار فايل بستگي دارد. 74 متداول ترين ساختار فايل که در يونيکس وجود دارد ، ي ک فاي ل اس کي ب ا کاراکت ر خ ط جدي د ب ه عنوان فاصل رکورده ا و در ص ورت امکان ،فضاي خال ي به عنوان فاصل فيلدها است. 75 روش ديگري که با جس تجوي ترتيبي تفاوت بنيادي دارد ، دستيابي مستقيم است. هنگامي که بتوانيم مستقيما ً به ابتداي يک رکورد برويم و آن را به حافظه وارد کنيم ،به آن رکورد دستيابي مستقيم داريم. 76 • ادامه مبحث مديريت فايلهايي از رکوردها 77 غالبا ً الزم است از برخي اطالعات عمومي مربوط به فايل آگاه باشيم تا در آينده به استفاده از فايل کمک شود ،رکورد س رآيند غالبا ً در آغاز فاي ل قرار داده م ي شود ت ا اين نوع اطالعات را نگهداري کند. 78 هر فايل داراي يک رکورد سرآيند ( )headerاست که حاوي سه مقدار در پايين است : )۱اندازه سرآيند )۲تعداد رکوردها )۳اندازه هر رکورد 79 دو ساختار مختلف از رکوردها که حاوي فيلدهاي طول متغير در يک رکورد با طول ثابت است : )۱فايل حاوي سرآيند ۳۲بيتي و دو رکورد طول ثابت است که شامل فيلدهاي طول متغيري است که به NULLختم مي شوند. )۲فايل حاوي سرآيند ۶۶بيتي و رکوردهايي با طول ۶۸ بايت است که با فيلدي دو بايتي شروع مي شوند. 80 يک طراحي شيءگراي خوب ،براي ماندگار شدن اشياء بايد عملياتي براي خواندن و نوشتن مستقيم اشياء فراهم آورد. 81 تا کنون عمل نوشتن نيازمند به دو عمل جداگانه بود : )۱فشرده سازي در يک بافر )۲نوشتن بافر روي فايل 82 در اين بخش ،کالس recordfileرا معرفي مي کنيم که نوعي عمل خواندن را پشتيباني مي کند که شيئي از يک کالس را گرفته ،آن را در يک فايل مي نويسد .کاربرد بافرها در داخل کالس پنهان مي شود. 83 در بحث هايي که طي اين فصل و فصل قبل داشتيم به موارد زير پرداختيم : )۱رکوردهاي طول متغير )۲رکوردهاي طول ثابت )۳دستيابي ترتيبي )۴دستيابي مستقيم دو مورد اول ب ه س ازماندهي فاي ل و دو مورد آخ ر به دستيابي به فايل مربوط مي شود. 84 داده هايي مثل صوت ،تصاوير ،و اسناد به صورت فيلدها و رکوردها ذخيره نمي شوند. 85 اگر در زبان برنامه نويسي امکان داشته باشد ،مي توانيم اطالعات کاربردي بيشتري درباره ساختار فايل در سرآيند قرار دهيم. هنگامي که سرآيند فايل حاوي اين نوع اطالعات باشد ،گفته مي شود اين فايل ،خود -توصيفگر است. 86 شبه داده ها را مي توان با هر فايلي همراه ساخت ،که داده هاي اصلي آن نياز به اطالعات پشتيبان دارد . 87 تصوير راستر رنگي ،آرايه اي راس ت گوشه از نقاط رنگي يا پيکسل ها است ،که روي صفحه به نمايش در مي آيند. 88 انواع متفاوت فراواني از شبه داده ها وجود دارند که مي توانند با يک تصوير همراه شوند ،از جمله : )۱تعداد بيت هاي به کار رفته در توصيف هرپيکسل )۲ابعاد تص وير -تعداد پيکس ل ه ا ب ه ازاي ه ر سطر و تعداد سطرها )۳يک جدول جستجوي رنگ يا جعب ه رنگ ( )palletکه نشان مي دهد کدام رنگ بايد به هر مقدار پيکسل در تصوير نسبت داده شود. 89 متدهايي براي کار با تصاوير به عنوان اشياي خاصي وجود دارد : )۱نمايش يک تصوير پنجره اي در صفحه نمايش کنسول )۲همراه کردن يک تصوير با يک جدول جستجوي رنگ خاص )۳قرار دادن تص ويري بر روي ي ک تص وير ديگ ر و ايجاد يک تصوير ترکيبي )۴به نمايش در آوردن پياپي چند تصوير براي انيميشن ()animation 90 ايده دنبال کردن فايل ها براي قرار دادن دامن ه وسيعي از اشياي گوناگون ،اجتناب ناپذي ر اس ت ،بويژه براي کاربردهايي که نياز به مقدار زيادي از شبه داده ها يا ترکيب غير قابل پيش بيني از انواع متفاوت داده ها دارند ،زيرا به اي ن ترتي ب ديگ ر الزم نيس ت رکورده ا حتما ً از يک نوع باشند. 91 براي توصيف ديدي که يک برنامه کاربردي از اشياي داده اي دارد ،از اص طالح مدل داد هاي انتزاع ي استفاده نموديم. اي ن کار اس اسا ً ديدي کاربردگرا و درون -حافظه اي از اشياء است و در آن از فرمت فيزيکي اشياء به آن صورت که در فايل ها نگهداري مي شود چشم پوشي مي گردد. 92 • ادامه مبحث مديريت فايلهايي از رکوردها • سازماندهي فايلها براي کارايي 93 يکي از مزاياي استفاده از برچسب ها براي شناسايي اشياي موجود در فايل ها آن است که نيازي نيست که از پيش بدانيم همه اشيايي که نرم افزار با آنها سرو کار خواهد داشت به چه صورت خواهد بود. 94 اختالف ميان زبان ها ،س يستم هاي عامل ،و معماري ماشين ،سه مشکل اصلي هستند که هنگام توليد فايل هاي قابل حمل با آن ها مواجهيم. 95 چند راه حل براي دستيابي به قابليت حمل : )۱توافق بر سر يک فرمت فيزيکي استاندارد براي رکورد و وفاداري به آن )۲توافق بر سر رمزگذاري دودويي استاندارد براي عناصر داده اي )۳تبديل اعداد و متون )۴تبديل ساختارهاي فايل 96 سازماندهي فايلها براي کارايي 97 فشرده سازي يک فرايند دسته اي ( )batchاست که براي حذف حفره هاي خالي فايلي به کار مي رود که بارها و بارها مورد حذف و بهنگام سازي قرار گرفته است. 98 داليل زيادي براي کوچک کردن فايلها وجود دارد : )۱فايل هاي کوچکتر نياز به حافظه ي کمتري دارند که باعث صرفه جويي مي شود. )۲سريع تر انتقال داده مي شوند که زمان دسترسي را کوتاهتر مي کند يا به جاي آن مي توان با همان زمان دسترسي از پهناي باند کمتر و ارزان تر استفاده کرد. )۳به صورت ترتيبي ،سريع تر قابل پردازش هستند. 99 فشرده سازي داده ها عبارت است از رمزگذاري اطالعات در فايل ،به صورتي که جاي کمتري بگيرد. 100 تکنيک فشرده سازي که در آن تعداد بيت ها با استفاده از يک نمادگذاري فشرده تر کاهش مي يابد يکي از روش هاي فشرده سازي است که به عنوان کاهش زوايد شناخته مي شوند. 101 آرايه هاي اسپارس براي نوعي فشرده سازي به نام رمزگذاري طول رانش مناسب اند .ابتدا مقدار خاصي را براي شروع رمزگذاري طول اجرا در يک بايت ذخيره کرده سپس الگوريتم آن را اجرا مي کنيم. 102 الگوريتم آ رايه هاي اسپارس را به صورت زير اجرا مي کنيم : )۱پيکسل هاي تشکيل دهنده ي شکل را خوانده آنها به ترتيب در فايل ذخيره کن. )۲جايي که يک مقدار پيکسل بيش از يک بار پشت سر هم تکرار شود اين سه بايت را به ترتيب جايگزين کن : الف) نشان دهنده کد طول اجرا ب ) مقدار پيکسلي که تکرار شده ج ) تعداد دفعاتي که اين مقدار تکرار شده است. 103 نوع ديگري از فشرده سازي کدهاي با طول متغير را بسته به تعداد دفعات ظاهر شدن مقادير ،به آن مقادير نسبت مي دهد. به مقاديري که بيشتر تکرار مي شوند کدهاي کوتاهتري نسبت داده مي شود بنابر اين جاي کمتري مي گيرند .کدهاي هافمن مثالي از کدهاي با طول متغير هستند. 104 راهي ديگر براي صرفه جويي فضا در يک فايل ،بازيابي فضا در آن فايل پس از تغيير يافتن فايل است. 105 تغييرات فايل به سه شکل انجام مي شود : )۱اضافه کردن رکورد )۲بهنگام سازي رکورد )۳حذف رکورد 106 متراکم کردن فايل از طريق پيدا کردن مکان هايي در فايل که حاوي هيچ داده اي نيستند و از بين بردن اين مکان هاي خالي فايل ها را کوچکتر مي کند .و مکان هاي خالي هم وقتي در فايل ايجاد مي شود که رکوردي را حذف مي کنيم. 107 متراکم کردن فايل آسان ترين و رايج ترين روش هاي بازيابي فضا است. 108 به طور کلي براي فراهم کردن مکانيسمي براي حذف رکوردها و ب ه دنبال آ ن اس تفاده دوباره از فضاي آزاد شده باي د بتوانيم دو مسئله را تضمين کنيم : )۱رکوردهاي حذف شده ب ه طور خاص ي عالمت گذاري شوند. )۲بتوانيم محلي را ک ه توسط رکوردهاي حذف شده اشغال شده بود پيدا کني م ت ا بتواني م براي اضافه کردن رکوردهاي جديد از اين محل ها استفاده کنيم. 109 • ادامه مبحث سازماندهي فايلها براي کارايي • شاخص گذاري 110 براي بازيابي سريعتر فضا به وارد زير نيازمنديم : )۱راهي که بالفاصله بدانيم که حفره هاي خالي در فايل وجود دارد يا نه )۲راهي که اگر چنين حفره اي وجود دارد مستقيما ً به آن پرش کنيم. 111 استفاده از ليست هاي پيوندي براي پيوند دادن تمام رکوردها هر دو نياز فوق را برآورده مي کند. 112 آسان ترين راه براي کار کردن با ليست استفاده از آن به صورت پشته است. پشته ليستي است که در آن اضافه و حذف گره ها از يک انتهاي ليست انجام مي شود. 113 براي بازيابي رکوردها از طريق ليست پيوندي به موارد زير نياز داريم : ) ۱راهي براي پيوند دادن رکوردهاي حذف شده و تبديل آنها به يک ليست )۲الگوريتمي براي اضافه کردن رکوردهاي حذف شده به ليست )۳الگوريتمي براي پيدا کردن و خارج کردن يک رکورد از ليست هنگامي که مي خواهيم از آن رکورد استفاده کنيم. 114 براي مقابله با پراکندگي خارجي يک روش متراکم کردن فايل است و دو راه ديگر به قرار زير است: )۱اگر دو حفره رکورد در ليست به صورت فيزيکي کنار هم قرار گيرند آنه ا را با هم يکي مي کنيم ت ا يک حفره رکورد بزرگتر ايجاد شود .به اين کار ادغام حفره ها در فايل ميگوييم. )۲س عي م ي کني م پراکندگ ي را ب ه حداق ل برس انيم .ب ه اين ترتي ب ک ه ي ک راه برد انتخاب ج ا را در نظ ر م ي گيري م که برنامه با استفاده از آن يک حفره رکورد را از ليست انتخاب کند. 115 هنگامي که نياز داريم يک حفره رکورد را از ليست خارج کنيم با شروع از ابتداي فايل عمل جستجو را انجام مي دهيم تا رکوردي به اندازه کافي بزرگ پيدا کنيم يا به انتهاي ليس ت برس يم .اي ن راه برد انتخاب ج ا به عنوان راهبرد اولين جاي مناسب( )first fitناميده مي شود. 116 س ه مشکل اس اسي مربوط ب ه مرتب س ازي و جستجوي دودويي عبارتند از : )۱جس تجوي دودوي ي نياز ب ه بي ش از ي ک يا دو دسترسي به ديسک دارد. )۲نگهداري ي ک فاي ل ب ه ص ورت مرت ب شده خيلي گران تمام مي شود. )۳مرتب سازي داخلي تنها در مورد فايل هاي کوچک عملي است. 117 مرت ب س ازي کليدي ک ه گاه ي ب ه آ ن مرت ب س ازي با برچسب مي گويند بر اين ايده استوار است که وقتي فايلي را در حافظه مرتب مي کنيم تنها چيزيکه واقعا ً به آن نياز داريم کليد رکوردها است. 118 عيب مرتب سازي کليدي اين است که مرتب کردن فايلي با nرکورد نياز به nدستيابي تصادفي به فايل اصلي دارد که مي تواند بسيار بيشتر از خواندن ترتيبي همان تعداد رکورد وقت بگيرد. 119 شاخص گذاري 120 همه شاخص ها بر اساس يک مفهوم اصلي واحد عمل مي کنند :کليدها و آدرس فيلدها. 121 انواع شاخص هايي که در اين فصل بررسي مي کنيم شاخص ساده ناميده مي شوند زيرا با استفاده از آرايه هاي ساده اي از ساختمان ها نشان داده مي شوند ،که حاوي کليدها و آدرس فيلدها هستند. 122 چون شاخص ها به طور غير مستقيم عمل مي کنند ، بدون دستکاري محتويات فايل ،به فايل نظم و ترتيب مي بخشند. 123 کاتالوگ کارتي در واقع مجموعه اي از سه شاخص است که هر کدام از يک فيلد کليد متفاوت استفاده مي کنند و همه انها از يک شماره کاتالوگ يکسان به عنوان فيلد آدرس بهره مي گيرند. 124 بنابراين کاربرد ديگر شاخص بندي اين است که مي توان از طريق مسيرهاي گوناگوني به فايل دست يافت. 125 در جستجوي دودويي الزم است امکان پرش به وسط فايل را داشته باشيم. 126 • ادامه مبحث شاخص گذاري 127 راه ديگر براي مرتب سازي ،ايجاد شاخص براي فايل است. 128 ساختار شيء شاخص بسيار ساده است. اين ساختار ليستي است که هر عنصر آن دو فيلد دارد: يک فيلد کليد و يک فيلد براي آفست بايت. 129 عملياتي که براي يافتن داده هاي مورد نظر ،از طريق شاخص الزمند عبارتند از : )۱ايجاد فايل داده ها و شاخص خالي اوليه ) ۲باز کزدن فايل شاخص در حافظه ،قبل از به کارگيري آن ) ۳نوشتن فايل شاخص بر روي ديسک ،پس از به کارگيري آن )۴افزودن رکوردهايي به فايل و داده ها )۵حذف رکوردها از فايل داده ها )۶بهنگام کردن رکوردها در فايل داده ها )۷بهنگام کردن شاخص براي انعکاس تغييرات به عمل آمده در فايل داده ها. 130 مزيت بزرگي که روش شيء گرا دارد آ ن اس ت که براي اجراي اين عمليات به هرچه نياز داشته باشيم مي توانيم در متدهاي کالس خود بيابيم. 131 در ايجاد فايل ها بايد دو فايل ايجاد شوند : )۱فايل داده ها براي نگهداري اشياي داده اي )۲فايل شاخص براي نگهداري شاخص کليد اوليه 132 بهنگام سازي رکوردها به دو صورت انجام مي شود : )۱بهنگام سازي ،تعداد فيلد و کليد را تغيير مي دهد. )۲بهنگام سازي ،در فيلد و کليد تأثير نمي گذارد. 133 آشکارترين بهينه سازي ،استفاده از جستجوي دودويي در متد findاست که توسط : ‏insert , search شود. 134 و remove به کار گرفته مي منب ع ديگ ر بهين ه س ازي ،چنانچ ه رکورد شاخ ص تغيير نکرده باشد ،نوشتن درباره رکورد شاخص در فايل شاخص است. 135 دستيابي به شاخص روي ديسک داراي معايب زير است : )۱جس تجوي دودوي ي شاخ ص ب ه جاي آنک ه ب ا سرعت حافظه صورت پذيرد ،نياز به چندين پيگرد دارد. )۲ترتي ب مجدد شاخ ص ک ه از حذف يا افزودن رکورد ناش ي م ي شود نياز ب ه جاب ه ج ا کردن ي ا مرت ب سازي رکوردها در حافظه ثانويه دارد که اين کار ميليونها بار گران تر از اجراي اين عمليات در حافظه است. 136 هرگاه يک شاخص ساده در حافظه جا نشود بايد از موارد زير استفاده کرد : )۱در صورتي که سرعت دستيابي در اولويت قرار داشته باشد ،از سازماندهي درهمسازي استفاده شود. )۲در صورتي که به هر دو نوع دستيابي کليدي و ترتيبي نياز داشت ه باشي د ،از ي ک شاخ ص چن د س طحي ب ا ساختار درختي نظير درخت Bاستفاده شود. 137 شاخص هاي ساده نسبت به استفاده از فايل داده اي که بر حسب کليد مرتب شده اند مزاياي چشمگيري دارد : )۱شاخص ساده استفاده از جستجوي دودويي را براي دستيابي کليدي به يک رکورد در فايلي که طول رکوردهاي آن متغير است امکان پذير مي سازد. )۲اگر ورودي هاي شاخص بسيار کوچکتر از رکوردهاي فايل داده ها باشد ،مرتب س ازي و نگهداري شاخص نسبت به مرتب سازي و نگهداري فايل داده ها زمان کمتري مي برد. )۳اگر در فايل داده ها رکوردهايي وجود دارند که در جاي خود مستقر هستند ،با استفاده از شاخص مي توان ترتيب کليدها را بدون جابجايي رکوردهاي داده ها عوض کرد. 138 هنگاميک ه شاخ ص ثانوي ه اي موجود باش د ،افزودن يک رکورد به فايل به معناي افزودن يک ورودي شاخص ثانويه است .زمان الزم برا انجام اين کار بسيار مشابه زمان الزم براي افزودن ورود يي به شاخص اوليه است. 139 يک اختالف مهم شاخص ثانويه و شاخص اوليه آن است که شاخص ثانويه مي تواند حاوي کليدهاي دوگانه باشد. 140 حذف ي ک رکورد معموالً ب ه معناي حذف تمامي آدرس هاي آن رکورد در سيستم فايل است. بنابراين حذف رکوردي از فايل داده ها نه تنها به معناي حذف ورودي مربوط در شاخص اوليه بلکه به معناي حذف همه ورودي هاي موجود در همه شاخص هاي ثانويه اي است که به اين ورودي از شاخص اوليه رجوع مي کنند. 141 مشکل اين است که شاخص هاي ثانويه همانند شاخص اوليه به ترتيب کليدها نگهداري مي شوند .در نتيجه حذف يک ورودي شامل ترتيب مجدد ورودي هاي موجود ،به منظور بستن فضاي باقيمانده از حذف است. 142 • ادامه مبحث شاخص گذاري • پردازش کمک ترتيبي و مرتب سازي فايل هاي بزرگ 143 بهنگام سا زي فايل داده ها فقط هنگامي شاخص ثانويه را تحت تأثير قرار مي دهد که کليد اوليه يا ثانويه تغيير يابند .که سه وضعيت ممکن است پيش بيايد : )۱بهنگام سازي باعث تغيير کليد ثانويه مي شود. )۲بهنگام سازي باعث تغيير کليد اوليه مي شود. )۳بهنگام سازي محدود به فيلدهاي ديگر 144 س اختارهاي شاخص ثانوي ه اي ک ه ت ا کنون ارائ ه کردي م دو مشکل دارند : )۱هربارکه رکورد جديدي به فايل افزوده مي شود ،بايد فايل شاخص را دوباره مرتب کنيم ،حتي اگر رکورد جديد به يک کليد ثانويه موجود مربوط باشد. )۲اگر کليدهاي ثانويه وجود داشته باشد ،فيلد کليد ثانويه براي هر ورودي تکرار مي شود .اين کار باعث هدر رفتن فضا مي شود. 145 درسيستم فايلي که طي اين فصل طراحي کرديم ، انقياد کليدهاي اوليه به آدرس در زمان ايجاد شدن فايل ها رخ مي دهد ول ي کليدهاي ثانوي ه در زمان اس تفاده ،به آدرس خود پيوند مي يابند. 146 پردازش کمک ترتيبي و مرتب سازي فايل هاي بزرگ 147 عمليات کمک ترتيبي شامل پردازش هماهنگ دو يا چند ليست ترتيبي براي ايجاد يک ليست خروجي است. گاهي پردازش منجر به ادغام يا اتحاد اقالم موجود در ليس ت هاي خروج ي م ي شود ،گاه ي هدف ،تطاب ق يا جايگذاري اقالم در ليست ها است ،گاهي نيز عمليات شامل ترکيبي از تطابق و ادغام مي شود. اي ن نوع عمليات روي ليس ت هاي ترتيبي ،مبناي بسياري از پردازش هاي فايل ها را تشکيل مي دهند. 148 گرچه روال همخواني بسيار ساده به نظر مي رسد ،براي آن که اين روال بهتر عمل کند به چند نکته بايد توجه داشت : )۱آماده سازي )۲دستيابي به عضو بعدي ليست )۳همزمان سازي )۴کنترل شرايط پايان فايل )۵تشخيص خطاها 149 اگر قرار باشد تعداد زيادي از ليست ها با هم ادغام شوند ،مي توان به جاي حلقه مقايسه ها از درخت انتخاب استفاده کرد. 150 مرتب سازي در حافظه شامل سه مرحله است : )۱خواندن کل فايل از روي ديسک به حافظه )۲مرت ب س ازي رکورده ا ب ا اس تفاده از يک روال مرتب سازي استاندارد ،مثل مرتب سازي shell )۳نوشتن دوباره فايل روي ديسک 151 آيا يک الگوريتم مرتب سازي داخلي وجود دارد که به قدر کاف ي س ريع باش د و بتوان د مرت ب سازي اعداد را بالفاصله پس از خوانده شدن آنها آغاز کند و منتظر قرار گرفتن کل فايل در حافظه نشود؟ بله ،نام آن مرتب سازي هرمي ( )heapsortاست و مبتني بر همان اصل درخت انتخاب است. 152 هرم درختي دودويي با ويژگي هاي زير است : )۱ه ر گره داراي کليدي اس ت ک ه آ ن کلي د بزگت ر يا مساوي کليد واقع در گره پدرش است. )۲يک درخت دودويي کامل است. )۳به خاطر ويژگيهاي ۱و ، ۲در نگهداري درخت مي توان آراي ه اي اختص اص داد ک ه در آن ،گره ريشه ،انديس ۱و انديسهاي فرزندان چپ و راست گره i ،به ترتيب برابر با i۲و i۲ + ۱باشند. 153 154 الگوريتم مرتب سازي هرمي دو بخش دارد: ابتدا هرم را ايجاد مي کنيم سپس کليدها را به صورت مرتب شده در خروجي قرار مي دهيم. 155 بازيابي ترتيبي کليدها به صورت زير انجام مي شود : )۱تعيين مقدار کلي د موجود در اولين موقعيت هرم .اين مقدار کوچکترين مقدار هرم است. )۲انتقال بزرگترين مقدار هرم به اولين محل آن و کم کردن يک واحد از تعداد عناصر. )۳ترتيب دوباره هرم .با اينکار بزرگترين عنصر با فرزند کوچکش جابجا مي شود. هر بار که اين س ه مرحل ه اجرا مي شود ،کوچکتري مقدار بازيابي شده از هرم حذف مي گردد. 156 مرتب سازي کليدي دو نارسايي دارد : )۱هنگاميکه کليدها مرتب سازيمي شوند ،بايد زمان زيادي ص رف اي ن موارد شود .پيگرد هر رکورد در رکوردهاي مرتب شده ،خواندن هر رکورد به حافظه و نوشتن آن روي فايل مرتب شده جديد شود. )۲در مرتب سازي کليدي ،اندازه فايلي که قابل مرتب سازي اس ت ب ه تعداد جف ت کلي د/اشاره گري ک ه در حافظ ه جا شود ،محدود مي شود .در نتيجه هنوز نمي تواني م فايل هاي واقعا ً بزرگ را مرتب سازي کنيم. 157 رانش داراي ويژگي هاي زير است : )۱واقعا ً قادر به مرتب سازي فايل هاي بزرگ هست و به فايل هايي به هر اندازه قابل بسط است. )۲خواندن فايل ورودي در مرحل ه ايجاد رانش ،ترتيبي است و لذا بسيار سرعتر از ورودي است ،زيرا ورودي به ازاي هر رکورد نياز به پيگرد دارد. )۳خواندن هر رانش طي مرحل ه ادغام و نوشتن رکوردهاي مرتب شده نيز ترتيبي است. )۴اگر براي بخشي از ادغام که در حافظه انجام مي شود از مرتب سازي هرمي استفاده شود مي توانيم اين عمليات را با I/Oهمپوشاني کنيم تا زمان ادغام افزايش پيدا نکند. )۵چون I/Oتا حد زيادي ترتيبي است ،در صورت نياز مي توان براي هر دو عمليات ورودي و خروجي از نوار نيز استفاده کرد. 158  I/Oچهار ب ار اجرا ميگ ردد. در مرحله مرتب سازي : )۱خواندن همه رکوردها به حافظه براي مرتب سازي و تشکيل رانش ها )۲نوشتن رانش هاي مرتب شده روي ديسک. در مرحله ادغام : )۱خواندن رانش هاي مرتب شده به حافظه براي ادغام )۲نوشتن فايل مرتب شده روي ديسک 159 • ادامه مبحث پردازش کمک ترتيبي و مرتب سازي فايل هاي بزرگ 160 يک اختالف عمده ميان مرحله مرتب سازي و مرحله ادغام ،در تعداد دستيابي ترتيبي (در مقابل دستيابي مستقيم) است. با استفاده از مرتب سازي هرمي براي ايجاد رانش هايي در مرحله مرتب سازي ،مي توان تضمين نمود که همه I/Oها از يک لحاظ ترتيبي است. 161 به طور خالصه چون مرحله ادغام تنها مرحله اي است که در آن مي توان بازدهي را با بهبود بخشيدن به روش کار ،افزايش داد بنابر اين بر آن بيشتر تأکيد داريم. 162 با بزرگ شدن فايل ها زمان الزم براي مرتب سازي ادغامي به سرعت افزايش مي يابد .براي کاهش اين زمان چند راه وجود دارد : )۱تخصيص سخت افزار بيشتر نظير ديسک گردان ،حافظه و کانال هاي I/O )۲اجراي ادغام در بيش از يک مرحله ،کاهش دادن مرتبه هر ادغام و افزايش دادن اندازه بافر براي هر رانش )۳افزايش طول رانش هاي مرتب شده از لحاظ الگوريتمي )۴يافتن راههايي براي همپوشاني عمليات I/O 163 در اين بخش سه تغيير ممکن در پيکربندي سيستم را در نظر مي گيريم که مي تواند زمان مرتب سازي را به طور چشمگيري کاهش دهد : )۱افزايش مقدار حافظه )۲افزايش تعداد ديسک گردان ها )۳افزايش تعداد کانال هاي I/O 164 165 هدف اصلي اين مرتب سازي ادغامي آن است که قادر باشيم فايلهايي را مرتب سازي کنيم که در حافظه جا نمي شوند. 166 در ادغام چند مرحله اي ،سعي نمي کنيم همه رانش ها را به يکباره ادغام کنيم .بلکه رانش هاي اوليه را به گروههاي کوچک تقسيم کرده ،رانش هاي موجود در اين گروه ها را جداگانه ادغام مي کنيم. 167 اساس انتخاب جايگزيني ،اين ايده است : انتخاب هميشگي کليدي از حافظه که داراي کمترين مقدار باشد ،قرار دادن آن کليد در خروجي ،و سپس تعويض آن با يک کليد جديد از ليست ورودي. 168 الگوريتم انتخاب جايگزيني را مي توان به طريق زير پياده سازي نمود : )۱خواندن مجموعه اي از رکوردها و مرتب سازي آنها با استفاده از مرتب سازي هرمي )۲به جاي نوشتن کل هرم اوليه به شکل مرتب شده فقط رکوردي را مي نويسيم که کليد آن داراي کمترين مقدار است. 169  )۳آوردن يک رکورد جديد و مقايسه مقدار کليد آن با مقدار کليدي که به تازگي در خروجي قرار گفته است. ال ف) اگ ر مقدار کلي د جدي د بزرگت ر باش د رکورد جدي د را در محل مناسب آن در هرم اوليه ،به همراه رکوردهايي قرار مي دهيم که از خروجي گزينش مي شوند. ب) اگر مقدار کليد رکورد جديد کمتر باشد ،رکورد را در يک هرم ثانويه از رکوردها با مقادير کليدي کمتر از آنهايي که پيش از اين نوشته شده اند قرار مي دهيم. )۴تا هنگاميکه رکوردي در هرم اوليه باقي باشد و رکوردهايي براي خواندن وجود داشته باشد مرحله ۳را تکرار مي کنيم. 170 گزينش جايگزيني ابزاري سودمند براي فايل هاي ورودي است که قدري مرتب هستند و اين گزينش فرصتي براي صرفه جويي در زمانهاي انتقال و پيگرد فراهم مي آورد که روشهاي مرتب سازي حافظه اي فاقد آن است. 171 در گزينش جايگزيني اگر دو ديسک در اختيار داشته باشيم ،بايد حافظه را نيز طوري پيکربندي کنيم که از آنها بهره برداري شود .حافظه را چنين پيکربندي مي کنيم : يک بافر ورودي و يک بافر خروجي اختصاص مي دهيم ت ا بافرده ي دوگان ه امکان پذي ر گردد و بقي ه حافظ ه را به تشکيل درخت انتخاب اختصاص دهيم. 172 اختصاص دادن بيش از يک پردازنده به يک کار امري است متداول که به حاالت زير امکان پذير است : )۱کامپيوترهاي بزرگ که بسياري از آنها مقدار زيادي از وقت خود را صرف مرتب سازي مي کنند ،معموالً داراي دو يا چند پردازنده هستند که همزمان روي بخش هاي متفاوت يک مسئله کار مي کنند. )۲پردازنده هاي برداري و آرايه اي را مي توان طوري برنامه ريزي کرد که انواع گوناگون الگوريتم مرتب سازي را سريعتر از پردازنده هاي اسکالر اجرا کند. )۳ماشين هاي موازي انبوه ،هزاران و شايد ميليونها پردازنده دارند که مي توانند مستقل از هم کار کنند و در عين حال به شيوه هاي پيچيده با هم ارتباط برقرار کنند. )۴شبکه هاي محلي بسيار سريع و نرم افزارهاي ارتباطي ،ارسال بخش هاي متفاوتي از يک فرايند به چند ماشين متفاوت را امکان پذير مي سازد. 173 اگر در سيستمي برنامه نويسي چندگانه امکان پذير باش د زمان ک ل براي I/Oممک ن اس ت طوالن ي تر باشد ،زيرا کارما بايد منتظر بماند تا کارهاي ديگر نيز I/Oخود را انجام دهند. 174 يکي از داليل برنامه ريزي چندگانه آن است که به س يستم عام ل امکان دهي م ت ا راههاي ي براي افزايش بازدهي کل سيستم ،با هم پوشاني پردازش و I/Oدر ميان امور متفاوت بيابد. 175 • ادامه مبحث پردازش کمک ترتيبي و مرتب سازي فايل هاي بزرگ • شاخص بندي چند سطحي و درختهاي B 176 ليست کاملي از مجموع ه جديد ابزاهايي که کارايي مرتب سازي خارجي را بهبود مي بخشند شامل موارد زيراست : )۱براي مرتب سازي درون حافظه اي ،از مرتب سازي هرمي براي تشکيل ليست اوليه عناصر مرتب شده در يک رانش استفاده مي کنيم. )۲استفاده از حداکثر حافظه ممکن )۳اگ ر تعداد ران ش هاي اولي ه چنان بزرگ باش د ک ه زمان کل پيگرد و چرخش ،بسيار بزگتر از زمان انتقال کل باشد از ادغام چندمرحله اي استفاده مي کنيم. )۴اس تفاده از گزين ش جايگزين ي براي تشکي ل ران ش هاي اولي ه را در نظر بگيريم. ) ۵از بيش از يک ديسک گردان و کانال I/Oاستفاده مي کنيم. )۶عناصر بنيادي مرتب سازي خارجي و هزينه هاي نسبي آنها را به خاطر مي س پاريم و ب ه دنبال راه هاي ي براي بهره بردن از معماري ه ا و سيستمهاي 177 جديد ،نظير پردازش موازي مي گرديم. درادغام موازنه شده دوجانبه ،توزيع اوليه بايد روي دو نوارگردان صورت پذيرد و در هر مرحله از ادغام ،به جز آخري خروجي بايد روي دو نوارگردان صورت گيرد. اين ادغام ساده ترين الگوريتم ادغام نواري است. 178 ايده هاي استفاده از الگوريت م هاي ادغام مرتبه باالتر و ادغام رانش ها از روي يک نوار در چند مرحله مبناي دو روش معروف براي ادغام ،موسوم به ادغام چند مرحله اي يا ادغام آبشاري است. به طور کلي اين ادغام ها در ويژگي هاي زير با هم مشترکند : )۱توزيع اوليه رانش ها چنان است حداقل ادغام اوليه يک ادغام j -1جانبه است که در آن jتعداد نوارگردان ها است. )۲توزيع رانش ها در ميان نوارها چنان است که نوارها غالبا ً حاوي تعداد متفاوتي از رانش ها هستند. 179 چون ديسک ها دستگاههاي دستيابي مستقيم هستند ادغام هاي با مرتب ه بسيار بزرگ را مي توان انجام داد ،حتي اگر فقط يک ديسک گردان وجود داشته باشد. چون نوارها دستگاه هاي دستيابي مستقيم نيستند براي هر ران ش اضاف ي ک ه بخواهي م ادغام کني م ب ه يک نوارگردان اضافي نياز داريم. بنابر اين ديسک ها بهترند. 180 شاخص بندي چند سطحي و درختهاي B 181 مشکل اصلي نگهداشتن شاخص در حافظ ه جانبي اين است که دستيابي به حافظه جانبي کند است. اين مشکل مي تواند به دو مشکل ويژه تقسيم شود : )۱جستجو بر حسب شاخص بايد سريعتر از جستجوي دودويي باشد. )۲درج وحذف بايد با سرعت جستجو کردن انجام شود. 182 درخت جستجوي دودويي چه اشکالي دارد؟ )۱براي شاخ ص بندي روي ديس ک سرعت الزم را ندارد. )۲يک راهبرد مؤثر براي موازنه کردن درخت وجود ندارد. 183 تالشهايي براي حل مشکالت درخت جستجوي دودويي انجام گرفت که دو تا از آنها عبارتند از : )۱درخت هاي AVL )۲درخت هاي دودويي صفحه صفحه 184 درخت AVLدرختي با ارتفاع موازنه شده است. يعني اينکه ،اختالف مجاز ميان هر دو زيردرخت ک ه ريش ه مشترک ي دارند محدودي ت دارد و حداکثر تفاوت مجاز ۱است. 185 186 دو مزيت که درخت هاي AVLرا با اهميت مي کنند عبارتند از : )۱ب ا تعيي ن کردن حداکث ر تفاوت مجاز در ارتفاع هر دو زيردرخت ،درخت هاي AVLحداقل کاراي ي را در جستجو تضمين مي کنند. )۲براي اينکه هنگام درج در درخت ، AVLويژگي خود را حفظ کند ،مستلزم چهار نوع چرخش است. 187 درخت دودويي صفحه اي ،سعي مي کند با قرار دادن چندين گره دودويي در يک صفحه ديسک ،مشکل را حل کند. 188 189 واضح است که تقسيم کردن درخت به چندين صفحه امکان جستجوي سريعتر در حافظ ه جانبي را فراهم مي کند وبه دست آوردن اطالعات را سريعتر از هر روش ديگر دستيابي با استفاده از کليد امکان پذير مي کند. 190 مشکل اصلي درخت هاي صفحه اي هنوز هم استفاده از ديسک است. 191 درخت هاي Bشاخص هاي چند سطحي هستندکه مشکل هزينه خطي درج و حذف کردن را حل مي کنند. اين ويژگي باعث جذابيت درخت Bمي شود ،زيرا اکنون درخ ت هاي Bروش اس تاندارد شاخ ص سازي هستند و از پايين به باال ساخته مي شوند و عملياتي نظي درج و حذف ،در حافظه روي گره هاي درخت Bاعمال مي شود. 192 ه مبحث شاخص بندي چند سطحي و درخته 193 جستجو در درخت : B )۱به صورت تکراري عمل مي کنند. )۲در دو مرحله عمل مي کنند : الف) به صورت يک درميان روي کل صفحات ب) در داخل صفحات 194 در مورد فرايند درج کردن ،تقسيم کردن و ارتقاء مالحظات زير را در نظر مي گيريم : )۱با جستجويي که تا سطح برگ پيش مي رود شروع مي شود. )۲بع د از پيدا کردن مح ل درج در سطح برگ ،کار درج ،تشخيص سر ريز و تقسيم کردن از پايين به سمت باال پيش مي رود. 195 از مرتب ه درخت Bبه عنوان حداقل تعداد کليدهايي که مي تواند در يک صفحه درخت وجود داشته باشد تعريف مي شود. 196 پايين ترين سطح کليدها در درخت Bرا برگ مي نامند. 197 با استفاده از تعاريف ارائه شده از مرتبه و برگ ،مي توانيم خواص يک درخت Bاز مرتبه mرا دقيقا ً بيان کنيم : )۱هر صفحه حد اکثر mفرزند دارد. ‏m )۲هر صفحه ،به جز ريشه و برگ ها ،حداقل] [ 2فرزند دارد. )۳ريشه حداقل دو فرزند دارد. )۴تمام برگ ها در يک سطح قرار دارد. )۵سطح برگ ها ،يک شاخص کامل و مرتب شده از فايل داده هاي مربوط به درخت را ايجاد مي کند. 198 تضمين اين که درخت پهن و کم عمق باشد ،نه باريک و عميق ،مربوط به اين قوانين است : )۱هر صفحه به جز ريشه و برگ ها حداقل ]m 2 [ فرزند دارد. ‏m )۲هر صفحه حاوي حداقل] [2و حداکثر mکليد است. 199 قوانين حذف کليد kاز گره nدر يک درخت Bبه اين ترتيبند : )۱اگر تعداد کليدهاي nبيشتر از حد اقل کليدهاي مجاز است و kبزرگترين کليد در nنيست ،کافي است kرا از nحذف کنيد. )۲اگر تعداد کليدهاي nبيشتر از حد اقل کليدهاي مجاز است و kبزرگترين کليد در nاست k،را حذف کنيد و شاخص هاس سطح باالتر را متناسب با بزرگترين کليد جديد در nتغيير دهيد. )۳اگ ر تعداد کليدهاي nدقيقا ً برابر حداق ل کليدهاي مجاز اس ت و يکي از برادرهاي nبه اندازه کافي خالي است nرا در برابرش ادغام کنيد و يک کليد را از گره مادر حذف کنيد. )۴اگ ر تعداد کليدهاي nدقيقا ً برابر حداق ل کليدهاي مجاز اس ت و يکي از برادرهاي nکليدهاي زيادي دارد ،با انتقال دادن بعضي از کليدها از يک برادر به ، nکليدها را دوباره توزيع کنيد و شاخص هاي سطح باالتر را متناسب با بزرگترين کليدهاي جديد گره هاي دستکاري شده تغيير دهيد. 200 توزيع دوباره در هنگام درج ،راهي براي جلوگيري يا حداقل به تعويق انداختن ايجاد صفحات جديد است. 201 به جاي تقسيم کردن يک صفحه پر و ايجاد دو صفحه نيمه پر ،توزيع دوباره اين امکان را به ما مي دهد که تعدادي از کليدهاي سرريز شده را به صفحه ديگري انتقال دهيم. بنابراي ن اس تفاده از توزي ع دوباره ب ه جاي تقسيم کردن باعث مي شود که درخت Bاز فضاي حافظه جانبي به طور مؤثرتر استفاده کند. 202 يک نوع جديد از درخت Bرا به عنوان درخت *Bتعريف مي کنيم که خواص آن به اين ترتيب است : )۱هر صفحه حداکثر mفرزند دارد. 2m 1 )۲هر صفحه به جزريشه حداقل ] [ 3فرزند دارد. )۳ريشه حداقل دو فرزند دارد. )۴تمام برگ ها در يک سطح قرار دارند. 203 فرايند دستيابي به ديسک براي خواندن صفحه اي که در بافر وجود ندارد ،نقص صفحه اي ( )page faultناميده مي شود. 204 دو علت براي نقص صفحه وجود دارد : )۱هيچگاه تا کنون از آن صفحه استفاده نکرده ايم. )۲آ ن ص فحه قبالً در باف ر بوده اس ت ام ا صفحه جديدي جايگزين آن شده است. 205 ي ک راه براي مورد دوم ص فحه قب ل اي ن اس ت که صفحه اي را که زودتر از همه مورد استفاده قرار گرفته است جايگزين کنيم ،اين روش جايگزيني LRU (List، ) Recently Usedناميده مي شود. 206 استفاده از رکوردهاي با طول متغير باعث صرفه جويي در فضا و در نتيجه کاهش ارتفاع درخت Bمي شود. 207 ي به فايل‌هاي ترتيبي شاخص‌دار و درخت‌ه 208 دستيابي به فايل هاي ترتيبي شاخص دار و درخت هاي B 209 ساختارهاي فايل ترتيبي انديس دار ،امکان انتخاب از ميان دو ديدگاه متفاوت نسبت به فايل را فراهم مي آورند : )۱شاخص دار :فايل را مي توان به عنوان مجموعه اي از کليدها در نظر گرفت که توسط کليد ،شاخص بندي شده اند. )۲ترتيبي :به فايل مي توان دستيابي ترتيبي داشت و رکوردها را به ترتيب توسط کليد بازگرداند. 210 مجموعه اي از رکوردها که به طور فيزيکي توسط کليدها مرتب شده اند و رکوردهايي به آن اضافه و يا از آن حذف مي شوند .چنين مجموعه اي از رکوردها را مجموعه ترتيبي مي ناميم. 211 هنگاميکه رکوردها را بلوک بندي مي کنيم ،بلوک واحد اصلي ورودي و خروجي مي شود. 212 همانند درخت هاي ، Bدرج رکوردهاي جديد در يک بلوک مي تواند باعث سرريز شدن بلوک شود. 213 مشکل سرريز شدن را مي توان توسط يک فرايند شکستن بلوک ها کنترل کرد که شبيه فرايند شکس تن بلوک ها در درخت هاي Bاست ،ولي نه دقيقا ً همان فرايند. 214 ته ريز شدن در درخت Bمي تواند منجر به يکي از دو راه حل زير شود : )۱اگر يک گره مجاور نيز نيمه پر باشد ،مي توان دو گره را در هم ادغام کرد و يکي از آنها را براي استفاده دوباره آزاد ساخت. )۲اگر گره هاي مجاور بيش از نيمه پر باشند ،مي توان رکوردها را دوباره ميان گره ها توزيع کرد تا توزيع تقريبا ً متعادل گردد. 215 مسئله اندازه بلوک به تعيين حدود ( )limitsاندازه بلوک تبديل مي شود. 216 دو شرطي که در رابطه با حد بااليي اندازه بلوک در نظر مي گيريم عبارت است از : )۱اندازه بلوک بايد چنان باشد که بتوانيم چندين رکورد را به يکباره در حافظه نگه داريم. )۲خواندن ي ا نوشت ن ي ک بلوک نبايد زمان زيادي را صرف کند. 217 ساختار مختلط يک شاخص Bبعالوه يک مجموعه ‏ راB ترتيبي که رکوردها را نگه مي دارد درخت تشکيل مي دهد. 218 هدف از س اختن شاخ ص آ ن اس ت ک ه هنگام جستجوي رکوردي با يک کليد مشخص ،به ما کمک نمايد. شاخص بايد ما را به بلوکي از مجموع ه ترتيبي هدايت کند که حاوي اين رکورد است. شاخص به عنوان نقش ه راهنمايي براي مجموع ه ترتيبي عمل مي کند. 219 محتويات شاخص فقط تا آن حد مورد عالقه ما هستند که بتوانند ما را در رسيدن به بلوک درست در مجموعه ترتيبي رهنمون باشند. 220 ب ا در نظ ر گرفت ن مجموع ه شاخ ص ب ه عنوان ي ک نقشه راهنما مي توانيم اين گام بسيار مهم را برداريم که : الزم نيست کليدها در شاخص نگهداري شوند .آنچه که واقعا ً نياز داريم ،جداکننده ها هستند. 221 شاخص درخت Bرا مجموعه شاخص مي نامند. اين شاخص به همراه مجموعه ترتيبي ،ساختار فايلي را ‏ ‏B پيشوندي ساده نام دارد. تشکيل مي دهد که درخت 222 عبارت پيشوندي ساده ( )simple prefixنشانگر آن است ک ه مجموع ه شاخ ص حاوي کوتاهتري ن جداکننده ه ا يا پيشوندهاي کليدها است نه يک کپي از روي خود کليدهاي واقعي. 223 اگ ر حذف رکورده ا از مجموع ه ترتي بي و اضافه کردن رکورده ا ب ه آ ن ،تعداد رکورده ا را در مجموع ه ترتي بي تغيير دهد ،چه پيش مي آيد؟ واضح است که اگر تعداد بلوک هاي بيشتري داشته باشيم ، به تعداد جداکننده هاي کمتري نياز خواهيم داشت .تغيير دادن تعداد جداکننده ه ا قطعا ً بر مجموع ه شاخ ص تأثي ر خواهد داشت ،زيرا جداکننده ها در آنجا نگهداري مي شوند. 224 • ادامه مبحث دستيابي به فايل هاي ترتيبي شاخص دار و درخت هاي+B • درهم سازي 225 درج و حذف رکوردها همواره در مجموع ه ترتيبي رخ مي دهد ،زيرا رکوردها در آنجا قرار دارند. 226 اگر شکافتگي ،ادغام يا توزيع دوباره مورد نياز باشد ، عمليات را درست طوري انجام مي دهيد که در صورت نبود مجموعه شاخص انجام مي داديد. 227 پس از کامل شدن عمليات مربوط به رکورد در مجموعه ترتيبي تغييرات مورد نياز در مجموعه شاخص را اعمال کنيد : )۱اگر بلوک ها در مجموعه ترتيبي شکافته شوند ،يک خط جداکننده جديد بايد در مجموعه شاخص درج گردد. )۲اگ ر بلوک ه ا در مجموع ه ترتي بي ادغام شون د ،يک جداکننده بايد از مجموعه شاخص حذف گردند. )۳اگر رکوردها بين بلوک ها در مجموع ه ترتيبي دوباره توزي ع شون د ،مقدار ي ک جداکننده در مجموع ه شاخ ص بايد تغيير يابد. 228 چند دلي ل براي اس تفاده از ا ندازه بلوک مشترک ميان مجموعه هاي ترتيبي و انديسي وجود دارد : )۱معموال از آ ن رو براي مجموع ه شاخص از اندازه بلوک مجموع ه ترتي بي اس تفاده م ي شود ک ه تطاب ق خوبي ميان اندازه بلوک ،ويژگيهاي ديس ک گردان ،ومقدار حافظ ه در دسترس وجود دارد. اندازهBبلوک مشترک پياده سازي يک الگوي بافردهي براي )۲با ‏ پيشوندي ساده مجازي ،مشابه درختهاي Bمجازي ايجاد درخت آسان تر مي گردد. )۳بلوک هاي مجموعه ترتيبي و بلوک هاي مجموعه شاخص غالبا ً در يک فايل قرار داده مي شوند تا از جستجو ميان دو فايل جداگانه ‏B در هنگام دستيابي به درخت پيشوندي ساده پرهيز شود. 229 عالوه بر بردار جداکننده ها ،شاخص اين جداکننده ها و ليست شماره هاي بلوک مربوط ،ساختار بلوک مجموعه شاخص شامل موارد زير مي شود : )۱تعداد جداکننده ها )۲طول کل جداکننده ها 230 فرايند بارگذاري بسيار سريع پيش مي رود زيرا : )۱خروجي را مي توان به طور ترتيبي نوشت. )۲بجاي چندين بار گذر مربوط به عمليات درج ،فقط يک بار از داده ها گذر مي کنيم. )۳با پيشرفت کار نيازي به سازماندهي دوباره بلوک ها نيست. 231  ‏ ‏B تفاوت ميان درخت Bپيشوندي ساده و درخت آن است که Bاز پيشوندهايي به عنوان جداکننده استفاده نمي کند .در عوض جداکننده ها در مجموع ه انديس ،صرفا ً يک کپي از کليدهاي واقعي اند. 232 هر دو نوع درخت Bپيشوندي ساده و درخت ، Bاز يک مجموعه رکورد تشکيل مي شود که در يک مجموعه ترتي بي بر حس ب کلي د مرت ب شده ان و ب ا ي ک مجموعه اندي س جف ت شده ان د ک ه دس تيابي س ريع به بلوک حاوي هرگون ه ترکي ب رکوردي خاص را فراه م م ي آورد .تنها ‏ اختالف در آن است که درخت Bپيشوندي ساده اي که ساخته ايم ،با استفاده از پيشوندهاي کليد مجموع ه انديسي از کوتاهترين جداکننده ها ،تشکيل مي شود. ‏ 233 ‏ دو عامل وجود دارد که ممکن است وضعيت را به نفع درخت که در آن ،کپي کاملي از کليدها به عنوان جدا کننده بکار گرفته مي شود ،تغيير دهد : )۱دلي ل اس تفاده از کوتاهتري ن جداکننده ه ا ،فشرده سازي هرچه بيشتر آنها در يک بلوک از مجموعه شاخص است. )۲برخ ي مجموع ه هاي کليدي ،هنگام استفاده از روش پيشوندي ساده براي ايجاد جداکننده ها ،فشرده سازي چنداني از خود نشان نمي دهند. 234 ‏B درخت ، Bدرخت Bپيشوندي ساده و درخت Bدر خصوصيات زير مشترکند : ‏ )۱همگي ساختارهاي شاخص صفحه اي هستند ،يعني کل اطالعات موجود در بلوک را يکباره به حافظه منتقل مي کنند. ) ۲در هر سه روش ،درختهايي نگهداري مي شود که ارتفاع آنها وازنه است. )۳در هم ه موارد ،درختها از پايين به باال رشد مي کنند و موازنه از طريق شکستن بلوک ،ادغام و توزيع دوباره حفظ مي شود. )۴با هر سه ساختار مي توان از طريق استفاده از شکافتگي دو به سه و در صورت امکان ،توزيع دوباره به جاي شکستن بلوک ،بازدهي را باال برد. )۵هر سه روش را مي توان به عنوان ساختارهاي درختي مجازي پياده سازي کرد که در آن ،آخرين بلوک هاي استفاده شده ،در حافظه نگهداري مي شوند. )۶هر يک از اين سه روش را مي توان با استفاده از ساختارهاي موجود در بلوک با رکوردهاي طول متغير به کار برد. 235 ساختار درخت Bسه مزيت مهم ير درخت Bدارد: ‏ )۱مجموعه ترتيبي را مي توان به شيوه اي واقعا ً خطي و ترتي بي پردازش کرد و در نتيج ه ب ه ترتي ب کليده ا به رکوردها دستيابي مؤثري داشت. )۲شاخ ص ب ا ي ک کلي د منفرد ي ا جداکننده ب ه ازاي هر بلوک از رکوردهاي داده ها به جاي يک کليد (به ازاي هر رکورد از داده ها) ساخته مي شود. 236 درهم سازي 237 دستيابي ) O(1به فايل به اين معنا است که مهم نيست فايل تا چه اندازه بزرگ مي شود ،بلکه دستيابي به يک رکورد هميشه به تعداد کم و ثابتي پيگرد نياز دارد. در مقابل اين نوع دستيابي ،دستيابي ) O(Nقرار دارد که از جستجوهاي ترتيبي حاصل مي شود و هرچه اندازه فايل بزرگتر شود تعداد پيگردها نيز بيشتر مي شود. 238 تابع درهم سازي مانند يک جعبه سياه است که هرگاه کليدي در داخل آن انداخته مي شود ،يک آدرس ارئه مي دهد .به بيان رسمي تر ،درهم سازي ،تابع ) h(Kاست که کليد kرا به يک آدرس انتقال مي دهد. 239 درهم سازي را تصادفي کردن نيز مي گويند. درهم سازي ،از اين نظر که يک کليد به يک آدرس وابسته مي شود ،شبيه انديس سازي است. 240 درهم سازي و انديس سازي از دو جهت با هم تفاوت دارند : )۱آدرس هايي که از درهم سازي به دست مي آيند به صورت تصادفي اند. )۲با درهم سازي ،دو کليد مختلف ممکن است به يک آدرس انتقال داده شوند. 241 • ادامه مبحث درهم سازي 242 اگر دو رکورد به يک مکان در فايل انتقال يابند به آن برخورد مي گويند. 243 روش ايده آ ل مقابل ه ب ا برخورده ا اي ن اس ت که بتوان الگوريت م تبديل ي پيدا کرد ک ه ب ه طور کل ي از برخوردها جلوگيري کند .ب ه چني ن الگوريتم ي الگوريت م دره م سازي کامل گفته مي شود. 244 چندين راه مختلف براي کاهش تعداد برخوردها وجود دارد که بعضي از آنها عبارتند از : )۱پراکنده کردن رکوردها )۲استفاده از حافظه اضافي )۳قرار دادن بيش از يک رکورد در يک آدرس 245 به آدرس هايي که مي توانند چندين رکورد را نگهداري کنند باکت مي گويند. 246 در اين فصل يک الگوريتم درهم سازي ساده نوشته تا انواع اعمالي را که در الگوريتم درهم سازي انجام مي شوند نشان دهد که اين الگوريم سه مرحله دارد که عبارتند از : )۱نمايش کليد به شکل عددي )۲تا کردن و اضافه کردن )۳تقسيم کردن بر يک عدد اول و استفاده از باقيمانده به عنوان آدرس 247 در حالت ايده آل تابع درهم سازي ،رکوردها را به گونه اي توزي ع م ي کن د ک ه هي چ برخوردي وجود نداشته باشد. چنين توزيعي را توزيع يکنواخت گويند زيرا رکوردها را به صورت يکنواخت بين آدرس ها توزيع کرده است. 248 249 بعضي از روشهايي که به صورت بالقوه بهتر از درهم سازي هستند نام مي بريم: )۱جستجو در کليدها براي يافتن يک الگو )۲تا کردن قسمتهايي از کليد )۳تقسيم يک کليد بر يک عدد )۴مجذور کردن کليد و گرفتن عدد مياني 250 )۵تبديل مبنا توزيع پوآسون ابزاري رياضي را براي بررسي اثرات توزيع تصادفي ارائه مي کند. از توابع پوآسون مي توان براي پيش بيني تعداد آدرس هايي که ممکن است به رکوردهاي 0و 1و 2وغيره نسبت داده شوند استفاده کرد. 251 گرچه مي توانيم تعداد برخوردها را کم کنيم ،بايد ابزارهايي داشته باشيم که در صورت وقوع برخورد ،با آنها مبارزه کنيم .روش سرريز فزاينده را براي اين کار انتخاب مي کنيم. 252 اگر جستجو براي يافتن رکورد آغاز شود اما رکورد در فايل ذخيره نشده باشد چه اتفاقي مي افتد؟ جستجو از آدرس خانگي رکورد آغاز مي شود و اين جستجو در آدرس هاي بعدي نيز ادامه پيدا مي کند. دو اتفاق ممکن است رخ دهد : )۱اگر با يک فضاي خالي مواجه شود ،جستجوگر ممکن است فرض کند که فضاي خالي به اين معنا است که رکورد در فايل موجود نيست. )۲اگر فايل پر باشد ،جستجو ادامه پيدا مي کند تا به جايي مي رسد که جستجو ،از آنجا شروع شده بود و مشخص مي شود که رکورد در فايل موجود نيست. 253 منظور از طول جستجو ،تعداد دستيابي هاي الزم براي بازيابي يک رکورد از حافظه ثانويه است. 254 255 هنگاميک ه قرار اس ت ک ه ي ک رکورد ذخيره ي ا بازيابي شود ،آدرس باکت خانگي ،توسط درهم سازي مشخص مي شود. کل باکت در حافظه قرار مي گيرد. براي پيدا کردن رکورد مورد نظر ،رکوردهاي موجود در باکت جستجو مي شوند. 256 براي محاسبه دانسيته فشردگي فايل بايد ه م به تعداد آدرس ها (باکت ها) و هم به تعداد رکوردهايي که مي توان در هر آدرس قرار داد توجه کرد(اندازه باکت). 257 • ادامه مبحث درهم سازي • درهم سازي قابل توسعه 258 ب ه عنوان ي ک اص ل معموالً اس تفاده از باکت هاي بزرگتر از شيار ،ايده خوبي نيست(مگر در مواردي که رکوردها خيلي بزرگ باشند). 259 فايلهاي درهم سازي به دو روش با فايلهايي که تا کنون مورد بررسي قرار گرفته ان متفاوتند : )۱چوت تابع درهم سازي ،بر اساس تعداد ثابتي از آدرس هاي موجود بنا نهاده شده است ،اندازه منطقي فايل درهم سازي شده بايد از قبل مشخص باشد و همچنين ،وقتي اين تابع بر روي فايل عمل مي کند ،طول فايل ثابت باقي بماند. )۲چون شماره رکورد نسبي ( )RRNخانگ ي هر رکورد در فايل درهم سازي شده ،نسبت به کليدش منحصر به فرد است ،هر روالي که يک رکورد را اضافه يا حذف کند و يا تغيير دهد ،بايد طوري عمل کند که پيوند بين رکورد و آدرس خانگي آن را از بين نبرد. 260 تنها تفاوت بين فايل هايي که باکت دارند و فايل هايي که تنها مي توانند يک رکورد را در خود جاي دهند اين است که در فايل هاي باکت دار ،هر آدرس ،فضاي کافي براي ذخيره سازي بيش از يک رکورد منطقي را دارد. 261 به دو دليل حذف کردن يک رکورد از فايل درهم سازي شده پيچيده تر از اضافه کردن رکورد است : )۱محل ي از فاي ل ک ه در اثر حذف کردن آزاد شده است ،نبايد مانع جستجوهاي بعدي شود. )۲بايد امکان استفاده مجدد از فضاهاي آزاد شده ،در اضافه کردن هاي بعدي وجود داشته باشد. 262 خوبي عالئم ويژه اين است که ،دو مشکلي را که درقبل آن اشاره شد حل مي کند : )۱فضاي آزاد شده مانع جستجوي متوالي رکورد نمي شود. )۲مسلما ً مي توان از اين فضاي آزاد شده براي ذخيره رکوردهاي بعدي استفاده کرد. 263 چون رکوردهاي سرريز ،تأثير بس زايي در کارايي دارند تکنيک هاي زيادي براي جلوگيري از برخوردها پيشنهاد شده اند: )۱درهم سازي دوگانه )۲سرريز فزاينده زنجيره اي )۳پيوند با ناحيه سرريز ديگر )۴جدول هاي پراکندگي 264 درهم سازي قابل توسعه 265 ويژگي مهم در درخت AVLو درخت Bآن است که اين ساختارها خود تنظيم هستند و شامل مکانيسم هايي اند که خود را نگهداري مي کنند. 266 ايده کليدي در فرايند درهم سازي قابل توسعه ،ترکيب کردن درهم سازي معمولي با يک روش بازيابي ديگر موسوم به تراي ))trieاست. تراي ها را جستجوي مبنا نيز مي نامند زيرا ضريب انشعاب درخت جستجو برابر با تعداد نماهاي مختلف است که ممکن است در هر موقعيت از کليد ظاهر شوند. 267 اگر رکوردي اضافه کنيم وجايي براي آن در باکت وجود نداشته باشد ،باکت را مي شکافيم. 268 هدف از سيستم درهم سازي قابل توسعه ،يافتن راهي براي افزايش فضاي آدرس ،در پاسخ به سرريز شدن است نه پاسخ دهي با ايجاد رشته اي بلند از رکوردهاي سرريز و باکت هايي که بايد به طور خطي جستجو شوند. 269 عمليات اص لي روي باک ت ه ا دقيقا ً همانند عمليات رکوردهاي شاخص است : افزودن يک جفت کليد -آدرس به باکت ،جستجو به دنبال يک کليد و بازگرداندن آدرس آن ،و حذف يک کليد. 270 حذف ،عکس فرايند اضافه کردن است ،با ذکر اين نکته که فقط در صورتي مي توان رکوردهاي دو باکت را با هم ترکيب کرد که دو باکت با هم دوست باشند يعن ي اي ن دو باک ت از شکافت ن ي ک باک ت نتيجه شده باشند. 271 عمل تنزل شامل تخصيص فضا به آرايه جديدي از آدرس هاي باکت است که اندازه آن نصف اندازه اوليه اس ت و س پس آدرس هاي باک ت مشترک در ه ر جفت سلول را به يک سلول واحد در فهرست راهنماي جديد کپي مي کند. 272 درهم سازي پويا و درهم سازي قابل توسعه از نظر عملکرد شباهت بسيار دارند. هر دو از يک فهرست راهنما براي فقط آدرس باکت ها اس تفاده م ي کنن د و ه ر دو فهرس ت راهنم ا را از طريق استفاده از تراي ها توسعه مي دهند و هر دو تابع درهم سازي را به طور محلي به صورت يک تراي جستجوي دودويي توسعه مي دهند تا سرريز شدن قابل کنترل باشد. 273 اختالف اصلي ميان دو روش درهم سازي پويا ودر هم سازي قابل توسعه آن است که در هم سازي پويا ،رشد تدريجي و آهسته فهرست راهنما را امکان پذير مي سازد حال آنکه درهم سازي قابل توسعه فهرست راهنما را با دو برابر کردن آن بزرگ مي کند. درهم سازي پويا فهرست راهنماي توسعه يافته را به عنوان يک ساختار متصل بيان مي کند که به نوبه خود به عنوان يک آرايه قابل بيان است. 274