درخت بی
From Wikipedia, the free encyclopedia
در علوم کامپیوتر، یک درخت بی یا بیتری (به انگلیسی: B-tree) دادهساختاری درختی است که دادهها را به صورت مرتبشده نگه میدارد و جستجو، درج و حذف را در زمان مصرفی لگاریتمی میسر میسازد. برخلاف درختهای جستجوی دودویی متوازن (به انگلیسی: Balanced binary search tree)، این دادهساختار برای سیستمهایی که بلاکهای عظیم اطلاعات را خوانده و مینویسند بهینهسازی شدهاست. این دادهساختار معمولاً در پایگاههای داده و سیستم پرونده استفاده میشود.
ویرایش درخت بی | |||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
![]() یک درخت بی از مرتبهٔ ۵ | |||||||||||||||||||||
گونه | درخت | ||||||||||||||||||||
سال اختراع | ۱۹۷۲ | ||||||||||||||||||||
مخترع | رودلف بایر، ادوارد مککریت | ||||||||||||||||||||
زمان اجرای الگوریتم بر پایه نماد O بزرگ | |||||||||||||||||||||
|
در درخت بی، گرههای درونی (و نه برگها) میتوانند یک شمارهٔ متغیر از محدودهای ازپیشتعریفشده مربوط به گرههای فرزند را اختیار کنند. زمانی که دادهها درج شده یا از یک گره حذف میشوند، شمارهٔ گرههای فرزند آنها تغییر میکند. به منظور نگهداری محدودهٔ ازپیشتعریفشده، ممکن است گرههای درونی به هم متصل شده یا از هم جدا شوند. به دلیل اینکه محدودهای از گرههای فرزند مجاز هستند، درخت بی، همانند دیگر درختهای جستجوی متوازن، نیازی ندارد که به صورت متناوب اقدام به برقراری توازن کند، اما به دلیل اینکه گرهها کاملاً پر نیستند، ممکن است مقداری حافظه هدر رود. حدود بالا و پایین شمارهٔ گرههای فرزند، برای یک پیادهسازی خاص، بهطور خاص تعیین شدهاند. برای مثال در یک درخت بیِ ۳–۲ (غالباً تنها با عنوان درخت ۳-۲ مورد اشاره قرار میگیرد)، هر گره ممکن است تنها ۲ یا ۳ گرهٔ فرزند داشتهباشد.
یک درخت بی با استلزام اینکه همهٔ برگها در یک عمق قرار داشته باشند، به صورت متوازن نگه داشتهمیشود. این عمق از طریق عناصری که به درخت اضافه میشوند کمکم افزایش مییابد، ولی افزایش در عمق سراسری، کم اتفاق میافتد و وجود یک گرهٔ اضافیِ دورتر از ریشه را نتیجه میدهد.
درختهای بی، هنگامی که زمان دسترسی به گرهها به میزان قابل توجهی بیشتر از زمان پیمایش بین دو گره باشد، مزیتهایی اساسی بر دیگر انواع پیادهسازی دارند. این اتفاق معمولاً زمانی رخ میدهد که گرهها در حافظهای ثانویه مانند دیسک سخت قرار دارند. به واسطهٔ بییشینه نمودن تعداد فرزندانِ هر گرهٔ درونی، ارتفاع درخت افزایش مییابد، توازن کمتر رخ میدهد، و کارایی بالا میرود. معمولاً این مقدار طوری تنظیم میشود که هر گره، یک بلاک کامل از دیسک یا مقداری برابر از حافظهٔ ثانویه را اشغال کند. هنگامی که درختهای بیِ ۳–۲ ممکن است در حافظهٔ اصلی مفید واقع شوند، اگر اندازهٔ گرهها به اندازهٔ یک بلاک دیسک تنظیم شوند، نتیجه ممکن است، یک درخت بیِ ۵۱۳–۲۵۷ باشد (که در آن اندازهها از توانهای بزرگتر ۲ هستند). یک درخت بی از مرتبهٔ m (بیشینهٔ تعداد فرزندان هر گره) درختی است که خصوصیات زیر را برآورده میکند:
- هر گره حداکثر m فرزند دارد.
- هر گره (به جز ریشه و برگها) حداقل m/2 فرزند دارد.
- ریشه، در صورتی که برگ نباشد، حداقل دو فرزند دارد.
- همهٔ برگها در یک سطح ظاهر شده و اطلاعات را منتقل میکنند.
- گرهای که برگ نبوده و k فرزند داشتهباشد، حاوی k-1 کلید میباشد.
رودالف بیر و دد مککرِیت درخت بی را زمانی که در شرکت بوئینگ،[1] مشغول به کار بودند ابداع نمودند، اما حرف B واقعاً از کجا آمده؟ داگلاس کامر یک سری از احتمالات را پیشنهاد کرد:
- "Balanced," "Broad," یا "Bushy" ممکن است استفاده شدهباشند [چون همهٔ برگها در یک سطح قرار دارند]. دیگران اظهار داشتند که حرف "B" از کلمهٔ بوئینگ گرفته شده است [به این دلیل که پدیدآوردنده درسال ۱۹۷۲ در آزمایشگاههای تحقیقاتی علمی شرکت بوئینگ کار میکرد]. با این وجود پنداشتن درخت بی به عنوان درخت "بِیِر" نیز درخور است.[2]