دانلود پاورپوینت آشنايي با ايندکسهاي B-Tree

  دانلود پاورپوینت آشنايي با ايندکسهاي B-Tree

عنوان های پاورپوینت آشنايي با ايندکسهاي B-Tree عبارتند از :

آشنايي با ايندکسهاي B-Tree
جستجوي کليد در ايندکس B-Tree
ايجاد کليد در ايندکس B-Tree
مثال ايجاد کليد در ايندکس B-Tree

خواص ايندکس B-Tree
خواص ايندکس B-Tree
حذف کليد در ايندکس B-Tree
حذف کليد در ايندکس B-Tree
مثال حذف کليد در ايندکس B-Tree
مثال حذف کليد در ايندکس B-Tree

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

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

تکه ها و قسمت های اتفاقی از فایل آشنايي با ايندکسهاي B-Tree

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 تا ريشه بشود.
مثال ايجاد کليد در ايندکس B-Tree
مثال ايجاد کليد در ايندکس B-Tree
مثال ايجاد کليد در ايندکس B-Tree
مثال ايجاد کليد در ايندکس B-Tree
مثال ايجاد کليد در ايندکس B-Tree

  دانلود پاورپوینت آشنايي با ايندکسهاي B-Tree
مثال ايجاد کليد در ايندکس B-Tree

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

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

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

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

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

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

مجموعه برگها يک ايندکس کامل و مرتب شده از کليدها را تشکيل ميدهد.
خواص ايندکس B-Tree
تعداد جستجودر B-Tree در بدترين حالت؟ (Worst-Case Search)

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

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

در يک B-Tree با درجه m، رابطه تعداد کليد N و تعداد سطوح d در بدترين حالت برابر است با:
N ≥ (2*[m/2] d-1 ) → d ≤ (1 + logm/2(N/2))

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

کليد k حذف مي شود،
و نود سطح بالايي نيز بروز ميگردد. (چرا؟)

حذف کليد در ايندکس B-Tree
روش حذف کليد (Deletion) در B-Tree چگونه است؟
براي حذف کليد k از نود (n) (ادامه...):

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

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

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

و پس از آن، نود سطح بالاتر نيز بروز ميگردد.
مثال حذف کليد در ايندکس B-Tree
Deleting “T” falls into case 1
Deleting “U” falls into case 1
Deleting “C” falls into case 2: Merge node 2 with node 3

مثال حذف کليد در ايندکس B-Tree
Deleting “W” falls into case 3:
Redistribute keys between node 4 and node 5
Deleting “M” allows for two possibilities: case 3 or 1
Merge Node 3 with Node 2; or
Redistribute keys between Node 3 and Node 4

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

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

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

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

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

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

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

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

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

با توزيع مجدد کليدها بين دو نود از حذف نود (n) جلوگيري ميشود.
انواع ديگرB-Tree
ايندکس B*Tree چگونه است؟

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

هر نود با لااقل 2/3 ظرفيت خود کليد دارد.

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

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

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

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

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

...

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

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

30 تا 70 درصد پروژه | پاورپوینت | سمینار | طرح های کارآفرینی و  توجیهی |  پایان-نامه |  پی دی اف  مقاله ( کتاب ) | نقشه | پلان طراحی |  های آماده به صورت رایگان میباشد ( word | pdf | docx | doc | )