بخشی از پاورپوینت
--- پاورپوینت شامل تصاویر میباشد ----
اسلاید 1 :
ساختاريک ايندکسB-Tree چگونه است؟
هر نود ميتواند يک رکورد با تعداد ثابتي کليد (مثلا 100) باشد.
تعداد کليد در هر گرهبين نصف تا تمام ظرفيت آن ميباشد.
براي اضافه نمودن کليد به نودي که ظرفيت آن تکميل شده:
آن نود را به 2نود جديد تقسيم ميکنند،
و بزرگترين کليد يکي از 2 نود جديد به سطح بالاتر ارتقا پيدا ميکند.
حذف نمودن کليد از نودي که ظرفيت آن به مينيمم رسيده است:
ممکن است باعث ادغام نود با نود مجاور يا متوازن نمودن کليدها بين آنها گردد،
و پس از آن، نود سطح بالاتر نيز بايد به روز شود.
اسلاید 2 :
جستجوي کليد در ايندکس B-Tree
روش جستجوي کليد دريک ايندکس B-Tree چيست؟
(1براي جستجوي کليد k ، بايستي اوّل نود ريشه (Root) به حافظه آورده شود.
(2در بين کليدهاي اين نود، کليد Ki جستجو ميشود ، بطوريکه:
يا Ki اولين کليد در نود و k ≤Ki باشد
يا Ki -1 < k ≤Ki باشد.
(3در صورت يافتن Ki ، نود مربوطه به حافظه آورده ميشود،
و عمل 2 تکرارمي گردد تا به نود برگ (Leave) برسيم و آدرس داده مورد نظر پيدا شود.
اسلاید 3 :
ايجادکليد در ايندکس B-Tree
روش ايجاد کليد (Insert) در B-Treeچگونه است؟
(1با روش قبل نود برگ (n) مربوط به کليد k جستجو ميشود.
(2در صورت وجود فضاي لازم:
کليد k به نود اضافه ميشود،
و اگر k از بزرگترين کليد موجود در نود بزرگتر باشد، نود سطح بالاتر نيز بروز ميشود.
(3در صورت پر بودن نود:
بايستي آن را به دو نود (n) و (n+1) تقسيم نمود،
کليد k را در يکي از دو نود جديد اضافه نمود،
و سپس نود سطح بالاتر را نيز بروز نمود،
که خود ممکن است باعث تکرار اعمال2 و 3 تا ريشه بشود.
اسلاید 4 :
خواص ايندکسB-Tree
ايندکسB-Tree بطور رسمي چه خواصي دارد؟ (Formal definition)
يکايندکس B-Tree با درجه m(Order) داراي خواص زير مي باشد:
هر نود ماکزيمم m فرزند دارد.
هر نود غير از ريشه (Root) و برگها (Leaves) لااقل m/2فرزند دارد.
نود ريشه لااقل دو فرزند دارد مگر هنگامي که ريشه همان برگ باشد.
تمام برگها (Leaves) در يک سطح قرار دارند.
مجموعه برگها يک ايندکس کامل و مرتب شده از کليدها را تشکيل ميدهد.
اسلاید 5 :
تعدادجستجودر 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 باشد:
d ≤ 1 + log256500000 → d ≤ 3.37
بنابر اين تعداد سطوحماکزيمم 3 ميباشد
اسلاید 6 :
حذف کليد در ايندکس B-Tree
روش حذف کليد (Deletion) در B-Treeچگونه است؟
براي حذف کليد k از نود (n):
(1اگر نود (n) بيش از مينيمم ظرفيت مجاز کليد داشته باشد:
کليد k حذف شده،
و در صورتيکه اين کليد بزرگترين کليد نود (n) باشد نود سطح بالايي نيز بايستي بروز شود.
(2Merge : اگر نود (n) به مينيمم ظرفيت مجاز کليدها رسيده باشد و فضاي موجود در نود مجاور آن (Sibling) اجازه بدهد:
هر دو نود با يکديگر ادغام شده،
کليد k حذف مي شود،
و نود سطح بالايي نيز بروز ميگردد. (چرا؟)
اسلاید 7 :
حذف کليد در ايندکس B-Tree
روش حذف کليد (Deletion) در B-Treeچگونه است؟
براي حذف کليد k از نود (n) (ادامه...):
(3Redistribute: اگر نود (n) به مينيمم ظرفيت مجاز رسيده باشد و يکي از نودهاي مجاورکه نود پدر آنها يکي باشد (Sibling) بيش از مينيمم مجاز کليد داشته باشد:
کليدها بين دو نود تقسيم مي شوند،
سپس کليد k حذف شده،
و پس از آن، نود سطح بالاتر نيز بروز ميگردد.
اسلاید 8 :
توزيع مجدد کليدها درB-Tree
کاربردهای توزيعمجدد کليدها (Redistribution) در B-Tree کدامند؟
توزيع مجدد کليدها بين دو نود مجاورکه از يک نود پدر باشند (sibling) انجام پذيراست.
هنگام حذف يا ايجاد کليد باعث صرفه جويي در I/O يا به تاخير اندختن آن ميشود.
هنگام ايجاد کليد، اگر تعداد کليدهاي نود (n) به ماکزيمم رسيده باشد (Key overflow) :
در صورتي که يکي از نودهاي مجاور فضاي لازم را داشته باشد،
با توزيع مجدد کليدها بين دو نود از شکسته شدن نود (n) و ايجاد نود جديد جلوگيري ميشود.
هنگام حذف، اگر تعداد کليدهاي نود (n) به مينيمم مجاز رسيده باشد (Key underflow) :
در صورتي که يکي از نودهاي مجاور کليد اضافي داشته باشد،
با توزيع مجدد کليدها بين دو نود از حذف نود (n) جلوگيري ميشود.
اسلاید 9 :
انواع ديگرB-Tree
ايندکس B*Tree چگونه است؟
نوعي B-Tree مي باشد که در آن:
(1هر نود با لااقل 2/3 ظرفيت خود کليد دارد.
(2عمل شکسته شدن نودها به کمک توزيع مجدد کليدها حتي الامکان به تاخير انداخته مي شود.
(3 ظرفيت نود ريشه بيش از نودهاي ديگر مي باشد تا:
درصورت Splitting، نودهاي جديد هر کدام 2/3ظرفيت کليد داشته باشند.
(4هنگام Splitting، هيچگاه يک نود به دو نود جديد تقسيم نمي شود بلکه:
دو نود مجاور با هم ادغام،
و سپس تبديل به سه نود مي شوند،
بطوريکه هر کدام 2/3ظرفيت کليد داشته باشند.
اسلاید 10 :
ايندکس VirtualB-Tree چگونه است؟
نوعي B-Tree ميباشد که در آن از روش Buffering of Pages استفاده ميگردد:
نگهداري تعدادي از نودها (Pages) در حافظه RAM باعث صرفه جويي در تعداد دسترسي به ديسک يا I/O ميشود.
در اينصورت هنگام لزوم دسترسي به يک نود، اوّل به فضاي رزرو شده و نودهاي موجود در حافظه رجوع مي شود و اگر نود پيدا شد احتياجي به يک I/O جديد نميباشد.
درصورت لزوم انجام I/O و آوردن يک نود جديد به حافظه، يکي از صفحات که مدتي استفاده نشده است حذف شده و نود جديد جاي آنرا ميگيرد. (Least Recently Used)
روش ديگر بجاي روش LRU، اين مي باشد که حتّي الامکان صفحات مربوط به سطوح بالاتر در حافظه نگاه داشته شده و صفحات مربوط به نودهاي برگ جايگزين شوند.
