ایک B-tree ایک self-balancing search tree ہے جہاں ہر node بہت سی keys رکھتا ہے اور بہت سے children رکھتا ہے (زیادہ fanout)۔ یہ tree کو کم گہرائی میں رکھتا ہے، disk reads کی تعداد کو کم کرتے ہوئے — جو بالکل وہی ہے جس کی ڈیٹا بیسز اور filesystems کو ضرورت ہے۔
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 میں، تمام values صرف leaves میں رہتی ہیں اور leaves linked ہیں، تو range scans leaves کی ایک linked list میں چلتی ہیں — WHERE age BETWEEN 20 AND 40 جیسی queries کے لیے بہترین۔
internal nodes: keys only (routing)
leaves: [..]<->[..]<->[..] <- linked for fast range scans
| Operation | Time | Disk I/O |
|---|---|---|
| search | O(log n) | O(height) |
| insert / delete | O(log n) | O(height) |
| range scan | O(log n + k) | sequential leaves |
Disk اور SSD رسائی memory سے کئی گنا سست ہے، تو وہ metric جو اہم ہے I/O count ہے، comparisons نہیں۔
بڑا fanout I/O کو کم کرتا ہے کیونکہ یہ tree کو صرف کچھ levels میں رکھتا ہے۔
یہی وجہ ہے کہ تقریباً ہر relational database index (اور بہت سے filesystems) B+ trees پر بنائے گئے ہیں binary search trees کی بجائے۔