پاورپوینت آشنايي با ايندکسهاي B Tree (با کیفیت)
دسته بندي :
علوم پایه »
دانلود پاورپوینت های علمی
لینک دانلود و خرید پایین توضیحات
دسته بندی : پاورپوینت
نوع فایل : powerpoint (..ppt) ( قابل ويرايش و آماده پرينت )
تعداد اسلاید : 25 اسلاید
قسمتی از متن powerpoint (..ppt) :
بنام خدا
File Structure
File Structure
آشنايي با ايندکسهاي B-Tree
ساختار يک ايندکس B-Tree چگونه است؟
هر نود ميتواند يک رکورد با تعداد ثابتي کليد (مثلا 100 ) باشد.
تعداد کليد در هر گره بين نصف تا تمام ظرفيت آن ميباشد.
براي اضافه نمود ن کليد به نود ي که ظرفيت آن تکميل شده :
آن نود را به 2 نود جديد تقسيم ميکنند ،
و بزرگترين کليد يکي از 2 نود جديد به سطح بالاتر ارتقا پيدا ميکند.
حذف نمودن کليد از نود ي که ظرفيت آن به مينيمم رسيده است :
ممکن است باعث ادغام نود با نود مجاور يا متوازن نمودن کليدها بين آنها گردد،
و پس از آن ، نود سطح بالاتر نيز بايد به روز شود.
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 ، نود مربوط ه به حافظه آورده ميشود ،
و عمل 2 تکرار مي گردد تا به نود برگ ( 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 را در يکي از دو نود جديد اضافه نمود ،
و سپس نود سطح بالاتر را نيز بروز نمود ،
که خود ممکن است باعث تکرار اعمال 2 و 3 تا ريشه بشود.
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