درخت بی: تفاوت میان نسخه‌ها

درخت‌های بی، هنگامی که زمان دسترسی به گره‌ها به میزان قابل توجهی بیشتر از زمان پیمایش بین دو گره باشد، مزیت‌هایی اساسی بر دیگر انواع پیاده‌سازی دارند. این اتفاق معمولاً زمانی رخ می‌دهد که گره‌ها در حافظه‌ای ثانویه مانند دیسک سخت قرار دارند. به واسطهٔ بییشینه نمودن تعداد فرزندانِ هر گرهٔ درونی، ارتفاع درخت افزایش می‌یابد، توازن کم‌تر رخ می‌دهد، و کارآیی بالا می‌رود. معمولاً این مقدار طوری تنظیم می‌شود که هر گره، یک بلاک کامل از دیسک یا مقداری برابر از حافظهٔ ثانویه را اشغال کند. هنگامی که درخت‌های بیِ ۳-۲ ممکن است در حافظهٔ اصلی مفید واقع شوند، اگر اندازهٔ گره‌ها به اندازهٔ یک بلاک دیسک تنظیم شوند، نتیجه ممکن است، یک درخت بیِ ۵۱۳-۲۵۷ باشد (که در آن اندازه‌ها از توان‌های بزرگ‌تر ۲ هستند).

یک درخت بی از مرتبهٔ m (بیشینهٔ تعداد فرزندان هر گره) درختی است که خصوصیات زیر را برآورده می‌کند:

# هر گره (به جز ریشه و برگ‌ها) حداقل m/2 فرزند دارد.

# ریشه، در صورتی که برگ نباشد، حداقل دو فرزند دارد.