B-tree یا بی تری یک ساختار درختی جست‌وجوی متوازن و چندشاخه است که کلیدها را مرتب نگه می‌دارد. حرف B در منابع تاریخی تعاریف مختلفی داشته و بهتر است آن را به یک واژه قطعی مانند Binary تعبیر نکنیم.
برخلاف درخت دودویی، هر گره بی تری می‌تواند چندین کلید و فرزند داشته باشد. به همین دلیل طراحی آن برای خواندن و نوشتن صفحه‌ای دیسک مناسب است.
ساختار و پیچیدگی
- کلیدها در گره مرتب‌اند و جست‌وجو میان بازه‌های کلید انجام می‌شود.
- درخت متوازن است و همه برگ‌ها در عمق یکسان قرار دارند.
- جست‌وجو، درج و حذف معمولاً پیچیدگی لگاریتمی نسبت به تعداد کلیدها دارند.
- بسیاری از دیتابیس‌ها برای ایندکس از گونه B+ tree استفاده می‌کنند. در B+ tree داده یا اشاره‌گر رکورد معمولاً در برگ‌ها قرار می‌گیرد.
چه زمانی مناسب است؟
| عملیات | بی تری یا B+ tree | نکته |
|---|---|---|
WHERE id = 42 | جست‌وجوی کلید | برای کلید اصلی مناسب است |
WHERE price BETWEEN 100 AND 500 | پویش بازه | برتری نسبت به هش ایندکس در بازه‌های مرتب |
ORDER BY created_at | خواندن مرتب | با ایندکس منطبق ممکن است هزینه مرتب‌سازی کاهش یابد |
WHERE name LIKE 'sam%' | جست‌وجوی پیشوند | وابسته به Collation و برنامه اجرا |
CREATE INDEX idx_orders_customer_created ON orders(customer_id, created_at);
EXPLAIN SELECT id FROM orders WHERE customer_id = 15 ORDER BY created_at DESC;نکته فنی
ایندکس بی تری با درخت دودویی جست‌وجو یکی نیست. انتخاب ایندکس را با EXPLAIN و رفتار واقعی داده بررسی کنید.
اصطلاحات مرتبط: ایندکسینگ، بهینه‌سازی کوئری، جدول هش، دیتابیس.