لطفا به نکات زیر در هنگام خرید دانلود فایل پاورپوینت آشنايي با ايندکسهاي B-Tree توجه فرمایید.

1-در این مطلب، متن اسلاید های اولیه دانلود فایل پاورپوینت آشنايي با ايندکسهاي B-Tree قرار داده شده است 2-به علت اینکه امکان درج تصاویر استفاده شده در پاورپوینت وجود ندارد،در صورتی که مایل به دریافت  تصاویری از ان قبل از خرید هستید، می توانید با پشتیبانی تماس حاصل فرمایید 3-پس از پرداخت هزینه ، حداکثر طی 4 ساعت پاورپوینت خرید شده ، به ادرس ایمیل شما ارسال خواهد شد 4-در صورت  مشاهده  بهم ریختگی احتمالی در متون زیر ،دلیل ان کپی کردن این مطالب از داخل اسلاید ها میباشد ودر فایل اصلی این پاورپوینت،به هیچ وجه بهم ریختگی وجود ندارد 5-در صورتی که اسلاید ها داری جدول و یا عکس باشند در متون زیر قرار نخواهند گرفت

— پاورپوینت شامل تصاویر میباشد —-

اسلاید ۱ :

 ساختاريک ايندکس B-Tree چگونه است؟

 

هر نود ميتواند يک رکورد با تعداد ثابتي کليد (مثلا ۱۰۰) باشد.

 

تعداد کليد  در هر گره بين نصف تا تمام ظرفيت آن ميباشد.

 

براي اضافه نمودن کليد به نودي که ظرفيت آن تکميل شده:

آن نود را به ۲ نود جديد تقسيم ميکنند،

و بزرگترين کليد يکي از ۲ نود جديد به سطح بالاتر ارتقا پيدا ميکند.

 

حذف نمودن کليد از نودي که ظرفيت آن به مينيمم رسيده است:

ممکن است باعث ادغام نود با نود مجاور يا متوازن نمودن کليدها بين آنها گردد،

و پس از آن،  نود سطح بالاتر نيز بايد به روز شود.

اسلاید ۲ :

جستجوي کليد در ايندکس B-Tree

      روش جستجوي کليد دريک ايندکس B-Tree چيست؟

(۱براي جستجوي کليد k ، بايستي اوّل نود ريشه (Root) به حافظه آورده شود.

(۲در بين کليدهاي اين نود،  کليد Ki   جستجو ميشود ، بطوريکه:

يا Ki   اولين کليد در نود و   k Ki باشد  

يا   Ki -1 < k Ki باشد.

(۳در صورت يافتن  Ki  ، نود مربوطه به حافظه آورده ميشود،

و عمل ۲  تکرارمي گردد تا به نود برگ (Leave) برسيم و آدرس داده مورد نظر پيدا شود.

اسلاید ۳ :

 ايجاد کليد در ايندکس B-Tree

روش ايجاد کليد (Insert) در  B-Treeچگونه است؟

(۱با روش قبل نود برگ (n) مربوط به کليد k جستجو ميشود.

(۲در صورت وجود فضاي لازم:

 کليد  k  به نود اضافه ميشود،

 و اگر k از بزرگترين کليد موجود در نود بزرگتر باشد، نود سطح بالاتر نيز بروز ميشود.

(۳در صورت پر بودن نود:

بايستي آن را به دو نود (n) و (n+1) تقسيم نمود،

 کليد k را در يکي از دو نود جديد اضافه نمود،

 و سپس نود سطح بالاتر را نيز بروز نمود،

که خود ممکن است باعث تکرار اعمال ۲ و ۳  تا ريشه بشود.

اسلاید ۴ :

خواص ايندکس B-Tree

   ايندکسB-Tree  بطور رسمي چه خواصي دارد؟ (Formal definition)

 يک ايندکس  B-Tree با درجه m (Order) داراي خواص زير مي باشد:

 

هر نود ماکزيمم m فرزند دارد.

 

هر نود غير از ريشه (Root) و برگها (Leaves) لااقل m/2 فرزند دارد.

 

نود ريشه لااقل دو فرزند دارد مگر هنگامي که ريشه همان برگ باشد.

 

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

 

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

اسلاید ۵ :

    تعداد جستجودر B-Tree در بدترين حالت؟    (Worst-Case Search)

 

تعداد جستجوی لازم  در B-Tree براي يافتن يک کليد بستگي به تعداد سطوح دارد.

 

در بدترين حالت فقط نيمي از ظرفيت هر نود استفاده شده و تعداد سطوح ماکزيمم ميباشد.

 

در يک B-Tree با درجه m، رابطه تعداد کليد N و تعداد سطوح d در بدترين حالت برابر است با:

N ≥  (۲*[m/2] d-1 )       d ≤  (۱ +  logm/2(N/2))

مثال:

اگر تعداد کليد N=1000000 و B-Tree از درجه m=512 باشد:

d ≤ ۱ + log256 500000    d ≤ ۳٫۳۷

بنابر اين تعداد سطوح ماکزيمم ۳ ميباشد

اسلاید ۶ :

 حذف کليد در ايندکس B-Tree

       روش حذف کليد (Deletion) در B-Tree چگونه است؟

      براي حذف کليد k از نود (n):

(۱اگر نود (n) بيش از مينيمم ظرفيت مجاز کليد داشته باشد:

 کليد k حذف شده،

 و در صورتيکه اين کليد بزرگترين کليد نود (n) باشد نود سطح بالايي نيز بايستي بروز شود.

(۲Merge : اگر نود (n) به مينيمم ظرفيت مجاز کليدها رسيده باشد و فضاي موجود در نود مجاور آن (Sibling)  اجازه بدهد:

 هر دو نود با يکديگر ادغام شده،

 کليد k حذف مي شود،

و نود سطح بالايي نيز بروز ميگردد.                                         (چرا؟)

اسلاید ۷ :

 حذف کليد در ايندکس B-Tree

       روش حذف کليد (Deletion) در B-Tree چگونه است؟

      براي حذف کليد k از نود (n) (ادامه…):

(۳Redistribute: اگر نود (n) به مينيمم ظرفيت مجاز رسيده باشد و يکي از نودهاي مجاورکه نود پدر آنها يکي باشد (Sibling) بيش از مينيمم مجاز کليد داشته باشد:

کليدها بين دو نود تقسيم مي شوند،

 

سپس کليد k حذف شده،

 

 و پس از آن،  نود سطح بالاتر نيز بروز ميگردد.

اسلاید ۸ :

توزيع مجدد کليدها در B-Tree

    کاربردهای توزيع مجدد کليدها (Redistribution) در B-Tree کدامند؟

توزيع مجدد کليدها بين دو نود مجاورکه از يک نود پدر باشند (sibling) انجام پذيراست.

 

هنگام حذف يا ايجاد کليد باعث صرفه جويي در I/O يا به تاخير اندختن آن ميشود.

 

هنگام ايجاد کليد، اگر تعداد کليدهاي نود (n) به ماکزيمم رسيده باشد (Key overflow) :

 

در صورتي که يکي از نودهاي مجاور فضاي لازم را داشته باشد،

 

با توزيع مجدد کليدها بين دو نود از شکسته شدن نود (n) و ايجاد نود جديد جلوگيري ميشود.

 

هنگام حذف، اگر تعداد کليدهاي نود (n) به مينيمم مجاز رسيده باشد (Key underflow) :

 

 در صورتي که يکي از نودهاي مجاور کليد اضافي داشته باشد،

 

با توزيع مجدد کليدها بين دو نود از حذف نود (n) جلوگيري ميشود.

اسلاید ۹ :

انواع ديگرB-Tree

     ايندکس B*Tree چگونه است؟    

  نوعي B-Tree مي باشد که در آن:

(۱هر نود با لااقل ۲/۳ ظرفيت خود کليد دارد.

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

(۳ ظرفيت نود ريشه بيش از نودهاي ديگر مي باشد تا:

 درصورت Splitting، نودهاي جديد هر کدام  ۲/۳ظرفيت کليد داشته باشند.

(۴هنگام Splitting، هيچگاه يک نود به دو نود جديد تقسيم نمي شود بلکه:

دو نود مجاور با هم ادغام،

 

و سپس تبديل به سه نود مي شوند،

 

بطوريکه هر کدام  ۲/۳ظرفيت کليد داشته باشند.

اسلاید ۱۰ :

     ايندکس Virtual B-Tree چگونه است؟ 

   نوعي B-Tree ميباشد که در آن از روش Buffering of Pages استفاده ميگردد:

نگهداري تعدادي از نودها (Pages) در حافظه RAM باعث صرفه جويي در تعداد دسترسي به ديسک يا I/O ميشود.

 

 در اينصورت هنگام لزوم دسترسي به يک نود، اوّل به فضاي رزرو شده و نودهاي موجود در حافظه رجوع مي شود و اگر نود پيدا شد احتياجي به يک I/O جديد نميباشد.

 

درصورت لزوم انجام I/O و آوردن يک نود جديد به حافظه، يکي از صفحات که مدتي استفاده نشده است حذف شده و نود جديد جاي آنرا ميگيرد. (Least Recently Used)

 

روش ديگر بجاي روش LRU، اين مي باشد که حتّي الامکان صفحات مربوط به سطوح بالاتر در حافظه نگاه داشته شده  و صفحات مربوط به نودهاي برگ جايگزين شوند.