پاورپوینت B trees, Btrees and Virtual B trees

لینک دانلود و خرید پایین توضیحات

دسته بندی : پاورپوینت

نوع فایل :  .ppt ( قابل ویرایش و آماده پرینت )

تعداد اسلاید : 24 اسلاید

 قسمتی از متن .ppt : 

Lecture 14B-trees, B*trees and Virtual B-trees (Sections 9.8-9.15)

آشنایی با ایندکسهای B-Tree

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

هر نود میتواند یک رکورد با تعداد ثابتی کلید (مثلا 100) باشد.

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

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

آن نود را به 2 نود جدید تقسیم میکنند،

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

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

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

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

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

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

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

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

یا Ki اولین کلید در نود و k ≤ Ki باشد

یا Ki -1 < k ≤ Ki باشد.

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

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

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

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

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

در صورت وجود فضای لازم:

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

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

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

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

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

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

که خود ممکن است باعث تکرار اعمال 2 و 3 تا ریشه بشود.