مقالات و جزوه های درسی رشته کامپیوتر

 

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

  

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

 

 ۱) به صورت تکراري عمل مي کنند.

 

 ۲) در دو مرحله عمل مي کنند :

 

 

 الف) به صورت يک درميان روي کل صفحات

 

 ب) در داخل صفحات

 در مورد فرايند درج کردن ،تقسيم کردن و ارتقاء ملاحظات زير را در نظر مي گيريم :

 

 ۱) با جستجويي که تا سطح برگ پيش مي رود شروع مي شود.

 

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

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

 

 پايين ترين سطح کليدها در درخت B را برگ مي نامند.

 

 با استفاده از تعاريف ارائه شده از مرتبه و برگ ،مي توانيم خواص يک درخت B از مرتبه m را دقيقاً بيان کنيم :

 

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

m

 ۲) هر صفحه ،به جز ريشه و برگ ها ،حداقل] ____ [ فرزند دارد.

2

۳) ريشه حداقل دو فرزند دارد.

 

۴) تمام برگ ها در يک سطح قرار دارد.

 

۵) سطح برگ ها ،يک شاخص کامل و مرتب شده از فايل داده هاي مربوط به درخت را ايجاد مي کند.

 تضمين اين که درخت پهن و کم عمق باشد ،نه باريک و عميق ،مربوط به اين قوانين است :

m

 ۱) هر صفحه به جز ريشه و برگ ها حداقل ] _____  [ فرزند دارد.

 2                      m                                        

 ۲) هر صفحه حاوي حداقل] ____ [ و حداکثر m کليد است. 

                                        2

 

قوانين حذف کليد k از گره n در يک درخت B به اين ترتيبند :

 

 ۱) اگر تعداد کليدهاي n بيشتر از حد اقل کليدهاي مجاز است و k بزرگترين کليد در  nنيست ،کافي است k را از n حذف کنيد.

 

 ۲) اگر تعداد کليدهاي n بيشتر از حد اقل کليدهاي مجاز است و k بزرگترين کليد در  nاست ،k را حذف کنيد و شاخص هاس سطح بالاتر را متناسب با بزرگترين کليد جديد در n تغيير دهيد.

 

 ۳) اگر تعداد کليدهاي n دقيقاً برابر حداقل کليدهاي مجاز است و يکي از برادرهاي  n به اندازه کافي خالي است n را در برابرش ادغام کنيد و يک کليد را از گره مادر حذف کنيد.

 

 ۴) اگر تعداد کليدهاي n دقيقاً برابر حداقل کليدهاي مجاز است و يکي از برادرهاي  n کليدهاي زيادي دارد ،با انتقال دادن بعضي از کليدها از يک برادر به n ،کليدها را دوباره توزيع کنيد و شاخص هاي سطح بالاتر را متناسب با بزرگترين کليدهاي جديد گره هاي دستکاري شده تغيير دهيد.

 

 توزيع دوباره در هنگام درج ،راهي براي جلوگيري يا حداقل به تعويق انداختن ايجاد صفحات جديد است.

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

 

 

 بنابراين استفاده از توزيع دوباره به جاي تقسيم کردن باعث مي شود که درخت B از فضاي حافظه جانبي به طور مؤثرتر استفاده کند.

 يک نوع جديد از درخت B را به عنوان درخت B* تعريف مي کنيم که خواص آن به اين ترتيب است :

 

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

 2m - 1                                           

 ۲) هر صفحه به جزريشه حداقل ______ فرزند دارد.

                                                3

 ۳) ريشه حداقل دو فرزند دارد.

 

 ۴) تمام برگ ها در يک سطح قرار دارند.

 

 فرايند دستيابي به ديسک براي خواندن صفحه اي که در بافر وجود ندارد، نقص صفحه اي (page fault) ناميده مي شود.

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

 

 ۱) هيچگاه تا کنون از آن صفحه استفاده نکرده ايم.

 

 ۲) آن صفحه قبلاً در بافر بوده است اما صفحه جديدي جايگزين آن شده است.

 

 يک راه براي مورد دوم صفحه قبل اين است که صفحه اي را که زودتر از همه مورد استفاده قرار گرفته است جايگزين کنيم ،اين روش جايگزيني ،LRU (List Recently Used) ناميده مي شود.

 

 استفاده از رکوردهاي با طول متغير باعث صرفه جويي در فضا و در نتيجه کاهش ارتفاع درخت B مي شود.

 

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

 ساختارهاي فايل ترتيبي انديس دار ،امکان انتخاب از ميان دو ديدگاه متفاوت نسبت به فايل را فراهم مي آورند :

 

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

 

 ۲) ترتيبي : به فايل مي توان دستيابي ترتيبي داشت و رکوردها را به ترتيب توسط کليد بازگرداند.

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

هنگاميکه رکوردها را بلوک بندي مي کنيم ، بلوک واحد اصلي ورودي و خروجي مي شود.

 

 همانند درخت هاي B ،درج رکوردهاي جديد در يک بلوک مي تواند باعث سرريز شدن بلوک شود. 

 مشکل سرريز شدن را مي توان توسط يک فرايند شکستن بلوک ها کنترل کرد که شبيه فرايند شکستن بلوک ها در درخت هاي B است ،ولي نه دقيقاً همان فرايند.

 

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

 

 ۱) اگر يک گره مجاور نيز نيمه پر باشد ،مي توان دو گره را در هم ادغام کرد و يکي از آنها را براي استفاده دوباره آزاد ساخت.

 

 ۲) اگر گره هاي مجاور بيش از نيمه پر باشند ،مي توان رکوردها را دوباره ميان گره ها توزيع کرد تا توزيع تقريباً متعادل گردد.

 

 مسئله اندازه بلوک به تعيين حدود (limits) اندازه بلوک تبديل مي شود.

 دو شرطي که در رابطه با حد بالايي اندازه بلوک در نظر مي گيريم عبارت است از :

 

 ۱) اندازه بلوک بايد چنان باشد که بتوانيم چندين رکورد را به يکباره در حافظه نگه داريم.

 

 ۲) خواندن يا نوشتن يک بلوک نبايد زمان زيادي را صرف کند.

 ساختار مختلط يک شاخص B بعلاوه يک مجموعه ترتيبي که رکوردها را نگه مي دارد درخت B+  را تشکيل مي دهد.

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

 

 

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

 

 شاخص به عنوان نقشه راهنمايي براي مجموعه ترتيبي عمل مي کند.

 

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

 

 با در نظر گرفتن مجموعه شاخص به عنوان يک نقشه راهنما مي توانيم اين گام بسيار مهم را برداريم که :

 

 لازم نيست کليدها در شاخص نگهداري شوند. آنچه که واقعاً نياز داريم ،جداکننده ها هستند.

 

 شاخص درخت B را مجموعه شاخص مي نامند.

 

 اين شاخص به همراه مجموعه ترتيبي ،ساختار فايلي را تشکيل مي دهد که درخت پيشوندي ساده نام دارد.

 عبارت پيشوندي ساده (simple prefix) نشانگر آن است که مجموعه شاخص حاوي کوتاهترين جداکننده ها يا پيشوندهاي کليدها است نه يک کپي از روي خود کليدهاي واقعي.

 

 اگر حذف رکوردها از مجموعه ترتيبي و اضافه کردن رکوردها به آن ،تعداد رکوردها را در مجموعه ترتيبي تغيير دهد ،چه پيش مي آيد؟

 

 واضح است که اگر تعداد بلوک هاي بيشتري داشته باشيم ، به تعداد جداکننده هاي کمتري نياز خواهيم داشت. تغيير دادن تعداد جداکننده ها قطعاً بر مجموعه شاخص تأثير خواهد داشت ، زيرا جداکننده ها در آنجا نگهداري مي شوند.

 درج و حذف رکوردها همواره در مجموعه ترتيبي رخ مي دهد ،زيرا رکوردها در آنجا قرار دارند.

 اگر شکافتگي ،ادغام يا توزيع دوباره مورد نياز باشد ، عمليات را درست طوري انجام مي دهيد که در صورت نبود مجموعه شاخص انجام مي داديد.

 پس از کامل شدن عمليات مربوط به رکورد در مجموعه ترتيبي تغييرات مورد نياز در مجموعه شاخص را اعمال کنيد :

 

 ۱) اگر بلوک ها در مجموعه ترتيبي شکافته شوند ،يک خط جداکننده جديد بايد در مجموعه شاخص درج گردد.

 

 ۲) اگر بلوک ها در مجموعه ترتيبي ادغام شوند ،يک جداکننده بايد از مجموعه شاخص حذف گردند.

 

 ۳) اگر رکوردها بين بلوک ها در مجموعه ترتيبي دوباره توزيع شوند ،مقدار يک جداکننده در مجموعه شاخص بايد تغيير يابد.

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

 

 ۱) معمولا از آن رو براي مجموعه شاخص از اندازه بلوک مجموعه ترتيبي استفاده مي شود که تطابق خوبي ميان اندازه بلوک ،ويژگيهاي ديسک گردان ،ومقدار حافظه در دسترس وجود دارد.

 

 ۲) با اندازه بلوک مشترک پياده سازي يک الگوي بافردهي براي ايجاد درخت B+ پيشوندي ساده مجازي ،مشابه درختهاي B مجازي آسان تر مي گردد.

 

 ۳) بلوک هاي مجموعه ترتيبي و بلوک هاي مجموعه شاخص غالباً در يک فايل قرار داده مي شوند تا از جستجو ميان دو فايل جداگانه در هنگام دستيابي به درخت B+ پيشوندي ساده پرهيز شود.

 علاوه بر بردار جداکننده ها ،شاخص اين جداکننده ها و ليست شماره هاي بلوک مربوط ،ساختار بلوک مجموعه شاخص شامل موارد زير مي شود :

 

 ۱) تعداد جداکننده ها

 

 ۲) طول کل جداکننده ها

فرايند بارگذاري بسيار سريع پيش مي رود زيرا :

 

 ۱) خروجي را مي توان به طور ترتيبي نوشت.

 

 ۲) بجاي چندين بار گذر مربوط به عمليات درج ،فقط يک بار از داده ها گذر مي کنيم.

 

 ۳) با پيشرفت کار نيازي به سازماندهي دوباره بلوک ها نيست.

 تفاوت ميان درخت B+ پيشوندي ساده و درخت B+ آن است که B+ از پيشوندهايي به عنوان جداکننده استفاده نمي کند. در عوض جداکننده ها در مجموعه انديس ،صرفاً يک کپي از کليدهاي واقعي اند.

 

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

 دو عامل وجود دارد که ممکن است وضعيت را به نفع درخت B+ که در آن ،کپي کاملي از کليدها به عنوان جدا کننده بکار گرفته مي شود ،تغيير دهد :

 

 ۱) دليل استفاده از کوتاهترين جداکننده ها ،فشرده سازي هرچه بيشتر آنها در يک بلوک از مجموعه شاخص است.

 

 ۲) برخي مجموعه هاي کليدي ،هنگام استفاده از روش پيشوندي ساده براي ايجاد جداکننده ها ،فشرده سازي چنداني از خود نشان نمي دهند.

 

درخت B ، درخت B+ پيشوندي ساده و درخت B+ در خصوصيات زير مشترکند :

 

 ۱) همگي ساختارهاي شاخص صفحه اي هستند ،يعني کل اطلاعات موجود در بلوک را يکباره به حافظه منتقل مي کنند.

 

 ۲) در هر سه روش ، درختهايي نگهداري مي شود که ارتفاع آنها وازنه است.

 

 ۳) در همه موارد ،درختها از پايين به بالا رشد مي کنند و موازنه از طريق شکستن بلوک ،ادغام و توزيع دوباره حفظ مي شود.

 

 ۴) با هر سه ساختار مي توان از طريق استفاده از شکافتگي دو به سه و در صورت امکان ،توزيع دوباره به جاي شکستن بلوک ،بازدهي را بالا برد.

 

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

 

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

 

ساختار درخت B+ سه مزيت مهم ير درخت B دارد:

 

 ۱) مجموعه ترتيبي را مي توان به شيوه اي واقعاً خطي و ترتيبي پردازش کرد و در نتيجه به ترتيب کليدها به رکوردها دستيابي مؤثري داشت.

 

 ۲) شاخص با يک کليد منفرد يا جداکننده به ازاي هر بلوک از رکوردهاي داده ها به جاي يک کليد (به ازاي هر رکورد از داده ها) ساخته مي شود.

 

درهم سازي

 دستيابي O(1) به فايل به اين معنا است که مهم نيست فايل تا چه اندازه بزرگ مي شود ،بلکه دستيابي به يک رکورد هميشه به تعداد کم و ثابتي پيگرد نياز دارد.

 

 در مقابل اين نوع دستيابي ، دستيابي O(N) قرار دارد که از جستجوهاي ترتيبي حاصل مي شود و هرچه اندازه فايل بزرگتر شود تعداد پيگردها نيز بيشتر مي شود.

 

 تابع درهم سازي مانند يک جعبه سياه است که هرگاه کليدي در داخل آن انداخته مي شود ،يک آدرس ارئه مي دهد. به بيان رسمي تر ،درهم سازي ،تابع h(K) است که کليد k را به يک آدرس انتقال مي دهد.

درهم سازي را تصادفي کردن نيز مي گويند.

 

 

 درهم سازي ،از اين نظر که يک کليد به يک آدرس وابسته مي شود ،شبيه انديس سازي است.

درهم سازي و انديس سازي از دو جهت با هم تفاوت دارند :

 

 ۱) آدرس هايي که از درهم سازي به دست مي آيند به صورت تصادفي اند.

 

 ۲) با درهم سازي ،دو کليد مختلف ممکن است به يک آدرس انتقال داده شوند.