پاورپوینت آشنایی با ایندکسهای B Tree (با کیفیت)
پاورپوینت آشنایی با ایندکسهای B Tree (با کیفیت)
لینک دانلود و خرید پایین توضیحات
دسته بندی : پاورپوینت
نوع فایل : powerpoint (..ppt) ( قابل ویرایش و آماده پرینت )
تعداد اسلاید : ۲۵ اسلاید
قسمتی از متن powerpoint (..ppt) :
بنام خدا
File Structure
File Structure
آشنایی با ایندکسهای B-Tree
ساختار یک ایندکس B-Tree چگونه است؟
هر نود میتواند یک رکورد با تعداد ثابتی کلید (مثلا ۱۰۰ ) باشد.
تعداد کلید در هر گره بین نصف تا تمام ظرفیت آن میباشد.
برای اضافه نمود ن کلید به نود ی که ظرفیت آن تکمیل شده :
آن نود را به ۲ نود جدید تقسیم میکنند ،
و بزرگترین کلید یکی از ۲ نود جدید به سطح بالاتر ارتقا پیدا میکند.
حذف نمودن کلید از نود ی که ظرفیت آن به مینیمم رسیده است :
ممکن است باعث ادغام نود با نود مجاور یا متوازن نمودن کلیدها بین آنها گردد،
و پس از آن ، نود سطح بالاتر نیز باید به روز شود.
P
W
D
M
P
T
W
A
B
C
D
G
I
M
N
P
R
S
T
U
W
File Structure
جستجوی کلید در ایندکس B-Tree
روش جستجو ی کلید در یک ایندکس B-Tree چیست؟
برای جستجوی کلید k ، بایستی اوّل نود ریشه ( Root ) به حافظه آورده شود.
در بین کلیدهای این نود ، کلید K i جستجو میشود ، بطوریکه :
یا K i اولین کلید در نود و k ≤ K i باشد
یا K i -1
در صورت یافتن K i ، نود مربوط ه به حافظه آورده میشود ،
و عمل ۲ تکرار می گردد تا به نود برگ ( Leave ) برسیم و آدرس داده مورد نظر پیدا شود.
P
W
D
M
P
T
W
A
B
C
D
G
I
M
N
P
R
S
T
U
W
File Structure
ایجاد کلید در ایندکس B-Tree
روش ایجاد کلید ( Insert ) در B-Tree چگونه است؟
با روش قبل نود برگ ( n ) مربوط به کلید k جستجو میشود.
در صورت وجود فضای لازم :
کلید k به نود اضافه میشود ،
و اگر k از ب زرگترین کلید موجود در نود بزرگتر باشد ، نود سطح بالاتر نیز بروز میشود.
در صورت پر بودن نود :
بایستی آن را به دو نود ( n ) و ( n+1 ) تقسیم نمود ،
کلید k را در یکی از دو نود جدید اضافه نمود ،
و سپس نود سطح بالاتر را نیز بروز نمود ،
که خود ممکن است باعث تکرار اعمال ۲ و ۳ تا ریشه بشود.
P
W
D
M
P
T
W
A
B
C
D
G
I
M
N
P
R
S
T
U
W
File Structure
مثال ایجاد کلید در ایندکس B-Tree
Input Sequence:
C S D T A M P I B W N G U R K E H O L J Y Q Z F X V
C
D
S
Insertion of C , S , D , T
into the initial page
D
D
A
C
S
Insertion of A causes node to split and the
largest key in each leaf node( D and T )to be
placed in the root node
T
T
T
Prof. Hyoung-Joo Kim, Comp Eng, Seoul National Univ
