File Structure
Lecture 14 B-trees, B*trees and Virtual B-trees (Sections 9.8-9.15)
File Structure
آشنایی با ایندکسهای B-Tree
ساختاریک ایندکس B-Tree چگونه است؟
هر نود میتواند یک رکورد با تعداد ثابتی کلید (مثلا 100) باشد.
تعداد کلید در هر گره بین نصف تا تمام ظرفیت آن میباشد.
برای اضافه نمودن کلید به نودی که ظرفیت آن تکمیل شده:
آن نود را به 2 نود جدید تقسیم میکنند،
و بزرگترین کلید یکی از 2 نود جدید به سطح بالاتر ارتقا پیدا میکند.
حذف نمودن کلید از نودی که ظرفیت آن به مینیمم رسیده است:
ممکن است باعث ادغام نود با نود مجاور یا متوازن نمودن کلیدها بین آنها گردد،
و پس از آن، نود سطح بالاتر نیز باید به روز شود.
File Structure
جستجوی کلید در ایندکس B-Tree
روش جستجوی کلید دریک ایندکس B-Tree چیست؟
برای جستجوی کلید k ، بایستی اوّل نود ریشه (Root) به حافظه آورده شود.
در بین کلیدهای این نود، کلید Ki جستجو میشود ، بطوریکه:
یا Ki اولین کلید در نود و k ≤ Ki باشد
یا Ki -1 < k ≤ Ki باشد.
در صورت یافتن Ki ، نود مربوطه به حافظه آورده میشود،
و عمل 2 تکرارمی گردد تا به نود برگ (Leave) برسیم و آدرس داده مورد نظر پیدا شود.
File Structure
ایجاد کلید در ایندکس B-Tree
روش ایجاد کلید (Insert) در B-Treeچگونه است؟
با روش قبل نود برگ (n) مربوط به کلید k جستجو میشود.
در صورت وجود فضای لازم:
کلید k به نود اضافه میشود،
و اگر k از بزرگترین کلید موجود در نود بزرگتر باشد، نود سطح بالاتر نیز بروز میشود.
در صورت پر بودن نود:
بایستی آن را به دو نود (n) و (n+1) تقسیم نمود،
کلید k را در یکی از دو نود جدید اضافه نمود،
و سپس نود سطح بالاتر را نیز بروز نمود،
که خود ممکن است باعث تکرار اعمال 2 و 3 تا ریشه بشود.
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
Prof. Hyoung-Joo Kim, Comp Eng, Seoul National Univ
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
Prof. Hyoung-Joo Kim, Comp Eng, Seoul National Univ
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
Prof. Hyoung-Joo Kim, Comp Eng, Seoul National Univ
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
Prof. Hyoung-Joo Kim, Comp Eng, Seoul National Univ
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
Prof. Hyoung-Joo Kim, Comp Eng, Seoul National Univ
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
Prof. Hyoung-Joo Kim, Comp Eng, Seoul National Univ
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
Prof. Hyoung-Joo Kim, Comp Eng, Seoul National Univ
File Structure
خواص ایندکس B-Tree
ایندکسB-Tree بطور رسمی چه خواصی دارد؟ (Formal definition)
یک ایندکس B-Tree با درجه m (Order) دارای خواص زیر می باشد:
هر نود ماکزیمم m فرزند دارد.
هر نود غیر از ریشه (Root) و برگها (Leaves) لااقل m/2 فرزند دارد.
نود ریشه لااقل دو فرزند دارد مگر هنگامی که ریشه همان برگ باشد.
تمام برگها (Leaves) در یک سطح قرار دارند.
مجموعه برگها یک ایندکس کامل و مرتب شده از کلیدها را تشکیل میدهد.
File Structure
خواص ایندکس 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 باشد:
d ≤ 1 + log256 500000 → d ≤ 3.37
بنابر این تعداد سطوح ماکزیمم 3 میباشد
File Structure
حذف کلید در ایندکس B-Tree
روش حذف کلید (Deletion) در B-Tree چگونه است؟
برای حذف کلید k از نود (n):
اگر نود (n) بیش از مینیمم ظرفیت مجاز کلید داشته باشد:
کلید k حذف شده،
و در صورتیکه این کلید بزرگترین کلید نود (n) باشد نود سطح بالایی نیز بایستی بروز شود.
Merge : اگر نود (n) به مینیمم ظرفیت مجاز کلیدها رسیده باشد و فضای موجود در نود مجاور آن (Sibling) اجازه بدهد:
هر دو نود با یکدیگر ادغام شده،
کلید k حذف می شود،
و نود سطح بالایی نیز بروز میگردد. (چرا؟)
File Structure
حذف کلید در ایندکس B-Tree
روش حذف کلید (Deletion) در B-Tree چگونه است؟
برای حذف کلید k از نود (n) (ادامه…):
Redistribute: اگر نود (n) به مینیمم ظرفیت مجاز رسیده باشد و یکی از نودهای مجاورکه نود پدر آنها یکی باشد (Sibling) بیش از مینیمم مجاز کلید داشته باشد:
کلیدها بین دو نود تقسیم می شوند،
سپس کلید k حذف شده،
و پس از آن، نود سطح بالاتر نیز بروز میگردد.
File Structure
مثال حذف کلید در ایندکس 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
مثال(1):
File Structure
مثال حذف کلید در ایندکس 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
مثال(1) ادامه… :
File Structure
مثال حذف کلید در ایندکس B-Tree
مثال(2):
Prof. Hyoung-Joo Kim, Comp Eng, Seoul National Univ
File Structure
مثال حذف کلید در ایندکس B-Tree
مثال(2) ادامه… :
Prof. Hyoung-Joo Kim, Comp Eng, Seoul National Univ
File Structure
مثال حذف کلید در ایندکس B-Tree
مثال(2) ادامه… :
Prof. Hyoung-Joo Kim, Comp Eng, Seoul National Univ
File Structure
مثال حذف کلید در ایندکس B-Tree
مثال(2) ادامه… :
Prof. Hyoung-Joo Kim, Comp Eng, Seoul National Univ
File Structure
توزیع مجدد کلیدها در B-Tree
کاربردهای توزیع مجدد کلیدها (Redistribution) در B-Tree کدامند؟
توزیع مجدد کلیدها بین دو نود مجاورکه از یک نود پدر باشند (sibling) انجام پذیراست.
هنگام حذف یا ایجاد کلید باعث صرفه جویی در I/O یا به تاخیر اندختن آن میشود.
هنگام ایجاد کلید، اگر تعداد کلیدهای نود (n) به ماکزیمم رسیده باشد (Key overflow) :
در صورتی که یکی از نودهای مجاور فضای لازم را داشته باشد،
با توزیع مجدد کلیدها بین دو نود از شکسته شدن نود (n) و ایجاد نود جدید جلوگیری میشود.
هنگام حذف، اگر تعداد کلیدهای نود (n) به مینیمم مجاز رسیده باشد (Key underflow) :
در صورتی که یکی از نودهای مجاور کلید اضافی داشته باشد،
با توزیع مجدد کلیدها بین دو نود از حذف نود (n) جلوگیری میشود.
File Structure
انواع دیگرB-Tree
ایندکس B*Tree چگونه است؟
نوعی B-Tree می باشد که در آن:
هر نود با لااقل 2/3 ظرفیت خود کلید دارد.
عمل شکسته شدن نودها به کمک توزیع مجدد کلیدها حتی الامکان به تاخیر انداخته می شود.
ظرفیت نود ریشه بیش از نودهای دیگر می باشد تا:
درصورت Splitting، نودهای جدید هر کدام 2/3ظرفیت کلید داشته باشند.
هنگام Splitting، هیچگاه یک نود به دو نود جدید تقسیم نمی شود بلکه:
دو نود مجاور با هم ادغام،
و سپس تبدیل به سه نود می شوند،
بطوریکه هر کدام 2/3ظرفیت کلید داشته باشند.
File Structure
انواع دیگر B-Tree
ایندکس Virtual B-Tree چگونه است؟
نوعی B-Tree میباشد که در آن از روش Buffering of Pages استفاده میگردد:
نگهداری تعدادی از نودها (Pages) در حافظه RAM باعث صرفه جویی در تعداد دسترسی به دیسک یا I/O میشود.
در اینصورت هنگام لزوم دسترسی به یک نود، اوّل به فضای رزرو شده و نودهای موجود در حافظه رجوع می شود و اگر نود پیدا شد احتیاجی به یک I/O جدید نمیباشد.
درصورت لزوم انجام I/O و آوردن یک نود جدید به حافظه، یکی از صفحات که مدتی استفاده نشده است حذف شده و نود جدید جای آنرا میگیرد. (Least Recently Used)
روش دیگر بجای روش LRU، این می باشد که حتّی الامکان صفحات مربوط به سطوح بالاتر در حافظه نگاه داشته شده و صفحات مربوط به نودهای برگ جایگزین شوند.