एक B-tree एक स्व-संतुलित खोज वृक्ष है जहाँ प्रत्येक नोड कई कुंजियाँ रखता है और कई बच्चे हैं (उच्च fanout)। यह पेड़ को उथला रखता है, डिस्क रीड की संख्या को कम करता है — जो बिल्कुल यही है जो डेटाबेस और फ़ाइलसिस्टम को चाहिए।
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
| ऑपरेशन | समय | डिस्क I/O |
|---|---|---|
| खोज | O(log n) | O(ऊँचाई) |
| सम्मिलित / हटाएं | O(log n) | O(ऊँचाई) |
| रेंज स्कैन | O(log n + k) | क्रमिक पत्तियाँ |
डिस्क और SSD एक्सेस मेमोरी से कई गुना धीमा है, इसलिए जो मेट्रिक मायने रखता है वह I/O की गिनती है, तुलना नहीं।
उच्च fanout पेड़ को केवल कुछ स्तर गहरा रखकर I/O को नाटकीय रूप से कम करता है।
यही कारण है कि लगभग हर relational डेटाबेस इंडेक्स (और कई फ़ाइलसिस्टम) B+ trees पर बनाए गए हैं बजाय binary खोज के पेड़ों के।