একটি 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 এর উপর নির্মিত।