b-tree

بسمه تعالی

مقدمه : یک درخت بی یاB-Tree  داده‌ساختاری درختی است که داده‌ها را به صورت مرتب‌شده نگه می‌دارد و جستجو، درج و حذف را در زمان مصرفی لگاریتمی میسر می‌سازد .این داده‌ساختار برای سیستم‌هایی که بلاک‌های عظیم اطلاعات را خوانده و می‌نویسند بهینه‌سازی شده است. این داده‌ساختار معمولا در پایگاه‌های داده و فایل‌های سیستمی استفاده می‌شود.

مفهوم : هر درخت از تعدادی نود تشکیل شده است . درجه هر نود تعداد زیر درختهای آن نود است به نودهای که دارای درجه صفر هستند برگ گفته می شود به نودهای دارای درجه بزرگتر از صفر، نودهای غیر انتهایی گفته می شود به ریشه های زیر درختان فرزند گفته می شود والد نودی است که یک یا چند فرزند دارد فرزندان یک والد همزاد هستند. به والد والد، جد گفته می شود. تمام نودهایی که روی مسیر ریشه به سمت یک نود قرار دارند، نیاکان آن نود هستند. به تمام نودهایی که در زیر درخت مربوط به یک نود قرار دارند، اعقاب آن نود گفته می شود.

درجه درخت: حداکثر درجه نودهای درخت .

سطح نود:  

سطح ریشه = 1

سطح نودهای غیر ریشه= تعداد لینکهای بین نود و ریشه + 1

ارتفاع یا عمق درخت : حداکثر سطح نودهای درخت

حداکثر تعداد نودها در سطح 1 برابر  است.

حداکثر تعداد نودها در درخت باینری با ارتفاع k ، برابر  است.

مزایا: درخت‌های بی، هنگامی که زمان دسترسی به گره‌ها به میزان قابل توجهی بیشتر از زمان پیمایش بین دو گره باشد، مزیت‌هایی اساسی بر دیگر انواع پیاده‌سازی دارند. این اتفاق معمولاً زمانی رخ می‌دهد که گره‌ها در حافظه‌ای ثانویه مانند دیسک سخت قرار دارند. به واسطه بییشینه نمودن تعداد فرزندانِ هر گره درونی، ارتفاع درخت افزایش می‌یابد، توازن کم‌تر رخ می‌دهد، و کارآیی بالا می‌رود.

مشکلات:

اندازه حافظه ثابت است  . براحتی قابل گسترش نیست . اگر درخت بالانس نباشد، حافظه هدر می رود

 در نرم افزار StarDic از الگوریتم B-Tree  استفاده شده است.

  

/ 0 نظر / 18 بازدید