B-tree هي شجرة بحث موازنة ذاتية حيث تحتفظ كل عقدة بـ مفاتيح عديدة وتمتلك عدة أطفال (high fanout). هذا يبقي الشجرة ضحلة، مما يقلل عدد disk reads — وهذا بالضبط ما تحتاجه قواعد البيانات وأنظمة الملفات.
Binary BST over 1,000,000 keys -> height ~20 (20 disk seeks)
B-tree, 100 keys/node -> height ~3 (3 disk seeks)
Each node = one disk block/page read.
[ 17 | 35 ]
/ | \
[4|9|12] [20|28] [40|50|60]
each node packs many keys -> few levels
في B+ tree، جميع القيم توجد في الأوراق والأوراق مرتبطة، لذا تمشي عمليات البحث عن نطاق عبر قائمة مرتبطة من الأوراق — مثالي للاستعلامات مثل WHERE age BETWEEN 20 AND 40.
internal nodes: keys only (routing)
leaves: [..]<->[..]<->[..] <- linked for fast range scans
| العملية | الوقت | Disk I/O |
|---|---|---|
| search | O(log n) | O(height) |
| insert / delete | O(log n) | O(height) |
| range scan | O(log n + k) | sequential leaves |
الوصول إلى القرص والـ SSD أبطأ بأوامر من حيث الحجم من الذاكرة، لذا المقياس الذي يهم هو عدد I/O، وليس المقارنات.
الـ fanout العالي يقلل I/O بشكل كبير بالحفاظ على الشجرة على بضعة مستويات فقط.
هذا هو السبب في أن كل فهرس قاعدة بيانات علائقية تقريباً (والعديد من أنظمة الملفات) مبني على B+ trees بدلاً من الأشجار البحثية الثنائية.